What is the motivation behind " Descriptive Complexity "?

If you're interested in logic, "what problems can you express in this logic?" is a completely natural question.

If you're interested in computational complexity, descriptive complexity gives another tool that you might be able to use to prove things. For example, the fact that existential second-order logic exactly corresponds to NP means that, if you can prove either (a) no logic corresponds exactly to P or (b) there is a logic that corresponds exactly to P but it has different expressive power to existential second-order, then you've proven that P$\,\neq\,$NP. And it's turned out that trying to prove it via logic has been exactly as fruitful as every other approach!


Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$?

If you have $n$ bits available you can represent the numbers $0$ to $2^n-1$ in binary. Therefore, if you want to represent a number $x$ in binary, you need a number of bits $n$ that is large enough so that

$$
\begin{split}
2^n - 1 & \geq x\\
n & \geq \log_2(x+1)\,.
\end{split}
$$

Now there are two cases for $\log_2(x+1)$:

It is an integer. Then $\log_2(x)$ won't be. It'll be slightly less. So $\lfloor\log_2(x)\rfloor + 1$ will yield the same value. (The exception where $x=1$ can be checked separately.)
It isn't an integer. In this case $\lfloor\log_2(x)\rfloor + 1$ yields the next largest integer just as $\lfloor\log_2(x+1)\rfloor + 1$ would.

In either case, because $n$ is always an integer we can write

$$
n \geq \lfloor\log_2(x)\rfloor + 1\,.
$$


The language  $L' = \Sigma^* y\Sigma^*$ is regular and, by the closure properties of regular languages, so is $\Sigma^* \setminus L'$. Then, by the closure properties of context-free languages, $L_2  = L_1 \cap (\Sigma^* \setminus L')$ is context-free (since it can be written as the intersection of a context free language with a regular language).


Deriving epsilon with a context free grammar with epsilon rules

Here's an example to get you started. Suppose our grammar had productions
$$
S\rightarrow TT\qquad T\rightarrow UU\qquad U\rightarrow \epsilon
$$
so $l=2, m=3$.

Then, how fast can you get from $S$ to $\epsilon$? Clearly, it'll take 7 steps:
$$
S\Rightarrow TT\Rightarrow UUT\Rightarrow UUUU\Rightarrow UUU\Rightarrow UU\Rightarrow U\Rightarrow \epsilon
$$
Notice that $(l^m-1)/(l-1)=(2^3-1)/(2-1)=7$.

What does the parse tree for this derivation look like? In particular, how many leaves will it have?

Now generalize this construction.


Why are NP-complete problems so different in terms of their approximation?

One reason that we see different approximation complexities for NP-complete problems is that the necessary conditions for NP-complete constitute a very coarse grained measure of a problem's complexity. You may be familiar with the basic definition of a problem $\Pi$ being NP-complete:

$\Pi$ is in NP, and
For every other problem $\Xi$ in NP, we can turn an instance $x$ of $\Xi$ into an instance $y$ of $\Pi$ in polynomial time such that $y$ is a yes-instance of $\Pi$ if and only if $x$ is a yes-instance of $\Xi$.

Consider condition 2: all that is required is that we can take $x$ and turn it into some $y$ that preserves the "single-bit" yes/no answer. There's no conditions about, for example, the relative size of the witnesses to the yes or no (that is, the size of the solution in the optimization context). So the only measure that's used is the total size of the input which only gives a very weak condition on the size of the solution. So it's pretty "easy" to turn a $\Xi$ into a $\Pi$.

We can see the difference in various NP-complete problems by looking at the complexity of the some simple algorithms. $k$-Coloring has a brute force $O(k^{n})$ (where $n$ is the input size). For $k$-Dominating Set, a brute force approach take $O(n^{k})$. These are, in essence the best exact algorithms we have. $k$-Vertex Cover however has a very simple $O(2^{k}n^{c})$ algorithm (pick an edge, branch on which endpoint to include, mark all covered, keep going until you have no edges unmarked or you hit your budget of $k$ and bactrack). Under polynomial-time many-one reductions (Karp reductions, i.e. what we're doing in condition 2 above), these problems are equivalent.

When we start to approach complexity with even slightly more delicate tools (approximation complexity, parameterized complexity, any others I can't think of), the reductions we use become more strict, or rather, more sensitive to the structure of the solution, and the differences start to appear; $k$-Vertex Cover (as Yuval mentioned) has a simple 2-approximation (but doesn't have an FPTAS unless some complexity classes collapse), $k$-Dominating Set has a $(1+\log n)$-approximation algorithm (but no $(c\log n)$-approximation for some $c>0$), and approximation doesn't really make sense at all for the straight forward version of $k$-Coloring.


Better word to describe JavaScript "algorithm"?

You can certainly describe the inner workings of your project as an algorithm. It takes an input (whatever information it obtains from the browser) and produces an output, as a result of some scheme of calculations. Perhaps it needs to read inputs during the course of its calculations (depending on the first inputs, it might make different queries of the browser), so it might be some sort of interactive or adaptive algorithm.


Proof of inequality $\lceil x \rceil \le x+1$

The definition of $\lceil x \rceil$ is:

$\lceil x \rceil$ is the minimal integer $n$ such that $n \geq x$.

(The existence of such an integer makes the reals an Archimedean field.)
Let us assume, for the sake of contradiction, that $\lceil x \rceil \geq x + 1$. Then $\lceil x \rceil - 1 \geq x$. Since $\lceil x \rceil - 1$ is also an integer, this contradicts the definition of $\lceil x \rceil$. Thus $\lceil x \rceil < x + 1$.
It is also easy to check that the inequality is tight, in the sense that $1$ cannot be replaced by any smaller $\theta$. Indeed, if $\theta = 1 - \epsilon$ for $\epsilon \in (0,1)$, then $\lceil \epsilon \rceil = 1 = \epsilon + \theta$.


The Shortest Levenshtein's Distance should be good enough.
See if this Matching Wildcards Wikipedia page can be of help.


Can intersection of non-context-free languages be context-free?

Let $L$ be an arbitrary language. Then
$$ \{ 0x : x \in L \} \cap \{ 1x : x \in L \} = \emptyset. $$


Understanding details of NP-Hard definition

The definition of NP-hardness for a problem $X$ is that every problem in NP reduces to $X$. Informally speaking, "$L$ reduces to $X$" means that if you could solve $X$, you could use that to solve $L$.

So, if $X$ is NP-hard, you can reduce all problems in NP, including the ones in P, to $X$. There's no contradiction here: $X$ is a hard problem, so saying that you can reduce a problem in P to $X$ is just saying, "If I could solve this hard problem, I could use that to solve a pretty easy problem." Sure, there are easier ways of solving that easy problem (that's why we call it an easy problem!) but all you've done is to show that there's a hard way to solve it, too.

  P is also a part of NP so when we say every problem y which belongs to NP we are saying we can take a problem in P and reduce to some X. Then X is NP-Hard?

Maybe it's just inaccurate writing but you have the implication the wrong way around. If $X$ is NP-hard, then you can reduce a problem in P to $X$. The converse (if you can reduce a problem in P to $X$, then $X$ is NP-hard) is not true.


Computational Complexity of Solutions of the Traveling Purchaser Problem on a Small Data Set

First, it is good to observe that the problem is very difficult to approximate (see e.g., my earlier answer on it here).

Second, there is very recent survey on the traveling purchaser problem and its variants by Manerba et al. [1]. Essentially, you will find discussion on relevant methods that have been applied to solve the problem in practical settings. If you want theoretical time bounds for heuristics, see Section 6.1.1. on page 13.

[1] Manerba, Daniele, Renata Mansini, and Jorge Riera-Ledesma. "The traveling purchaser problem and its variants." European Journal of Operational Research 259.1 (2017): 1-18.


Is best case complexity big Omega of worst case complexity?

Consider the following algorithm $A$:

If the input consists entirely of zeroes, return.
Otherwise, count from $1$ to $n^2$, where $n$ is the length of the input.

The best case complexity of this algorithm is $O(n)$, and the worst-case complexity of this algorithm is $\Omega(n^2)$. Does $n = \Omega(n^2)$ hold?


How can I prove that my greedy algorithm for least guards is optimal?

You can achieve this per induction over the position of the last artwork. Note that in the optimal strategy the guard must be put 5 meter ahead of the left most artwork and not exactly at it.

In the induction step you have to consider an additional artwork and distinct two cases, whether it is covered by the last fixed guard or not. If it is, you do not have to add one and hence, the optimal can not be better. In case it is not, it is easy to show, that an optimal that woul have covered it should have used strictly more guards.


What is the exact relation between programming languages and Turing machines?

Maybe I'm misreading the question, but it sounds like there's some confusion in the comparison between Turing machines and programming languages.

The definition and method of defining a Turing machine constitute a programming language. Turing machines represent programs in that language.

Language syntax and semantics (e.g., in BNF) can constitute a programming language, and artifacts which satisfy those syntactic and semantic constraints are programs in that language.

So it's not really precise (IMHO; of course we can think about what TMs do in different ways, and in some of these ways of looking at TMs, you could think of individual TMs as defining programming languages. Indeed, a classically constructed universal Turing machine defines a very clear programming language, i.e., representations of Turing machines as strings) to compare implementing a programming language to implementing a Turing machine. Implementing a programming language involves defining the rules of the game, much like Turing defined the rules of the game (or whoever it was, whatever) when he defined what it meant for something to be Turing machine.

"Implementing" a programming language, and defining Turing machines, is a very difficult activity. Writing programs in a language, and defining specific Turing machines, is also a difficult activity. But they are quite different activities (except in those exceptional cases where you're writing a Turing machine to act as an interpreter, in which case maybe it makes sense to talk about designing a programming language via writing a TM... but I'm not sure this is what you were after).


Simulated annealing to find the correct permutation of 20 words

No, that's not simulated annealing.  It's not really even close.

Whether it will be a good enough approach will depend on your metric.  Since you haven't told us what the metric is, it's not really possible to say.  In the worst case, if your metric is sufficiently horrible, you might need to explore all $20!$ permutations.   In any case, usually the only reliable way to find out whether your approach is a good one is to implement and see what happens.  There are few theorems that gives useful provable results about how effective the approach will be; instead, you need to use empirical evaluation.


Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

let $ z \in L$ such that $ |z| \geq n $ (where $n$ is the lemma's constant).
By the pumping lemma for CFL, we know that we can write $z=uvwxy$ such that:

$|vwx| \leq n$
$|vx| \geq 1$
for all $i \geq 0$: $uv^iwx^iy \in L$

Because $L$ is over an unary alphabet, we can change the order of the sub-words and the word ($z$) will not change, meaning we can also write $z=wvxuy$.

So. for all $i \geq 0$, $uv^iwx^iy = wv^ix^iuy = w(vx)^iuy$.
Let's write a little different:
$u' = w, v' = vx, w' = uy$. and we have that $u'(v')^iw' \in L$.

It's easy to see that $|u'v'| \leq n$ and $|v'| \geq 1$,
So we can conclude that for the same $n$, the conditions of pumping lemma for regular languages holds.

It might be worth mentioning that every CFL of unary alphabet is also regular (We know that even though a language satisfies the pumping lemma for regular/CF languages, it does't mean that the language is regular/CF).

It can be shown using Parikh's theorem, and showing that for every semi-linear set $S \subseteq \mathbb{N}  $ there is a regular language $L$ such that $\Psi (L)=S$ (or $p(L)$ using wikipedia's notations)


Claim: No, there is no such $\mu$.

Proof: We give an infinite sequence of AVL trees of growing size whose weight-balance value tends to $0$, contradicting the claim.

Let $C_h$ the complete tree of height $h$; it has $2^{h+1}-1$ nodes.

Let $S_h$ the Fibonacci tree of height $h$; it has $F_{h+2} - 1$ nodes. [1,2,TAoCP 3]

Now let $(T_h)_{i\geq 1}$ with $T_h = N(S_h,C_h)$ the sequence of trees we claim to be a counter example.

Consider the weight-balancing value of the root of $T_h$ for some $h \in \mathbb{N}_+$:

$\qquad \displaystyle \begin{align*}
  \frac{F_{h+2}}{2^{h+1} + F_{h+2} - 1} &= \frac{1}{1 + \frac{2^{h+1}}{F_{h+2}} - \frac{1}{F_{h+2}{}}} \\
&\sim \frac{F_{h+2}}{2^{h+1}} \\
&= \frac{\frac{1}{\sqrt{5}}(\phi^{h+2} - \hat{\phi}^{h+2})}{2^{h+1}} \\
&\sim \frac{\phi^{h+2}}{\sqrt{5}\cdot 2^{h+1}} \underset{h \to \infty}{\to} 0
\end{align*}$

This concludes the proof.

Notation:

$F_n$ is the $n$th Fibonacci number
$\phi \approx 1.6$ is the Golden Ratio, $\hat{\phi} \approx -0.62$ its conjugate.
$f \sim g$ means that $f$ and $g$ are asymptotically equal, i.e. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$.

Nota bene: Fibonacci trees are exactly those AVL trees with the least nodes for a given height (or, equivalently, the maximum height for a given number of nodes).

Addendum: How can we come up with Fibonacci trees if we had not overheard a professor mentioning them? Well, what would an AVL tree of height $h$ with as few nodes as possible look like? Certainly, you need a root. One of the subtrees needs to have height $h-1$, and we have to choose it with as few nodes as possible. The other one can have height $h-2$ without violating the height balancing condition, and we choose it also with as few nodes as possible. In essence, we construct the trees we want recursively! These are the first four:

[source]

We set up a recurrence for the number of nodes $f(h)$ in the thusly constructed tree with height $h$:

$\qquad \displaystyle \begin{align*}
  f(1) &= 1 \\
  f(2) &= 2 \\
  f(h) &= f(h-1) + f(h-2) + 1 \qquad n \geq 3
\end{align*}$

Solving it leads to $f(h) = F_{h+2} - 1$ which we used above.

The same proof is given (with less detail) in Binary search trees of bounded balance by Nievergelt and Reingold (1972).


Pumping Lemma for Regular Languages with 3 variables (a^nb^mc^m)

Apply the pumping lemma on the word $b^nc^n$.


Mutex implementation on top of a minimalistic preemptive scheduler

Mutex

For the mutex I'm going to propose a modification of the MCS spinlock that uses your sleep/wake primitives to block instead of spin while waiting to acquire the mutex.  The MCS lock was introduced in

  Mellor-Crummey, John M; Scott, Michael L: Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors, ACM Trans. on Comp. Sys. (TOCS), 9(1):21-65, 1991.

The MCS lock was specifically designed to eliminate the undesirable coherence traffic associated with spin locks in large-scale cache-coherent shared memory multiprocessors (which is not your concern) but I'm suggesting it because of the analogy between inter-processor coherence messaging in multiprocessors and your sleep and wake primitives.

Essentially we are keeping a linked-list of waiters for the lock.  The lock itself is a pointer to the tail of the list.  The head of the list is the thread that currently has the lock.  The tricky part is that there are two pointers to the tail so you need to be careful about the lack of atomicity when adding or removing the tail node.

I'm going to use the same pseudo-code notation used in the paper, which is Pascal-based (it was 1991, give them a break), so the pointer notation may be unfamiliar to many readers.  I: ^qnode means, "the variable I has the type 'pointer to qnode'," and I^ means, "that which I points to."

compare_and_swap(addr, old, new) is defined as (atomically) if addr^ != old return false; addr^ := new; return true.  atomic_swap(addr, new) is defined as (atomically) old := addr^; addr^ := new; return old.

type QNode = record
  owner    : Boolean
  threadId : ThreadIdentifier
  next     : ^QNode

type lock = ^QNode    // locks start initialized to "nil" (the null pointer)

// The qnode I needs to be allocated in an outer scope

procedure acquire_lock (L : ^lock, I : ^qnode)
  I->threadId := myThreadId
  I->next     := nil
  predecessor : ^qnode := atomic_swap(L, I)
  if predecessor != nil                    // queue was non-empty
     I->owner := false
     predecessor->next := I                // put myself on the tail
     repeat sleep() while not I->owner

procedure release_lock (L : ^lock, I : ^qnode)
  if I->next == nil                        // no known successor
     if compare_and_swap(L, I, nil) return true  // L agrees that there's no successor
     else repeat (spin) while I->next == nil     // else spin wait for race to clear itself
  I->next->owner := true                   // there is a successor, wake it
  wake(I->next->threadId)

The only spinning is (1) in the (hopefully extremely rare) condition that the queue is empty except for the lock holder, and the lock holder tries to release at exactly the same time some other thread is trying to add itself to the queue or (2) when a thread waiting to acquire the lock receives a spurious wake up.

Condition Variable

Given a working mutex implementation with lock(m) and unlock(m), it is possible to do a relatively naïve but working implementation of a condition variable.  This design is based on

  Birrell, Andrew D; Impliementing Condition Variables with Semaphores, in Computer Systems, Theory, Technology, and Applications, Andrew Herbert and Karen Spärck Jones, editors, pp. 29-37, Springer Monographs in Computer Science, 2004.

and in particular, Birrell's advice that the condition variable should do the queueing itself, rather than relying on some other primitive.  Birrell's version additionally makes use of the observation that each thread can be waiting for at most one condition variable, so each qnode can be allocated as part of the thread control block when the thread is created.  (Which seems a bad idea to me, because then you have a dangling pointer when a thread gets killed while waiting for a condition variable.)

Start with a non-atomic queue of integers data type with push_tail(q, t) and pop_head(q)  and is_empty(q).

type CVar = record
  q : Queue
  qm : Mutex   // private mutex to protect the queue

// precondition: caller holds mutex m
procedure wait(cv : ^CVar, m : ^Mutex)
  lock(cv->qm)
  push_tail(cv->q, myThreadId)   // atomically add caller to the queue
  unlock(cv->qm)
  unlock(m)
  sleep()
  lock(m)

procedure signal(cv : ^CVar)
  lock(cv->qm)
  if not is_empty(cv->q)
    wake(pop_head(cv->q))
  unlock(cv->qm)

This implementation does suffer from spurious wakeups, but that's standard for condition variable implementations.  It is assumed that you are using condition variables to wait for some precondition (described by predicate P()) to become true and that you are thus using the condition variable like this:

m  : Mutex
cv : CVar

lock(m)
while not P()
  wait(cv, m)
// at this point P() is true and m is acquired


How to match two sets of points based on the closeset distance?

You have an instance of a bipartite matching problem. There are some variations on the problem. I think you're looking for a minimum cost bipartite matching, but maybe you're looking for a stable matching.


Problems showing the constraint of master theorem case three holds

The following shows that the second statement is false.

Define $f$ as follows:
$$ f(n) = \begin{cases} 4n^3 & n \text{ is a power of }4, \\ n^2 & \text{otherwise}. \end{cases} $$
Let $n = 2^{2k+1}$. Then $f(n) = n^2$ while
$$ T(n) \geq 2T(n/2) \geq 2f(n/2) = n^3. $$


Revert array shuffle faster than in O(n^2)

It's not very clear what you are asking. It seems you want to find the values of f(i) for all i.

Problem: You can't distinguish between f(0) = 1, f(1) = 0, and f(0) = 0, f(1) = 1.


Complexity of finding the pseudoinverse matrix

First of all, people tend to forget that $\omega$ is an infimum. Whenever we write $O(n^\omega)$, we actually mean for all $\gamma > \omega$, there is an algorithm running in time $O_\gamma(n^\gamma)$.

Keller-Gehrig showed (among else) how to present a matrix $A$ in rank normal form in time $O(n^\omega)$. If $A$ has rank $r$, then a rank normal form of $A$ is
$$ S \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} T $$
for some invertible $S,T$ of the appropriate dimensions; see also Algebraic Complexity Theory, Proposition 16.13 on page 435.

Rank normal form is similar to the rank decomposition mentioned in the Wikipedia article, $A = XY$ where $X$ has $r$ columns and $Y$ has $r$ rows. Indeed, we can take $X$ to be the first $r$ columns of $S$, and $Y$ to be the first $r$ rows of $T$. Given this decomposition, Wikipedia gives a formula for the pseudoinverse using only Hermitian adjoint, matrix multiplication and matrix inverse. Therefore the pseudoinverse can be computed in time $O(n^\omega)$.


Why is Big O not defined here for a hash table?

The chart is underspecified. I assume they mean by "Access" to "retrieve the $i$-th element¹.

In hashtables, there is no notion of order. While you could pick the $i$-th element in the underlying array, that would have no meaning at all. Hence, this operation does not make sense on hashtables -- n/a.

Which is of course underspecified or unfair, depending on how you look at it: in a BST, "Access" gives you also the $i$-th smallest element, whereas in a plain array you get just some element.


Is OS mode required for accessing general purpose registers

Computations on general-purpose registers ((a), (b), (d)) doesn't require any privileges.

Input/output requires privileges, to access a peripheral or to communicate with the part of the system that manages files. So (c) does generally require going to kernel mode. It's possible for some printf calls to remain entirely within the calling process, for example if output is buffered and the output of this call is going entirely inside the buffer. But in general a printf call does need to do actual I/O and thus does need a transition to kernel mode.

A processor does not really “have more than one process executing at the same time”. The processor alternates between executing different processes, but at a given point in time, it's only executing one process (or it's in kernel mode). On a multiprocessor machine, each processor¹ executes one process at a given time, but the different processors can be executing different processes. While a process is executing, it can access the general-purpose registers directly. It doesn't need the kernel for that. (And how would it ask the kernel, anyway? A process communicates with the kernel by placing the parameters of a system call in general-purpose registers and then invoking the system call instruction.)

Processes execute code as if the other processes didn't exist. When the kernel decides to switch to another process, it suspends the running process and unsuspends the process that it wants to run next. Part of this suspension mechanism is to save the values of the general-purpose registers into a dedicated memory area that belongs to the process that is being suspended. There is one such register store for each process². Part of the unsuspension mechanism is to restore the registers of the process that is being unsuspended. When a process is unsuspended, it keeps running where it left off, with the same values in registers as when it was suspended. This suspension/unsuspension mechanism is called a context switch.

A process never overwrites the registers used by another process because only the currently running process's register values are in the processor registers. The other processes' register values are in their register store. There has to be a context switch to change which process's register values are in the processor registers.

Switching between processes does not involve semaphores. It's the other way round: in order to use semaphores to synchronize between different processes, the processes need to call the kernel.

¹  Each core, each thread — whatever you call the single-threaded processing unit.
²  More generally, for each kernel thread.


Prove that 2-Colourability is in L from Undir-Reachability is in L

Hint: a graph is not bipartite if there is a walk of odd length from a vertex to itself.


Infinite languages and undecidable languages

The set $\{L' : L' \subseteq L\}$ is an uncountable set of languages, and since there is only countably many decidable languages, it has to contain an undecidable language. (You can get a concrete $L'$ by a diagonal argument.)


Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels?

No.  A complete binary tree has $\ell$ levels and about $2^\ell$ nodes.  Any algorithm must examine all nodes to get the correct answer, so the running time has to be exponential in the number of levels.
(A small note of caution: "polynomial time" typically means polynomial in the size of the input, so it could risk some confusion to talk about it as "polynomial time" when you mean a polynomial in the number of levels.)


What purpose do the leaves in a range trees serve?

The Range Tree is made from the input array. The array is sorted and then the tree is built. This means that in the standard construction we have started with the array, this may indicate the leaves. And this BST comes from the sorted array, so there is no point in changing it to e.g. self-balancing trees in the standard case and if there are modifications to the points, the self-balanced trees would perform worse (with very complicated implementation for rotations).

But the Range Tree can be more dimensional, them the leaves represent more dimensions, which leads to several decisions: are these actually pointers or integers (as in example)? Do we want to save memory? Are internal nodes used somewhere else to perform destructive operations?
If the footprint really matters, using integers is a good idea, if there are more dimensions or the integers are cheaper than pointers (to me integers are twice cheaper) this design would be better. So if you add pointers instead of the integers it gets heavier, also the ranges might be smaller, so the savings are bigger.

Also like Raphael pointed it looks like in-order traversal, so it may be right thread in the tree as well.

It may also be for illustratory purposes as you indicated.

Please take a look at the Range trees lecture from Marc ban Kreveld.


Application Ambiguity in Untyped Lambda Calculus

You can't evaluate (x t), where x is free, since evaluation ($\beta$-reduction) is usually defined in terms of substitution, but here you have neither a bound variable nor a function body for $t$ to be substituted into.

A term that cannot take a further step is called a normal form.


Why is it most efficient to resize a dynamic array to 2 * array.length()?

Consider a model in which elements are only added, one at a time, and once an array is full, it is increased in size by a factor of $C$. Suppose also that resizing an array of size $x$ costs $Cx$. Adding $N = C^n$ elements (the worst case in terms of resizing cost per element) has cost $C(1+C+C^2+\cdots+C^n) \approx \frac{C^2}{C-1} N$. The amortized cost of adding an element is thus $f(C) = \frac{C^2}{C-1}$. The derivative of this function is
$$
f'(C) = \frac{2C(C-1)-C^2}{(C-1)^2} = \frac{C(2-C)}{(C-1)^2},
$$
which vanishes at $C=2$. It is not hard to check that this is a minimum of $f(C)$.


Proving ambiguity of this Context Free Grammar

The string $ababab$ has two different parse trees. In one of them the first two $ab$'s are grouped together, and in the other one, the last two $ab$'s are grouped together.

Stated differently, one parse tree corresponds to a derivation $S \Rightarrow SS \Rightarrow^* ababS \Rightarrow^* ababab$, and the other one to a derivation $S \Rightarrow SS \Rightarrow^* Sabab \Rightarrow^* ababab$. If you draw the parse trees for both derivations, you'll see that you get different parse trees.

Finally, here are actual two different leftmost derivations of $ababab$:

$S \Rightarrow SS \Rightarrow SSS \Rightarrow TSS \Rightarrow abSS \Rightarrow abTS \Rightarrow ababS \Rightarrow ababT \Rightarrow ababab$.
$S \Rightarrow SS \Rightarrow TS \Rightarrow abS \Rightarrow abSS \Rightarrow abTS \Rightarrow ababS \Rightarrow ababT \Rightarrow ababab$.

As an aside, an equivalent unambiguous grammar replaces the production $S \to SS$ by the production $S \to ST$ (or by the production $S \to TS$).


Requiring at least one alldiff constraint to be satisfied converted to SAT

If you want to model an alldiff() constraint in SAT, there are several options.  Here are two different options you can try:

One way is to expand $\text{alldiff}(x_1,\dots,x_n)$ into $n(n-1)/2$ inequality constraints: $(x_1 \ne x_2) \land (x_1 \ne x_3) \land \cdots$.  Now you can express each inequality constraint $x_i \ne x_j$ on $b$-bit values in turn as a boolean formula: $(x_i[0] \ne x_j[0]) \lor (x_i[1] \ne x_j[1]) \lor \cdots$, where $x_i[k]$ is the $k$th bit of $x_i$.  In this way each alldiff constraint on $n$ $b$-bit variables expands into a boolean formula of size $\Theta(n^2 b)$.
Alternatively, a different way is to use a one-hot encoding.  Suppose each $x_i$ needs to take values from some universe $U$ of $u$ values.  Instead of encoding each $x_i$ as a $\lceil \lg u \rceil$-bit value, encode it as a $u$-bit boolean vector, where $x_i[k]=1$ if $x_i = k$ and $x_i[k]=0$ otherwise.  Now an alldiff constraint on $n$ variables amounts to requiring that there are exactly $n$ ones in the $nu$-bit vector obtained by concatenating the vectors for each of the $n$ variables in the alldiff constraint.  Thus, we obtain a $n$-out-of-$nu$ constraint.

This $n$-out-of-$nu$ constraint can be encoded in multiple ways; one way is to use a tree of half-adders  to sum up these values.  The tree will have $nu$ leaves, and with a $\lceil \lg nu \rceil$-bit output at the root.  You can find more about encoding cardinality constraints here: https://cs.stackexchange.com/a/6522/755.

These approaches give you a boolean formula, i.e., a boolean circuit; it's not in CNF form.  So, strictly speaking, it's not an instance of SAT.  However, there is a standard way to convert any such boolean formula to CNF form: you use the Tseitin transform (equivalently, you use the standard reduction from CircuitSAT to SAT) and then run a SAT solver on the result.  There are several SAT front-ends that will do this work for you; STP is one I have used that is quite convenient, but there are others as well.

This gives you at least options you could consider, for converting your problem to SAT.  Which one is most efficient might depend on your specific problem and the parameters of your problem (the size of the domain, the number of variables in each alldiff constraint).

Also, if you have a lot of alldiff constraints, it seems likely that a CSP solver might do better than a SAT solver.  CSP solvers are designed to handle alldiff constraints well, thus they might perform better than naively bitblasting to SAT, as SAT solvers won't be aware of that structure.

See also When to use SAT vs Constraint Satisfaction? and Converting (math) problems to SAT instances and https://cs.stackexchange.com/a/12153/755.


Is there a graph theory textbook that covers treewidth thoroughly?

I don't know if the thing you are looking for exists, but here are at least some pointers:
Parameterized Algorithms by Cygan et al (free PDF version) has a chapter dedicated on the topic.  This is slightly algorithms oriented, but contains structural stuff too.
Graph Theory by Diestel has one chapter, (12.  Minors, Trees and WQO) on the subject, about 40 pages.  homepage
Bodlaender has a chapter Treewidth of Graphs in the Encyclopedia of Algorithms.  homepage
Heggernes has a short compendium used for her advanced algorithms class Treewidth, partial $k$-trees, and chordal graphs.
You also have Ton Kloks' book, Treewidth springer, but it's getting rather old.  I have not read this one, so I don't know much about it.


Adding a character in the middle (rolling hash)

With just the Rolling HASH for the whole ABBDE, you can not insert into the middle of it.

But...
   as I understand rolling Hash...

If you are building the hashes up as you go (adding into the middle, adding other entries), you would need a little extra information to be able to insert into the middle at a latter access.

As I see it , You need  need to know:

A) The whole hash (I assume you got by finding the entry there)
B) The hash for one of the halves (Left or Right)
C) A length of the HALF to know the offset that needs to be adjusted by.
D) An indicator to know which half is being adjusted to keep the halves balanced.`

Then all the parts can be used to recalculate, updated, replaced, and inserted to make new entries.

This would then give an O(1) time

BTW,  what is this for?

The answer to another question with a related general solution:
Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation


Approximating longest path on graphs with average degree n/2

Here is something to get you started.
Suppose that your graph were $n/2$-regular, and consider the following algorithm. Start at an arbitrary vertex $v_1$. Choose one of its $n/2$ neighbors $v_2$. Choose one of $v_2$'s $n/2$ neighbors $v_3 \neq v_1$. And so on. The process will continue for at least $n/2+1$ steps. Since every path has length at most $n$, this gives a $1/2$ approximation. In fact, this would work even if the minimal degree were at least $n/2$.


The chess board problem is, although complex, a finite problem. Specifically, the number of moves, starting from any board position, is finite.

Then, a TM can just go over all the possible moves (there are only $C$ such moves, for some "small" constant $C$), and verify if a certain position is feasible continuation of a prior position. Hence, any such question is decidable.


Hint: suppose that we are able to solve your problem efficiently. Then what if we take an arbitrary subset sum problem and multiply all elements by $2$, as well as the target?


Are regular languages closed under inverse homomorphism?

Yes, regular languages are closed under inverse homomorphism.

Here is a proof.
We start with a DFA of $L$, $X$. To prove that $\varphi^{-1}(L)$  is regular, we will construct a DFA, $Y$ for $\varphi^{-1}(L)$.

$$ X = (Q,\Sigma,\delta_X,q_0,F)$$

So our construction will be as follows:

$$ Y = (Q,\Delta,\delta_Y,q_0,F)$$

Where:

$$\delta_Y(q,w) = \hat{\delta_X}(q,\varphi(w))$$

Or in other words, the transition in Y on w is the result of the sequences of transition that X makes on the string of symbols $\varphi(w)$. So all we need to do now is prove this transition. To do this we will induct on $|w|$. Our hypothesis being $\hat{\delta_Y}(q,w) = \hat{\delta_X}(q,\varphi(w))$.

Base: When $w = \epsilon$:

$$q_0 = \delta_Y(q_0,\epsilon) = \delta_X(q_0,\varphi(\epsilon)) = \delta_X(q_0,\epsilon) = q_0$$

Inductive Step: First let $w = \sigma s$:

$$\hat{\delta_Y}(q_0,w) = \hat{\delta_Y}(\delta_Y(q_0,\sigma),s)$$

Then by our inductive hypothesis:

$$\hat{\delta_Y}(\delta_Y(q_0,\sigma),s) = \hat{\delta_Y}(\delta_X(q_0,\varphi(\sigma)),s)$$

Now by our DFA definition above:

$$\hat{\delta_Y}(\delta_X(q_0,\varphi(\sigma)),s) = \hat{\delta_X}(\delta_X(q_0,\varphi(\sigma)),\varphi(s))$$

Pulling the $\delta$ back in:

$$\hat{\delta_X}(\delta_X(q_0,\varphi(\sigma)),\varphi(s)) = \hat{\delta_X}(q_0,\varphi(\sigma)\varphi(s))$$

Now by the definition of homomorphism:

$$\hat{\delta_X}(q_0,\varphi(\sigma)\varphi(s)) = \hat{\delta_X}(q_0,\varphi(\sigma s)) = \hat{\delta_X}(q_0,\varphi(w))$$


The edge from $2$ to $3$ isn't part of the minimum cut. It's oriented in the wrong direction, from the sink side to the source side, so you can delete it from your cut and there's still no path from $s$ to $t$.


Remember, big-O is essentially an upper bound so we do have
$$
n! = O(n^n)
$$
in the sense that there is a constant $c$ for which $n!\le c\;n^n$ eventually. [Note, by the way, that there's no function $T(\cdot)$ involved here.]

Now let's see if $n!=O(2^{n\log n})$. We can argue this way (assuming the log is base-2):
$$
2^{n\log n} = 2^{(\log n) n} = \left(2^{\log n}\right)^n = n^n
$$
so we can conclude that the two sets $O(n^n)$ and $O(2^{n\log n})$ are in fact equal.


Finding the longest common subsequence algorithm using hash table Slow

One optimization is to replace the access to reached_index[item] by a local variable which is initialized from the hash table at the beginning of the for item loop, and stored back to the hash table at the end of the loop.

Another optimization which will speed up things is to replace the hash tables with arrays of size 256.


Reccurrence equation and finding suitable algorithm

1) It doesn't mean anything, for two reasons:

First of all, it's important to distinguish between an algorithm vs the running time of an algorithm.  $T(\cdot)$ is not an algorithm; it's a function.  For instance, $T(n)$ might be the running time of a computer program, as a function of the size of its input, but it's not the program itself.  Anyway, $T(n)$ is just a mathematical function: if it is intended to represent the running time of some algorithm, that should be stated explicitly.
Second, every algorithm needs to take at least at least one step, so the running time always has to be at least one: it can never be zero.  Therefore, it doesn't make sense to have a running time of zero.  This might be a bit of a quibble/nitpick.

2) I suggest you do a bit more practice with the reverse: given a simple algorithm, work out a recurrence relation for its running time.  Once you feel like you're able to do that confidently, you'll probably find this exercise easy.

See also our reference question, How to come up with the runtime of algorithms?.  There's also a more advanced, sophisticated treatment at Is there a system behind the magic of algorithm analysis?.


Difficulty understanding the solution of heap problem in CLRS book?

But I don't understand the how to come up with the fact that $(k−1)2^h+k(2^{h−1}+1)$ is less than the number of leaves.

It is quite straightforward from the very first statement of the solution which says there are all but one set of size $2^{h}$. Where $k$ is total number of sets of nodes at height $h$.

Therefore, total number of nodes at $h$ height is:
$$\begin{align*}
s &= (\text{total sets} \times \text{size of each sets})\\
 &= k(2^{h}+2^{h-1}+1)-1 \cdot 2^{h}\\
 &= (k−1)2^h+k(2^{h−1}+1)
\end{align*}$$

Another way to solve this is here.


Finding a specific "balls-into-bins" partition given its index in the lexicographical ordering

The procedure of generating the $i$-th structure according to some ordering of a combinatorial class is called unranking.

In your specific case an unranking algorithm for $P_{n,k}(i)$ can be created as follows:

Define $s_m := \sum_{j=0}^m |P_{n-j,k-1}|$, the number of vectors that start with $m$ or a smaller number, $s_{-1}=0$.

If $k=1$, the vector contains the single entry $n$.
Otherwise,

The first entry in the vector is $m$ so that $s_{m-1} < i \le s_m$.
The remaining vector is $P_{n-m,k-1}(i-s_{m-1})$.


How does Grover's Quantum Sorting avoid reading the list?

The list (or database) is given implicitly by an "oracle" function, which is called $\Theta(\sqrt{N})$ times throughout the algorithm. Suppose for example you're looking for a divisor of some number $N$. Then the function could map $k \leq \sqrt{N}$ to true if $k$ is a non-trivial divisor of $N$, and false otherwise. Grover's algorithm will then find a non-trivial divisor of $N$ in time $\tilde{O}(\sqrt[4]{N})$ instead of the usual $\tilde{O}(\sqrt{N})$ (note that better algorithms are available in this case, even for a classical computer).


Find a recurrence relation for merging of sublists of an array

The mistake is when converting $O(n)$ to $O(2^m)$, and then varying $m$. In fact, $n$ is constant here and $m$ changes. So the recurrence relation is $T(m) = T(m/2) + O(n)$, whose solution is $T(m) = O(n\log m)$. Substituting $m = \log n$, we obtain $O(n\log\log n)$.


Which pretrained model will be best for my dataset?

There's no general answer.  In this field, you'll just have to try multiple approaches and see how well they work.  We usually won't know what will work best until we try it.
I can suggest three candidate approaches:

Get more data.

Use a pre-trained model and fine-tune it.  You can use any state-of-the-art model, pick a version that was pre-trained on ImageNet, and then fine-tune it (either fixing the first n-1 layers and training only the last layer; or training all layers, but with a smaller step size).

Use few-shot learning.  This will probably require more sophisticated methods and more study.

Aggressive data augmentation might be useful.


Is there an affordable experiment which shows chips can't get much smaller?

I think you are right that the Heisenberg uncertainty principle is involved in the limit.  I don't think we are anywhere near the Heisenberg limit.  The limit we are currently approaching is that we currently compute with devices based on atoms.  An atom is about 1 angstrom = .1 nm wide.  We are currently making transistors that are about 22 nm wide, so we're getting close to needing to make 1 atom transistors.  If we want to scale beyond that we're going to need to find ways of computing that involve storing and manipulating multiple states per atom.

The wikipedia article on fundamental limits of computation is a good starting point.  I think what you really want is the Bekenstein bound.

The researchers that I know of in this area are Rolf Landauer, Charles H Bennett, and Seth Lloyd.  (I think Charles H Bennett considers himself a computer scientist while the other two consider themselves physicists.)  Richard Feynman was also very interested in this question and has a book called Feynman Lectures on Computation (which you can read about at http://quantum.quniverse.sk/buzek/zaujimave/p257_s.pdf).  Also @PeterShor is an active member here and is the expert on quantum computation.

Here's a Scientific American article by Bennett and Landauer:

http://web.eecs.umich.edu/~taustin/EECS598-HIC/public/Physical-Limits.pdf

Here's Seth Lloyd's article in Nature: http://arxiv.org/abs/quant-ph/9908043

Here's a web page at Cambridge: http://www.sp.phy.cam.ac.uk/~SiGe/Fundamental%20Limits%20of%20Computation%20-%20Landauer%20and%20Heisenburg.html


An advice to a self-learner of computational complexity

My recommendation is to focus on two things: prerequisites, and practice.

Prerequisites: It's going to be harder to learn computational complexity without first having a good understanding of algorithms.  At many schools, a class in algorithms is a prerequisite to the class on computational complexity.  You mention you feel you may lack maturity in algorithms, and in your position, who wouldn't?  It's a non-trivial subject that you haven't studied.  So, my first piece of advice is: before spending too much time on computational complexity, first spend some time studying algorithms.  There are many good algorithms textbooks and online courses (e.g., via Udacity, Coursera, or EdX).  It might be helpful to spend some time learning that material.  You don't need to learn every algorithm in the world, but try to get a feel for some common algorithmic techniques; designing reductions is basically designing an algorithm, so this knowledge will be helpful.  Also, make especially sure you are comfortable with proofs of correctness for algorithms and asymptotic running time analysis.

Next, practice.  No one starts out with a maturity with reductions.  The way to get more comfortable with that is to practice -- do exercises until you either feel comfortable with the material, or the exercises uncover some gap in your understanding (which you can then go back and focus on learning more about).  You probably can't learn the material without this kind of practice.

To help you practice, it may be helpful to look for an online course (a MOOC) on computational complexity.  You can check Udacity, Coursera, or EdX.

How rigorous should you be?  Rigorous enough that you are convinced that you could fill in all the details if you needed to (and that a fellow classmate at a similar level of studies could fill in all the details without thinking hard -- they'd agree filling in the details is tedious but straightforward and obvious).


How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

Here is my approach: I'll show that if you can decide your problem, then you can decide Post's correspondence problem (PCP), which is known to be not decidable.

Remember, PCP is a decision problem that asks if in a set of $2$-tuples $P=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ you can build a sequence (incl. repetition) such that the concatenated $x_i$s and the concatenated $y_i$s of this sequence form the same word. Notice that the alphabet has to have at least 2 characters.

So, let $P$ be an instance of the PCP.
Consider the following context-free grammar, where we've introduced a new terminal symbol $t_i$ for the $i$-th element in $P$. The grammar has the following rules:
$$
\begin{align}
S& \to X \; ! \;Y \\
X& \to x_1 X' t_1 \mid x_2 X' t_2 \mid  \cdots  x_n X' t_n \\
X'& \to x_1 X' t_1 \mid x_2 X' t_2 \mid  \cdots  x_n X' t_n \mid \varepsilon\\
Y& \to y_1 Y t_1 \mid y_2 Y t_2 \mid  \cdots  y_n Y t_n \mid \varepsilon \\
\end{align}
$$
(The variable $X'$ is only there to rule out $S\Rightarrow !$).

Of course, given any grammar, we can find a corresponding PDA that accepts the same language as the grammar.  So, construct the corresponding PDA, and then use the hypothetical algorithm for your problem to determine whether this PDA accepts any word of the form $u!v$ (i.e., whether one can derive any word of the form $u!v$ from this grammar).  I will show how to use this information to solve the PCP instance $P$.

Assume now that $u!v$ is a word in this grammar.
The word $u$ has two parts, the suffix, consisting of the $t_i$ terminals, and the remainder called prefix.  The same is true of $v$.
We have $u=v$ if and only if their prefixes and suffixes coincide. The suffixes coincide only if we have used the same sequence of tuples from $P$ to built the words $u$ and $v$. The prefixes of $u$ and $v$ coincide if the concatenation of the $x_i$s and $y_i$s (based on the reversed tuple-sequence given by the $t_i$s) is the same. Hence $u=v$ if and only if there is a solution for the PCP instance $P$.

Similarly, if there is a solution for the PCP instance $P$, then from the solution it is easy to construct a word of the form $u!v$ that is derivable from this grammar.

It follows that the PCP instance $P$ has a solution if and only if this grammar contains a word of the form $u!v$.  If there was an algorithm to decide your problem, we could use it to solve PCP.  But of course PCP is known to be undecidable, so your problem is undecidable, too.


Quality LISP/Scheme compilers to compete with C/C++

As noted in the comments, it isn't very exact to state "the current crop of compilers (Bigloo, SBCL, Gambit, Chicken, etc) are 20-50 times slower than equivalent C code", without qualifying how you tested and what you tested.

For my use, I find that for many things Gambit and Chicken Scheme are quite close to the equivalent 'C' code in speed, with the current version of Gambit (4.7.3) generally faster than Chicken (4.9.0.1) but over pre-optimizing the output 'C' code (making assumptions about the number of available registers - assumes x686 - and forcing the use of stack memory for any extra memory requirements, which decisions should be left to the 'C' compiler as Chicken does, which often eliminates the requirement for extra registers and combines processing steps) so as to prevent the 'C' compiler from doing its own optimizations resulting in very tight small loops being up to about twice as slow as those same tight small loops in 'C' (or Chicken); Chicken just defines as many variables local to a given function as it sees fit (mostly used immutably) and then depends on the compiler to optimize most of those away.  Chicken doesn't seem to optimize Continuation Passing Style (CPS) algorithms with multiple forked levels of continuations as well as Gambit and can be up to about eight times slower than Gambit for these, but then one thinks that CPS isn't really formalized for 'C' code at all so...

EDIT_ADD:  I have done some more research into the Chicken and Gambit-C Scheme versions and have found the following:

Chicken is faster than Gambit for small tight loops for the above reason (depends more on the 'C' compiler for optimizations without doing as much itself and thus takes better advantage of x86-64 extra registers), but also because it doesn't include a "POLL" stack maintenance check inside the loops, whereas Gambit includes the "POLL" check inside the loop.  Even when this isn't triggered (the usual case), it will take several CPU clock cycles to determine that nothing is required (about 6 cycles).  A future smarter compiler might see that there is no need to do a stack check when inside a tight loop and not doing stack-building operations, doing it just before or after the loop and save this time.
Gambit's 'C' macro's do too much work, as said, in precisely defining how the operations should be carried out, especially including fixed stack size operations, and these are likely harder for the 'C' compiler to optimize; using registers more effectively could reduce tight loop time by perhaps 4 cycles, which in combination with the above would put it into the Chicken ballpark.
Neither output "read/modify/write" optimizations for say vector operations that are modify in place and don't output code so that the compiler does it.  A smarter backend such as LLVM when used with Haskell does this kind of thing.  This would reduce register use by one and execution time in using only a single instruction rather than a separate read, computation of the modification, and a write to the same location; this would become just a calculation of the modification (say a bit or), and then a read modify (|=) write single instruction.  This might make the speed faster by a cycle or so
Both are dynamically typed and process data "tag" bits as part of their data.  Neither are smart enough for tight loops to reduce the tags, perform the loop "tag-less", then add the tags back for any results from the loop, nor do they produce code where the 'C' compiler can see to do this although it does combine these operations for some cases.  Optimization here could reduce loop times by a couple of CPU cycles or so, depending on the loop.
Very tight 'C' loops can take about 3.5 CPU clock cycles per loop on a fast CPU that isn't memory cache access speed throttled (such as AMD Bulldozer, which is about twice as slow); the same loop in Chicken currently takes about 6 cycles and Gambit takes about 16.9 cycles.  With all of the optimizations as per the above, there is no reason that these implementations of Scheme couldn't do that, however some work is required:
In the case of Gambit, the harder work might be improving the flow analysis to recognize when no "POLL" tests need to be inserted (ie. could this be interrupt driven, although the compiler does allow interrupts to be turned off for some uses?); the easier improvement would be to just implement better register usage (ie. recognize x86-64 registers better rather than the default x686 architecture).  For both, better flow analysis to recognize that they can "untag" the data, especially "fixnum", "flonum", and vector, data so these operations aren't necessary inside tight loops and combining read/modify/write instructions. Both of these ends could be accomplished by using a better backend such as LLVM (not a trivial amount of work, but both are already partly there).

Conclusion: Chicken is currently about 50% slower than 'C' on the fastest CPU's (not my Bulldozer, where it is about the same speed due to cache throttling of the 'C' code) and Gambit is about 400% slower (only about 125% slower on my slow Bulldozer).  However, future improvements to the compilers could reduce this so that either code is no slower than 'C' or within the margin that the OP specifies.

A more complex language such as Haskell, when using the LLVM backend, paying careful attention to strictness use (not a problem with scheme which is always eager by default), and using appropriate data structures (ST unboxed arrays rather than lists for tight loops; somewhat applicable to Scheme using vectors), runs at about the same speed as 'C' if the LLVM backend is used with full optimizations.  If it can do this, so can Scheme with the above compiler improvements.

AGAIN, there is no way that either of these is 20 to 50 times as slow when used with proper optimization flags.  END_EDIT_ADD

Of course, all benchmarks are invalidated if one does not use the appropriate optimization settings for each as one would in a production environment...

I would think that the commercial Chez Scheme compiler would be in the ballpark as to producing high performance output as do Gambit and Chicken, as being commercial it surely has some "serious time and money invested into it".

The only way I can get Gambit or Chicken to run as slow as "20 to 50 times slower than 'C'" is to not use any optimization settings, in which case they often don't run much faster than as interpreted in their REPL's - 10's of times slower than as properly using those settings.

Is it possible that the OP hasn't tested using these settings properly?

If the OP cares to clarify his testing procedures, I will gladly edit this answer to show that at least Gambit and Chicken don't have to be that slow.


Difference between equivalence and implication

First, to answer the question in your question title: the difference between equivalence and implication in CTL formulae is the same as the difference between equivalence and implication in propositional logic, that is, $A \leftrightarrow B$ is the same $(A \to B) \land (B \to A)$.

But your real question is whether $\mathrm{AG}\,(A \land B)$ is equivalent to $\mathrm{AG} \,A \land \mathrm{AG}\,B$. To solve this question, you have to look at the semantics of the operators AG and $\land$; that is, what do $\mathrm{AG}\,\phi$ and $\psi_1\land\psi_2$ mean (for arbitrary formulas $\phi,\psi_1,\psi_2$?

The semantics of CTL works via transition systems. Two formula are equivalent if they are true in exactly the same transition systems and states. Looking at the semantics of AG and $\land$, it should be fairly easy to decide whether there is a transition system where the one formula is true and the other isn't.


Find a particular connected graph within a complete graph keeping all vertices

Clearly you can focus on trees, since removing edges can only reduce the weight of the maximal edge. What you're looking for is called a minimum bottleneck spanning tree, and an MST is also a minimum bottleneck spanning tree.

To see why, suppose for the purpose of contradiction that $T$ is an MST which does not minmize the maximum weight. Let $(u,v)$ be the maximal weight edge in $T$, and $T'$ be a minimum bottleneck spanning tree. By our assumption $(u,v)\notin T'$, hence there exists a path from $u$ to $v$ in $T'$ which does not contain $(u,v)$, let us denote this path by $P$. Note that all the edges in $P$ are lighter than $(u,v)$. Remove $(u,v)$ from $T$, now $u,v$ are in different connected components. Suppose $P=(w_1=u,...,w_k=v)$, and denote by $i$ the minimal index such that $w_i$ and $w_{i+1}$ are in different connected components in $T\setminus\{(u,v)\}$. Now, $\left(T\setminus\{(u,v)\}\right)\cup\{(w_i,w_{i+1})\}$ is a spanning tree of $G$ with smaller weight, contradicting the fact that $T$ is an MST.


number of queries to recover the permutation

Suppose that my input is some permutation $\sigma$. Applying $f$ is the same as multiplying by $f$ from the left (assuming that $\alpha\beta(i) = \alpha(\beta(i))$, and then applying $p$ is the same as multiplying by $p$ from the right. In other words, we have an oracle for the function $\sigma \mapsto f\sigma p$.

Given $f\sigma p$ and $f\tau p$, we can find $(f\sigma p)^{-1} (f \tau p) = p^{-1} (\sigma^{-1} \tau) p$. In particular, using two oracle calls we can find $p^{-1} (1\;2\;3\;\cdots\;n) p = (p^{-1}(1)\;p^{-1}(2)\;p^{-1}(3)\;\cdots\;p^{-1}(n))$. Using one more oracle call, we can also find $(p^{-1}(2)\;p^{-1}(1)\;p^{-1}(3)\;\cdots\;p^{-1}(n))$ (the only difference is the first two values). From these two long cycles we can locate $p^{-1}(1)$ and so recover $p^{-1}$ (and so $p$), as well as $f$ if we so wish. In total, we used three oracle calls.


Clustering Application with a Huge Number of Clusters

In `Learning Feature Representations with K-means' [1] the authors apply unsupervised learning, i.e., k-means to learn 256 features (centroids, centers).
They also claim that the huge number of centers, in this case, k=256 is a limitation to this approach.
p[11]:
``Indeed, it is frequently best to set k as large as compute resources will
allow, considering data requirements. Though performance typically asymptotes
as k becomes extremely large, increasing the size of k is a very effective way
to squeeze out a bit of extra performance from an already-built system''
[1] https://www-cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf


Is the minimal number of colors needed to color a graph some fixed number?

The problem is always in $\Delta_2 = \Sigma_2 \cap \Pi_2$, as you mention. For some values of 2015 it is easier: deciding whether a graph has chromatic number 3 is NP-complete, and deciding whether a graph has chromatic number 2 or 1 is in P (since you can check whether a graph is bipartite in polytime).

Since deciding whether a graph has chromatic number 3 is NP-hard, so is deciding whether it has chromatic number 2015, by reduction: add a clique of size 2012, and connect it to all vertices; this increases the chromatic number by exactly 2012. So there is no hope for a polynomial time algorithm.


Show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem on $n$ points?

We may reason in a combinatorial way.

There are $n!$ permutations of $n$ nodes, but that overcounts the number of tours in two different ways. Since tours are closed, we may start indifferently on any of the $n$ nodes, and we may choose the direction in $2$ ways. Therefore, each tour was counted a total of $2n$ times.

This yields the desired result.


Prove that in a tree where each node has 0 or 2 children, number of nodes with 0 child is one more than the number of nodes with 2 children

This can be proven by induction. What you describe is a Full binary tree, and it has a convenient induction definition:

a single node (or leaf) is a full binary tree;
a tree with two children that are full binary trees is a full binary tree.

This permits a structural induction proof of the property you want:

prove that it is true for a single node tree;
suppose that it is true for two full binary trees $a$, $b$, then prove that it is true for the node $N(a, b)$ with $a$ and $b$ as children.


How to test implementation details when there are multiple ways of implementing the algorithm, without reading the code?

To find out if it is e.g. doing binary search (or using hashing, or whatever) inside, you have to look at what it is doing. No way around it.

Why would you insist on a particular algorithm? The whole point of modularity (and thus of much of modern programming languages and techniques) is to be able to hide such irrelevant details, and have users depend only on observable behaviour (so you can go back tomorrow and replace a simple, inefficient algorithm by a complex, efficient one, and noone is the wiser).


Instead of cutting corners and jumping right in to a reduction, I believe you would profit from actually stepping back and clarifying the logical basis of your argument.

Given an instance $(G, s, t)$ of HAMPATH, your reduction produces an instance $(G', s')$ of HAMCYCLE, as you have described. To prove your reduction works, you need to show:
$$(G, s, t) \in \textsf{HAMPATH} \iff (G', s') \in \textsf{HAMCYCLE}$$
for every instance $(G, s, t)$ of HAMPATH, where $(G', s')$ is uniquely determined as a function of $(G, s, t)$ (the function in case being your reduction).

To prove this equivalence, you first fix an arbitrary instance $(G, s, t)$ of HAMPATH (which may be a "yes" or a "no" instance). $(G', s')$ is then uniquely determined by $(G, s, t)$. Then, you either prove the two sides of the equivalence (as you have done) or show that, if $(G, s, t)$ is a "yes" instance, then $(G', s')$ is a "yes" instance and, if $(G, s, t)$ is a "no" instance, then $(G', s')$ is a "no" instance. Although usually the latter is preferred, either is fine; you can reference all of $G$, $s$, $t$, $G'$, and $s'$ in both cases since they are all fixed.

The problem with your argument is that you obtain a cycle $(s, \dots, s)$ and then (correctly) reason there is a node $t'$ right before $s$ which makes it a Hamiltonian cycle (and gives you a Hamiltonian path from $s$ to $t'$). However, because $t$ is fixed, there is no guarantee that $t' = t$. You still need to consider the case $t' \neq t$ and show this gives you a Hamiltonian path from $s$ to $t$ even if you delete the edge $(t, s)$ (since this yields $G$ from $G'$).

Unfortunately, you will not be able to. Consider, for instance, the case where $G$ is a cycle $(s, t, v, s)$. Then both $G$ and $G'$ obviously have a Hamiltonian cycle which starts and ends at $s$, but there is no Hamiltonian path from $s$ to $t$ in $G$; the only way to reach $t$ from $s$ (by a path) is the single edge $(s, t)$, which fails to visit the vertex $v$.

You will have to modify your reduction. Hint: Try to find a way of forcing $G$ to not have a Hamiltonian cycle in the first place (and note this implies $t' = t$ above).


The order of which time complexity is higher, 3 ^ log(n) or n ^ 3?

The answer easily follows from the identity $3^{\log n} = n^{\log 3}$. Whether or not $\log 3 < 3$ depends on the basis of the logarithm.


Is this lambda abstraction created as a generator of a recursive function?

If you look at the $Z$ combinator (because we're in an eager context), you have $$Z=\lambda g.(\lambda f.g(\lambda v.ffv))(\lambda f.g(\lambda v.ffv))$$

If you look at the code, we don't apply a fixed point combinator to sum, we simply apply sum to itself, so there's no reason for sum to be "generator".

You can also readily show that sum is (modulo currying) equal to $\lambda f.g(\lambda v.ffv)$ for some $g$, basically by replacing (f f ...) with (h ...) where h is the argument to $g$ in the definition for sum (minus the outermost lambda).


Proving following regular expressions equal to one another?

Convert both regular expressions to a DFA, compute the symmetric difference of the two DFA's using a product construction, and then check whether the result accept the non-empty language.  Each of those steps is described here on this site.  See also Does this regular expression equal this automata? for a very similar question.


The notation $S\to(L)|a$ is shorthand to $S\to(L)$ and $S\to a$, so you can rewrite the grammar in your equivalent form; I don't see how this makes things any different, since the two grammars are exactly the same.

The first step in writing a parse tree is coming up with a derivation. In the derivation below, I use boldface to indicate the non-terminal being expanded.
$$
\begin{align*}
\mathbf{S}&\to(\mathbf{L}) \\ &\to(\mathbf{L},S) \\ &\to (\mathbf{S},S) \\ &\to (a,\mathbf{S}) \\ &\to (a,(\mathbf{L})) \\ &\to (a,(\mathbf{L},S)) \\ &\to (a,(\mathbf{S},S)) \\ &\to (a,(a,\mathbf{S})) \\ &\to (a,(a,a))
\end{align*}
$$
There are several different derivations which "feel" the same. For example, in this derivation I always expanded the left-most non-terminal, but you could just as well expand any other non-terminal. When you draw the derivation tree, all these derivations give rise to the same tree.

Here is the actual derivation tree, drawn by Rick Decker:


Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not

You are not starting with the right proof idea. It's this:

I want to show $L$ is not regular.
Assume towards a contradiction that $L$ is regular.
Since REG is closed against $f$, I conclude that $L' = f(L)$ is also regular.
But I already know that $L'$ is not regular (from elsewhere). Contradiction; $L$ can't be regular.

See here for complete examples.


Time complexity of minimizing Boolean expression

The Wikipedia article states that the problem is $\Sigma_2^P$-hard, and in particular it's NP-hard. Therefore it's probably not solvable in polynomial time (unless P=NP).


Solving $$f(x, k) = f(x, k-1) + f(x-1, k-1) + \dots + f(1, k-1)$$ in terms of $x$

The answers to all three questions become easier once we proved the following formula for all positive integer $k$ and $x$.
$$ f(x,k) = \frac{x(x+1)(x+2)\cdots(x+k-1)}{k!}$$
Proof: The formula is easily seen to be true for $k=1$ and all positive integer $x$.

Assume the formula is true for some positive integer $k$ and all positive integer $x$.
Then,
$$\begin{align}
 &f(x, k+1)\\
&=f(x, k) + f(x-1, k) + f(x-2, k) + \dots + f(1, k)\\
&=\frac1{k!}(x(x+1)(x+2)\cdots(x+k-1) + (x-1)x(x+1)(x+2)\cdots(x+k-2)\\
&\quad\quad+\cdots+1\cdot2\cdots k\\
&=\frac1{k!}\left(\frac{x(x+1)(x+2)\cdots(x+k)-(x-1)x(x+1)\cdots(x+k-1)}{k+1}\right.\\
&\quad\quad+\frac{(x-1)x(x+1)\cdots(x+k-1)-(x-2)(x-1)x\cdots(x+k-2)}{k+1}\\
&\quad\quad+\cdots\\
&\quad\quad+\frac{2\cdot3\cdots(k+1)-1\cdot2\cdots k}{k+1}\\
&\quad\quad+\left.\frac{1\cdot2\cdots k}{k+1}\right)\\
&=\frac1{k!}\frac{x(x+1)(x+2)\cdots(x+k)}{k+1}\\
&=\frac{x(x+1)(x+2)\cdots(x+(k+1)-1)}{(k+1)!}\end{align}$$

By mathematical induction on $k$, the formula is true for all positive integer $k$ and $x$.

Here are the answers to your three cases.

1) For fixed $k$ and $x\to\infty$,
$$f(x,k)=\frac{x^k}{k!}\frac xx\frac{x+1}x\cdots\frac{x+k-1}{x}\sim\frac{x^k}{k!}$$
That is, $f(x,k)=\Omega(x^k)$.

2) For fixed $x$ and $k\to\infty$, by Stirling's approximation,
$$\begin{align}f(x,k)&=\frac{(x-1+k)!}{(x-1)!k!}\\
&\sim\frac1{(x-1)!}\frac{\sqrt{2\pi(x-1+k)}\left(\frac{x-1+k}{e}\right)^{x-1+k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}\\
&=\frac1{(x-1)!}\sqrt\frac{x-1+k}k
(x-1+k)^{x-1}\left(\frac{x-1+k}{k}\right)^k\frac{1}{e^{x-1}}\\
&=\frac1{(x-1)!}\sqrt\frac{x-1+k}k\left(\frac{x-1+k}{k}\right)^{x-1}k^{x-1}\left(1+\frac{1}{\frac k{x-1}}\right)^{\frac k{x-1}(x-1)}\frac{1}{e^{x-1}}\\
&\sim\frac1{(x-1)!}k^{x-1}e^{x-1}\frac{1}{e^{x-1}}\\
&=\frac{k^{x-1}}{(x-1)!}\end{align}$$
That is, $f(x,k)=\Omega(k^{x-1})$

3) Let $k=x-1$ go to infinity, again by Stirling's approximation,
$$f(x,k) = \frac{(2k)!}{k!k!}\sim \frac{\sqrt{2\pi2k}\left(\frac{2k}{e}\right)^{2k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}=\frac{2^{2k}}{\sqrt{\pi k}}$$
That is, $f(k+1,k)=\Omega(k^{-1/2}2^{2k})$.


How does Gradient Descent treat multiple features?

That's correct.  The derivative of $x_2$ with respect to $x_1$ is 0.
A little context: with words like derivative and slope, you are describing how gradient descent works in one dimension (with only one feature / one value to optimize).  In multiple dimensions (multiple features / multiple variables you are trying to optimize), we use the gradient and update all of the variables in each step.  That said, yes, this is basically equivalent to separately updating each variable in the one-dimensional way that you describe.


Classes and Algebras: Which begat which?

I'm not sure I fully understand your question, but I think you noticed that algebras (or more precisely algebraic signatures) and classes share a feature, namely that they both can be seen as specifying a bunch of operations. For example the algebraic construct group has three operations: multiplication, inverse and the constant $1$. Now you ask if algebras can be used to model classes.

The answer is negative at this point. Classes in the sense of OO programming are complicated beasts. They have features that algebras don't have, in particular computational dynamics. There are other features like inheritance, method overriding, mutable private members that also
don't lend themselves to easy algebraic description. For this reason, purely algebraic sematics of OO languages don't exist.

As to the historic question, I don't know. The development of types goes back to the end of the 19th century, a time when abstract algebra was in nascent form too


Is there an adjustment for Adler32 algorithm so it works well on short messages?

In [1], the authors show that for 1500 bytes, the chance of an undetected collision with Adler32 is less than one in 100 billion.

In that paper, see Figure 13 which states:

  Comparison of 8-, 16-, and 32-bit Fletcher and Adler checksums using random data at a BER of 10-5. The data point values are the mean of 10 trials.

And shows probability of undetected error using Adler32 to below 10-11 for a 1500 byte message.

Therefore, as D.W. suggested above, no adjustment is needed.

[1] Maxino, Theresa C., and Philip J. Koopman. "The effectiveness of checksums for embedded control networks." Dependable and Secure Computing, IEEE Transactions on 6.1 (2009): 59-72.


Lower bound on the number of comparisons needed for finding the two largest elements

With impossibility proofs, you don’t control the algorithm; you control
the input. For this particular impossibility proof, the input is the
outcome of the comparisons that the algorithm performs. Here’s one
possible adversary strategy.

This adversary never claims that elements in distinct positions are
equal. At each point in the algorithm’s execution, there are two classes
of elements: candidates, which are the elements that have not compared
less than another element; and non-candidates, which are the remaining
elements. Candidates always compare greater than non-candidates.
Non-candidates compare in an arbitrary consistent way. Comparisons
between candidates can be resolved arbitrarily (prove this); the
adversary declares the candidate involved in more previous comparisons
of this sort (“knockout” comparisons) to be greater.

At the end of the execution, there can be only one candidate; otherwise,
the algorithm can’t know which of the candidates is the maximum (prove
this). The only way to reduce the number of candidates is a knockout comparison, which reduces the number of candidates by one. This implies that there are
n - 1 knockout comparisons, forming a tournament tree of some
shape. We observe that, for each node of the tree, when an element
secures its place there, it has participated in a number of knockout
comparisons equal to the height of that node. The root has height at
least lg n, so it takes lg n - 1 comparisons to determine which of the
lg n elements compared less than the maximum only (otherwise, the second
maximum isn’t known). None of these comparisons are knockouts, so the total is at least n + lg n - 2.


Recurrence relation for time complexity $T(n) = T(n-1) + n^2$

Just continue your reasoning as follows.

\begin{eqnarray}
T(n) &=& T(n-1) + cn^2 \\
&=& T(n-2) + c(n-1)^2 + cn^2 \\
&=& \ldots \\
&=& T(n-n) + c(1^2) + c(2^2) + \ldots cn^2 \\
&=& T(0) +c\sum_{1\leq i\leq n} i^2.
\end{eqnarray}

Do you know how to simplify this using the addition formula for the first $n$ squares?


Meaning of "number of keys in the range $a$ to $b$"

It probably means "the number of array elements whose value is between $a$ and $b$".
For the solution, it is crucial that the number of possible values of array elements is $O(1)$.


The malicious user has to first get the malicious code into kernel space somehow. User and kernel address spaces often look contiguous under linux and various unixes, but user space isn't mapped into kernel space, and vice versa. Some variations of Unix (the Masscomp system, as I recall) made this more explicit by having user space and kernel space start at 0x00000000. So, that's the first problem: code at 0x0804890c (or where ever) writeable by the user doesn't exist in the kernel's address space.

Secondly, the malicious user would have to have the ability to change the interrupt vector. This vector conceptually could live in either kernel or user space, but probably resides in kernel space. If the interrupt vector resides in kernel space, the user doesn't have write access.  If the interrupt vector resides in user space, it's marked read-only, and the addresses in it point to code in kernel space. Which is why problem (1) above for the malicious user exists.


Minimizing catastrophic risk in Gale-Shapley matching

(In theory) No, no other strategy will help. In the student-proposing version of the deferred acceptance algorithm, it is a theorem[0] that each student's optimal action is to report her true preference order. It's a dominant strategy, meaning this is optimal regardless of what others submit. This implies that if the student is unmatched when submitting her true preferences, then there is no other submission she could make that would have gotten her matched[1].

Note deferred acceptance still works for weak preference orderings (see [0]), so e.g. here the student is indifferent between all hospitals and prefers them all to being unmatched. The dominant-strategy guarantee of deferred acceptance still holds.

(In practice) In practice, students don't interview or rank all possible hospitals. So a student could likely improve her chances by trying to interview and rank mostly lower-prestige programs where the competition is lower.

[0] e.g. Theorem 8 of the survey by Al Roth, Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions. https://web.stanford.edu/~alroth/papers/GaleandShapley.revised.IJGT.pdf

[1] I am assuming she prefers any match to being unmatched.


Reduction — Do they work for unrelated problems?

If you have a problem $X$ that is in P, then you can construct a polynomial time reduction to any problem $Y$ in NP (or in 'any' other class of problems*). This is possible, as our 'reduction' is allowed to spend polynomial time on the input of $X$, so it can simply determine whether a given input $I$ for $X$ is a 'yes'-input in polynomial time and map to a trivial input for $Y$ with the same truth-value.

*: To be precise, any decision problem such that we can find at least one 'yes'-instance and one 'no'-instance, which holds for pretty much any interesting decision problem.


Whether language of all turing machines is decidable or undecidable or semi-decidable?

Let us express $L$ slightly more precisely.
$$ L=\{<TM>\; \mid \text{The language accepted by } TM \\ \text{ is a recursively enumerable language}\}$$

Since for any Turing machine $TM$, the language accepted by it is a recursively enumerable language by definition, that restriction clause for $TM$ does not have any effect at all. We have, as indicated by OP,
$$L \text{ is the set of encodings of Turing machines.} $$

The question becomes "Whether the language of all Turing machines is decidable or undecidable or semi-decidable?" as in the title.

Now this question is really about how we encode all Turing machines (in some specified model). There are ways to encode them so that we could end up with undecidable or semi-decidable language. However, in most reasonable encodings of Turing machines of most common models such as the standard Turing machines described in Wikipedia, we can check whether a string encodes a Turing machine by an algorithm in finite time.

So the simplified answer is "$L$ is decidable". This is the generally accepted answer. It is especially suitable when the encoding of Turing machines is implied to be decidable such as in the book Introduction to the theory of computation by Michael Sipser. Or when a decidable encoding of Turing machines has been described explicitly and has been assumed to be the default such as in the book Introduction to automata theory languages and computation by John E. Hopcraft et. al.

(The complete answer would be "$L$ is decidable unless an unusual encoding of Turing machines is used", which sounds, however, pedantic and which is usually not a welcomed answer.)


How does the Monte Carlo Tree Search Algorithm Decide When to Expand?

With each rollout the algorithm goes through steps of selection, expansion, simulation, and backpropagation. It does this incrementally one move at a time. 1 selection, 1 expansion, 1 simulation of random playouts them back propagated the values back to root. Next rollout and henceforth depending on ucb weights between exploration and exploitation.


Can you do operations on the halt state of a turing machine?

It may depend on the exact definition you're using for Turing machines, but most reasonable definitions will probably halt at the halt state. Your transition function can include transitions at the halt state, they just won't be executed. It's also possible that your particular definition prohibits such transitions.

In summary, your definition will tell you everything you need to know. Take a look!


Counting permutations whose elements are not exactly their index ± 1

Checkout Derangements

"Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number."

In applying this to your problem, there would be two hats: the element's index +1, the elements index -1.

I'm not certain this solves the problem, but it seems like a step in the right direction.


proving correctness of algorithm about graphs with DFS

Your algorithm is correct, but I think there's an issue with your proof. The issue is that if $u$ and $v$ are in different branches of the tree, then their distance would be $L[u]+L[v]$, not $t$.  This quantity is already defined to be even, so your proof only needs to be slightly modified to handle this case.

Edit: It is also the case that for any DFS tree, any edge not in the tree will be a back edge between nodes in the same branch. Therefore, the question asker's proof is correct.


Operations making non-context-free languages regular

Let $A$ be $\{a^p\mid p\text{ is prime}\}$. Let $B$ be $\{a\}^*$.

Both $A^*$ and $A\circ B$ are regular. $A^*$ is $\epsilon+aaa^*$ and  $A\circ B$ is $aaa^*$.


Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper

If I wanted to solve this problem, I wouldn't limit myself to the linear subset scan algorithm: I would consider other algorithms as well.

For instance, here is one approach that might be effective in many cases.  If $\theta$ is a non-negative real number, define

$$h(\theta) = \max \left\{\sum_{i \in I} a_i : \sum_{i \in I} b_i \le \theta\right\}.$$

Note that

$$F(I^*)/G(I^*) = \max_\theta F(h(\theta))/G(\theta).$$

So, define $f:\mathbb{R}\to \mathbb{R}$ by

$$f(\theta) = F(h(\theta))/G(\theta).$$

With these definitions, our goal is to find the maximum of $f$.

Also, note that we can compute $h(\theta)$ for any given $\theta$ of our choice, using integer linear programming.  (In principle, there is no guarantee that ILP will run in polynomial time, but in practice, I bet it may often be possible to compute this reasonably efficiently.)  Your linear subset scan algorithm (sort the $a_i,b_i$ by decreasing value of $a_i/b_i$) is a good heuristic for efficiently computing an approximate solution to this ILP (computing a lower bound on $h(\theta)$), but as far as I can see, there is no guarantee that it will actually find the true optimum value.

This means that we can also compute $f(\theta)$ for any given $\theta$ of our choice.

So, we have a function $f$ in one real variable, to which we have black-box access, and we want to maximize it.  Now a reasonable approach is to apply any standard algorithm for black-box mathematical optimization, e.g., grid search followed by hill-climbing, coordinate descent, gradient descent, Newton's method, or other methods.

It is also possible that some suitable criterion on $F,G$ might imply that $f$ has a nice property that makes it easy to maximize (e.g., it is increasing or something), and which might imply that your linear subset scan algorithm is a good approach.  I have not thought about that carefully, but you might look at that direction.


We can consider the more general problem of makespan, in which we wish to partition the tasks into $m$ sets as evenly as possible (your case is $m=2$). We measure the quality of our solution using the maximum total sum of a set, which we wish to minimize. Finn and Horowitz showed that the locality gap for this problem is $2-2/(m+1)$. This means that a locally optimal solution has objective value larger by a factor of at most $2-2/(m+1)$, and moreover there are examples in which the ratio approaches $2-2/(m+1)$. In particular, local search doesn't always give the optimal solution.

For other local search algorithms for makespan, consult the survey of Schuurman and Vredeveld.


Checking whether union of two languages is regular

If $L$ were regular than so would the following language be:
$$L \cap ca^*b^* = \{ ca^nb^n \mid n \geq 0 \}.$$
You can show that the latter language is not regular in various ways.


In general we do not assume that push-down automata have an end-of-string (or end-of-input) marker.

PDA have two modes of acceptance, with final state and with empty stack. Even when the automata are written for final state acceptance it is helpful in the design to check that the stack is empty. That ensures no data is unprocessed.

The PDA on wikipedia for the language $\{0^{n}1^{n}\mid n\geq 0\}$ has transitions: $(p,0,Z,p,AZ)$,
 $(p,0,A,p,AA)$,
 $(p,\epsilon ,Z,q,Z)$,
 $(p,\epsilon ,A,q,A)$,
 $(q,1,A,q,\epsilon )$, and
 $(q,\epsilon ,Z,r,Z)$. Initial state $p$ and final state $r$. This indeed is of the form you describe.

The same language can be accepted without $\epsilon$-transitions at all.

$(p,0,Z,q,Z)$, $(q,0,Z,q,AZ)$, $(q,0,A,q,AA)$, $(q,1,A,r,\epsilon)$, $(q,1,Z,s,\epsilon)$,  $(r,1,A,r,\epsilon)$, $(r,1,Z,s,\epsilon)$. Initial state $p$ and final states $p$ [to accept $\epsilon$] and $s$.


Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it

You can solve in linear time this using dynamic programming on trees.

Scan the tree from the leaves up toward the root, for each vertex $v$ calculating, for $b \in \{0,1\}$, the number of vertices $u$ below $v$ such that the $(v,u)$ path has the same parity as $b$.


How to prove {a^(n^2) | n>0} is not context-free?

[Since (a) this is an instance of a standard problem and (b) I wasn't able to find it in the archives, I'll expand my comment into a hinted solution.]

As usual in problems like this, we assume that the language $L$ is context free, so the Pumping Lemma applies, meaning that there is an integer $p>0$ such that we can write the string $a^{p^2}$ as the concatenation of strings $uvxyz$ with $|vy|>0$ and $|vxy|=t\le p$. Hence, we'll have
$$
0 < |vy|=t\le p
$$
This means that when we pump $uvxyz$ to $uv^ixy^iz$ we'll have
$$
p^2<|uv^ixy^iz|=p^2+(i-1)t\le p^2+(i-1)p
$$
Choosing $i=2$ gives us
$$
p^2<|uv^2xy^2z|\le p^2+p
$$
Now, in length order, the next string in $L$ after $a^{p^2}$ will be $a^{(p+1)^2}$. Here's the hint: use this fact to show that $uv^ixy^iz$ can't possibly be in $L$, contradicting the Pumping Lemma consequence that all the pumped strings are in $L$, so consequently $L$ cannot be a CFL.

This idiom, BTW, can be used to show that other languages over a one-symbol alphabet aren't context-free, like the $a^{n^5}$ language or the $a^p$ language, where $p$ ranges over the primes. There are more general results, as well, like the one that says that any CFL over a one-symbol language is regular. That, along with another theorem that says, roughly, that a regular language over a one-symbol language can't be too "sparse", gives a higher-level proof of your question.


According to wikipedia, topological sorting is in NC2. Note sure whether this is trustworthy, the proposed algorithm seems to require AC2:

  One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph. Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering (Dekel, Nassimi & Sahni 1981).

To check whether this algorithm is really in NC2 instead of just AC2, note that even so a single addition could take log log n time, all the additions of a max-plus matrix multiplication can be done in parallel. However, it is unclear how to do a single binary max operation in constant time.

It looks as if the max operations of a max-plus matrix multiplication cannot all be done in parallel. Maybe there is some trick to get the max of n numbers with log n bits in log n time, but I cannot see it at the moment. Edit: Here is the trick: Expand the numbers from binary to unary, then the maximum can be computed independent for each bit. Since conversion between unary and binary can be done in AC0 in both directions, it looks like we don't just get NC2, but even AC1. So this is even an example for the real question, i.e. a non-trivial function in TC1.

As Emil Jeřábek pointed out, there is no end to functions in TC1:

  all context-free languages, determinants over Z and over finite fields, various related problems in linear algebra (matrix powering, matrix inverse, characteristic polynomial, solvability of linear systems)

However, I have the impression that all those examples are also in AC1 or even weaker classes like SAC1. Just like my example which initially was even unclear whether it is in NC2, they don't need the power of TC1.

Coming up with examples which are in TC1 (or NC2) and really need TC1 (or NC2) will be extremely challenging.


Word factorization in $O(n^2 \log n)$ time

If I'm not misunderstanding you, I think the minimum cost factorization can be calculated in $O(n^2)$ time as follows.

For each index i, we will calculate a bunch of values $(p_i^\ell, r_i^\ell)$ for $\ell=1,2,\ldots$ as follows. Let $p_i^1\ge 1$ be the smallest integer such that there is an integer $r\ge 2$ satisfying $$S[i-rp_i^1+1, i-p_i^1] = S[i-(r-1)p_i^1+1, i].$$ For this particular $p_i^1$, let $r_i^1$ be the largest $r$ with this property.
If no such $p_i$ exists, set $L_i=0$ so we know there are zero $(p_i^\ell,r_i^\ell)$ values for this index.

Let $p_i^2$ be the smallest integer strictly bigger than $(r_i^1-1)p_i^1$ satisfying, likewise,
$$S[i-r_i^2p_i^2+1, i-p_i^2] = S[i-(r_i^2-1)p_i^2+1, i]$$
for some $r_i^2\ge 2$. Like before, take $r_i^2$ to be the maximal one having fixed $p_i^2$.
In general $p_i^\ell$ is the smallest such number strictly bigger than $(r_i^{\ell-1}-1)p_i^{\ell-1}$. If no such $p_i^\ell$ exists, then $L_i=\ell-1$.

Note that for each index i, we have $L_i=O(\log (i+1))$ due to $p_i^\ell$ values increasing geometrically with $\ell$. (if $p_i^{\ell+1}$ exists, it's not just strictly bigger than $(r_i^\ell-1)p_i^\ell$ but bigger than that by at least $p_i^\ell/2$. This establishes the geometric increase.)

  Suppose now all $(p_i^\ell,r_i^\ell)$ values are given to us. The minimum cost is given by the recurrence
  $$\mathrm{dp}(i,j) = \min\left\{\mathrm{dp}(i, j-1) + 1, \min_\ell \left(\mathrm{dp}\left(i,j - r_j^\ell p_j^\ell\right) + \mathrm{dp}(j-r_j^\ell p_j^\ell+1,j-p_j^\ell)\right)\right\}$$
  with the understanding that for $i>j$ we set $\mathrm{dp}(i,j) = +\infty$.
  The table can be filled in $O(n^2 + n\sum_j L_j)$ time.

We already observed above that $\sum_j L_j = O(\sum_j \log (j+1)) = \Theta(n\log n)$ by bounding the sum term by term. But actually if we look at the whole sum, we can prove something sharper.

Consider the suffix tree $T(\overleftarrow{S})$ of the reverse of $S$ (i.e., the prefix tree of S). We will charge each contribution to the sum $\sum_i L_i$ to an edge of $T(\overleftarrow{S})$ so that each edge will be charged at most once. Charge each $p_i^j$ to the edge emanating from $\mathrm{nca}(v(i), v(i-p_i^j))$ and going towards $v(i-p_i^j)$. Here $v(i)$ is the leaf of the prefix tree corresponding to $S[1..i]$ and nca denotes the nearest common ancestor.

This shows that $O(\sum_i L_i)=O(n)$. The values $(p_i^j,r_i^j)$ can be calculated in time $O(n+\sum_i L_i)$ by a traversal of the suffix tree but  I will leave the details to a later edit if anyone is interested.

Let me know if this makes sense.


String matching for wildcard-based records

One candidate approach would be build a BDD or a deterministic finite-state automaton that accepts all strings that match at least one of the records in your set of records.  These data structures can handle wildcards.  To use a BDD, treat each segment as a bit string, so the alphabet is $\{0,1,.\}$ (perhaps it's now a trinary decision diagram rather than a binary decision diagram, but the ideas remain the same).

An alternative approach (if the number of segments per string will always be relatively small): You can solve your problem by building a set of indices, one index for each subset of possible segments.

Suppose we're guaranteed that every string will have exactly 3 segments, call them segments ABC.  We're now going to build seven indices:

The ABC index contains the set of all records with no wildcard.  e.g., 1.2.3
The AB index contains the set of all records with a single wildcard, in the 3rd (C) segment. e.g., 1.2.*
The AC index contains the set of all records with a single wildcard, in the 2nd (B) segment. e.g., 1.*.3
The BC index contains the set of all records with a single wildcard, in the 1st (A) segment. e.g., *.2.3
The A index contains the set of all records with two wildcards, in the 2nd and 3rd (B and C) segments. e.g., 1.*.*
The B index contains the set of all records with two wildcards, in the 1st and 3rd (A and C) segments. e.g., *.2.*
The C index contains the set of all records with two wildcards, in the 1st and 2nd (A and B) segments. e.g., *.*.3
I assume you won't have any records with three wildcards (*.*.*), but if that was possible, you'd have an 8th index that records whether you have such a record or not.

Each index is stored as a hash table, so given a string you can quickly (in $O(1)$ time) check whether that string is present in that index.

Now, when you receive a string 4.5.6, you look it up in each index.  For instance, you look up 4.5.6 in the ABC index, 4.5.* in the AB index, 4.*.6 in the AC index, and so on.  If any of these lookups succeeds, then you know that 4.5.6 matches one of the records.  Otherwise, 4.5.6 does not match any of the records.  The running time for a lookup is $O(1)$.

If you know that every string will have exactly 5 segments, you'll need 31 indices and the time for a lookup is $O(1)$ (31 lookups into 31 hashtables).
If every string has exactly 5 segments and you know that no record will have more than 2 wildcards, then it's enough to have $1+5+10=16$ indices.

This will probably be OK for your particular parameters, where every string has at most 5 segments.  Obviously, though, if the number of segments is too large, this will be extremely slow and inefficient.


What does the $\leq_{\mathrm{P}}$ symbol mean?

It should have been defined wherever you've seen it used. It normally stands for polynomial-time reducibility of one kind or another; usually many-one reducibility.


Merge Sort Confusion - Initial Phase Missing?

What is pictured is often called "bottom up mergesort", which is contrast to the "normal" mergesort, which you could call "top down merge sort".

You can find them contrasted in this article from Algorithms:

  Bottom-up mergesort. Even though we are thinking in terms of merging together two large subarrays, the fact is that most merges are merging together tiny subarrays. Another way to implement mergesort is to organize the merges so that we do all the merges of tiny arrays on one pass, then do a second pass to merge those arrays in pairs, and so forth, continuing until we do a merge that encompasses the whole array. This method requires even less code than the standard recursive implementation. We start by doing a pass of 1-by-1 merges (considering individual items as subarrays of size 1), then a pass of 2-by-2 merges (merge subarrays of size 2 to make subarrays of size 4), then 4-by-4 merges, and so forth.

We don't need to use recursive calls to decide how to break down the array. Rather, it's implicit which elements can be grouped with which elements by simply grouping them into powers of two.
This version of merge sort can be more easily written without recursion, which removes some overhead. It's also seems more amenable to various optimizations, such as SIMD or other vectorized operations, loop unrolling, etc.


Can we prove mathematical induction statements in Lisp?

Let me try to clarify a point that seems to be confusing you: you seem to be conflating 2 related, but different concepts.

The first is the concept of a proof system, which allows you to specify and prove theorems about mathematics or computer science. Dependent types are one elegant way to do this, where the types are the specification language and the proofs are identified with programs, but this is not the only way to build a proof system! Isabelle allows you to specify and prove properties about programs, and is not based on dependent types or the Curry-Howard isomorphism/approach. The crucial takeaway is that these systems require the user to supply the proof.
The second is the notion of automatic theorem proof systems (or provers) which take a specification language and automatically attempt to divine a proof. This means that ATP systems are in particular proof systems, where the user input for proofs is just a click on the "prove" button (actually most ATP systems allow and require a lot more input from the user). This state of affairs is of course quite desirable in theory, as it greatly relieves the burden for the user, and most proof systems integrate some capabilities of ATP.

With these clarifications in mind, my first answer is that Lisp is neither a proof system nor an ATP system. It is a programming language. As such, it cannot be said to prove anything as is. The Lisp language is untyped, so it doesn't even make sense to ask if its type system can be seen as a specification language.

My second answer is that Haskell is neither a proof system nor an ATP system. This seems to contradict the answer given to you here, but the point is that the Haskell type system closely reassembles a dependently typed proof system, to the extent that "specification-like" types can be given and "proof-like" programs can be written. One important limitation is that Haskell is not consistent when viewed as a logic. In particular, $1+1 = 3$ can easily be "proven" in a variety of different ways. Actual proof systems like Agda and Coq, however, can be used to specify and prove things about programs, which themselves can be extracted to Haskell programs.

All this being said, there is a very notable ATP system that can specify and automatically prove things about (a small subset of) Lisp programs including your example: the ACL2 system. Hey, they even have your example in these slides! (They don't give the solution though).


Is the following problem NP-hard? (or have you seen it before?)

This problem (more formally its decision version) is NP-complete.
NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard.
In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a specific order. Each operation $o$ has a specific machine $m_o \in M$ that it needs to be processed on and only one operation in a job can be processed at a given time. (adapted from Wikipedia)
Now it is easy to see that JSP is just a special case of your proposed problem (one task per operation of JSP, dependencies only between successive operations in a job), which makes it at least NP-hard too.
Membership in NP can be shown by guessing an optimal schedule and verifying in polynomial time that it fulfills all constraints.


Represent the Hex as Graph;

each node has additional property; has_letter; $T,F$
add the first randomly

choose starting point on the graph, probably randomly
place the letters by DFS or BFS,
add the letter into a list $l$.

adding another word with one connection, from start

from the list find the first letter of the new string that in the middle of another.
place the remaining words by DFS or BFS in nodes with $F$ flag.

adding another word with one connection, not necessary from the beginning.

from the list find the letters of the new string.
One part may be on the upper; as corner and almond. if the connection is $o$, alm on the upper,
One part may be on the lower, and nd from the previous example.
place the upper part with DFS or BFS in nodes with $F$ flag.
place the lower part with DFS or BFS in nodes with $F$ flag.

Hope this helps;


Can you pop 2 elements at a time in a PDA

In the usual definition of pushdown automata, at every step the PDA pops a stack symbol and reads an input symbol, and based on that it pushes a string of symbols (zero or more) onto the stack, and transitions to a new state (possibly non-deterministically, i.e. there could be several or no choices). If you define PDAs according to this definition then you cannot pop two stack symbols in a single transition.

That said, you can simulate popping two symbols using epsilon transitions (exercise). Therefore, the variant of PDAs in which you are allowed to pop more than one stack symbol is equivalent in power to a standard PDA.


How can I solve a recursive equation with a summation notation?