Deciding whether there exists a permutation of the entries of an $n \times n$ matrix that is magic Given an array of $n^2$ integers, what is the most efficient way to determine whether any permutation of those integers can form a magic square? "Magic square" being an arrangement of those integers on a square grid such that all rows, columns and diagonals sum to the same value.

Note that this isn't asking how to test if a given arrangement is a magic square, which would be $O(n^2)$, but whether any possible square formed from the array is magic.

One approach is to use integer linear programming, and hope that an ILP solver will be able to find a solution.  This will probably still be exponential in $n$ in the worst case, but it might be faster than enumerating all $n!$ solutions.

Here's more detail.  Suppose we are given the integers $a_1,a_2,\dots,a_{n^2}$.  Let $M=(a_1+\dots+a_{n^2})/n$ be the magic constant of the magic square, so that every row, every column, and every diagonal needs to sum to $M$.  Define zero-or-one integer variables $x_{i,j,k}$, with the intended meaning that $x_{i,j,k}=1$ means that the number $a_k$ is placed in row $i$, column $j$.  Then we have the inequalities

$$\begin{align*}
&\sum_i a_k x_{i,j,k} = M\\
&\sum_j a_k x_{i,j,k} = M\\
&\sum_i a_k x_{i,i,k} = M\\
&\sum_i a_k x_{i,n+1-i,k} = M\\
&\sum_k x_{i,j,k} = 1\\
&\sum_{i,j} x_{i,j,k} = 1.
\end{align*}$$

Then any feasible solution to these linear equalities will represent a valid magic square, so you can feed this to an off-the-shelf ILP solver and hope that it finds a solution for you.  Probably it will fail (take forever) once $n$ gets large, but it might be effective if $n$ is small enough.


Breaking up sum of power of 2s I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays.

I encountered a sub-problem that requires me to break up sums of numbers which are power of 2, i.e. how to find combinations of these numbers that sum up to a certain value. The sum and the combination size are given. Also only 4 power of 2s can be present in a combination: 2,4,8,16.

Lets suppose I have a sum of 8 and I need to break up into a set of 3 numbers. The result would invariably be [2,2,4].

If I need to break up 20 into 3 power of 2s, I could have [2,2,16] or [4,8,8].

Naturally larger sets will result in many possible combinations.

My aim is to write an algorithm that obtains all possible combinations as efficiently as possible. I'm not looking for the algorithm itself, but some leads into how to partition the number.
What are some properties of power of 2s that I need to use to partition a sum into a possible combination?

Look at the binary representation of the sum. Each 1 in that representation represents a power of two that has to be included as a summand, either directly or indirectly.

If the number of 1s in that representation is greater than the number of summands, there is no solution, if it is equal, there is exactly one solution, and if it is smaller, things get interesting.

The basic property you'll want to exploit in the last case is that you can represent any power of two as once that power, or twice the next smaller power, or 4 times the one after that and so on.

I think this approach can lead to an efficient algorithm. (But I did not follow it through myself, so no guarantees.)


Find position in array where element-wise multiplication with string of 1 and 0s results in max value I have a sequence of 1s and 0s. For example: $bits = [1, 0, 1, 1, 1, 0]$. I also have an array of positive integers. For example $arr = [12, 23, 4, 6, 8, 0, 24, 72]$. I need to find the index, $i$, in $arr$ of the leftmost element of $bits$ such that
$$\sum_{j = i}^{i + \textrm{length of bits}}{bits[j - i] * arr[j]}$$
is a maximum. Essentially I am maximizing the element-wise multiplication between the two sequences starting at index $i$.
I need to solve it in $O(n\log n)$ or better, but I can only think of a way to do it in $O(n^2)$. I have a feeling prefix sums could be used but am not sure how.

Let the array consist of the numbers $a_0,\ldots,a_{n-1}$, and let the mask be $b_0,\ldots,b_{k-1}$. Define
$$
A = \sum_i a_i x^i, \quad
B = \sum_j b_j x^{k-1-j}.
$$
Notice that
$$
AB = \sum_{i,j} a_i b_j x^{i+k-1-j},
$$
and so the coefficient of $x^{i+k-1}$ in $AB$ is
$$
\sum_{j=i}^{i+k-1} a_j b_{j-i}.
$$
Therefore if you can calculate $AB$, you can solve your problem.
You can calculate $AB$ in $O(n\log n)$ using FFT.


number of random sets needed to generate subset Let $A\subseteq \{1\ldots n\}$ with $|A|=\alpha n, 0<\alpha\leq1$. Now we start generating random sets $B_i \subseteq \{1\ldots n\}$ with $|B_i|=\beta n$ where $0<\beta\leq\alpha$.

How many $B_i$ do we have to generate, so that there exists a $j: B_j\subseteq A$ with decent probability (constant or overwhelming in $n$).

It holds that $\Pr[B_i\subseteq A$ for a fixed $i$]=${\binom{\alpha n}{\beta n}}/\binom{n}{\beta n}$. If the probabilities for all $B_i$ would be independent we could make use of the geometric distribution to calculate (or at least bound) the probability that after generating $N$ random $B_i$ there is no $B_i: B_i\subseteq A$. But as soon as the $B_i$ start intersecting the probabilities seem not to be independent anymore. Any help would be appreciated.

Edit:

Ok, I guess my problem is, that I do not understand, if we are facing dependencies or not. So let me give some more details: The set $A$ is unknown, but we get access to an oracle $\mathcal{O}(B_i)$, that for input $B_i\subseteq \{1,...,n\}$ with $ |B_i|=\beta n$ outputs true, if $B_i \subseteq A$ holds and false otherwise. The $B_i$ are generated independently at random and tested sequentially for being a subset.
So if the probabilities for all $B_i$ being a subset of $A$ are independent it must especially hold, that $$\Pr[B_2\subseteq A | B_1\not\subseteq A]=\Pr[B_2\subseteq A]$$

But doesn't the probability of $B_2$ being a subset of $A$ conditioned on $B_1$ being not a subset of $A$ depend on the size of the intersection of $B_1$ and $B_2$? So for example if $|B_1\cap B_2|=\beta n \Leftrightarrow B_1=B_2$ than $\Pr[B_2\subseteq A | B_1\not\subseteq A~\wedge~ B_1=B_2]=0$. Or does this just mean that all three events $(B_2\subseteq A, B_1\not\subseteq A, B_1=B_2)$  are not independent, but $B_2\subseteq A$ and $B_1\not\subseteq A$ can still be independent? If so, can we give a formal proof, that these events are indeed independent?

The sets $B_i$ can be independent but still have an intersection; just because they are generated independently doesn't prevent them having an element in common (in fact, it ensures that possibility exists).  If you assume that the sets $B_i$ are generated independently, then they are independent, period.  If you don't assume that, you have to define how you assume that they are generated before you can calculate any probabilities.

Regarding your updated question: "But doesn't ... ?"  - Answer: No, it doesn't.  If the r.v.s $B_1,B_2$ are independent, then the events $B_1 \not\subseteq A$, $B_2 \subseteq A$ are independent.

If you want a formal proof, here is one.  If $B_1,B_2$ are independent random variables and $f$ is any function, then $f(B_1),f(B_2)$ are independent random variables.  (You should try to prove it; it is not hard.) Then let $f(X)$ be true if $X \subseteq A$, or false otherwise, and the claimed result follows.


Determining if $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} is not a regular language using Pumping Lemma? In short, is this similar to how $a^nb^n$ is not a regular langauge?

$L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $}

For instance, if we have the string  $w=a^psb^p$, and we know that $|xy| \le p$, there would simply be a disproportianate amount of a's or b's regardless of where we put $y$ ?

Your language is equal to $L(a^+b^+)$ (why?).


MAX 10-SAT Algorithm The MAX k-SAT problem is:

  “Given a set of clauses C1,…,Ck, each of length k, over a set of
  variables x1,…,xn, find a truth assignment that satisfies as many of
  the clauses as possible.”

I'm trying for find a randomized 0.999-approximation algorithm for the MAX 10-SAT problem. Help :(


Can a total programming language be Turing-complete? I've seen two answers to this:
Wikipedia says no:

These restrictions mean that total functional programming is not Turing-complete.

And the Wikipedia article cites D.A. Turner as the coiner of "total functional programming," and Turner says on page 755 of Total Functional Programming:

There are two obvious disadvantages of total functional programming

Our programming language is no longer Turing complete
If all programs terminate, how do we write an operating system?

But Conor McBride says total programming languages can be Turing-complete:

Now represent the semantics of Turing machines as coinductive processes and review your hasty and inaccurate repetition of the common falsehood that totality prevents Turing-completeness. You exactly get to say “we know how to run it for as long as we’re willing to wait, but we can’t promise you it will stop”, which is both the truth, and exactly the deal when you work in a partial language. The only difference is that when you promise something does work, you’re believable. The expressive weakness is on the partial side.

Turner had indeed thought about codata, and it plays a big role in their article re problem (2), but they don't seem to think codata helps with (1).
Would an answer to McBride's Retort be something like:

Re "Now represent the semantics of Turing machines as coinductive processes ..." A Universal Turing Machine won't halt (if executing a program with an infinite loop), but a copgram will always halt until someone asks it to compute some more: to actually do computation for infinite time rather than just representing an infinite computation requires non-termination.

I'm pretty sure McBride isn't claiming that a total programming language can be Turing complete, just that it's a useless distinction in practice. You can take any program in a partial language and replace all not-provably-terminating loops with loops that run at most $2^{128}$ times, and the result is theoretically different but not observably different.

You exactly get to say “we know how to run it for as long as we’re willing to wait, but we can’t promise you it will stop”, which is [...] exactly the deal when you work in a partial language.

I.e. maximum run times are bounded in the real world.

The only difference is that when you promise something does work, you’re believable. The expressive weakness is on the partial side.

I.e. there's an expressivity tradeoff in using total vs partial languages, but the expressive advantage of total languages is useful in practice, while the theoretical expressive advantage of partial languages has no practical consequence.

Edit: In response to OP's comment, I think ruakh's comment is correct. McBride is implicitly suggesting that a better notion of completeness ought to not only replace Turing completeness as the de facto standard for real-world languages, but also take the name of Turing completeness and the brand identity associated with it, because it's more deserving of it. Maybe it would be more accurate to say he thinks the better notion of completeness ought to have been called Turing completeness from the beginning. It matters because the perception that total languages are deficient in some practical way, due to their lack of Turing completeness, may have actually hindered their real-world adoption.


Data Structure for State in Automata When I read the word "state" I think of a global object with a bunch of properties like the "application state". But it seems that in automata that the state is pretty much just an empty value.

Wondering what specifically the data structure is for automata states in general.

For example, the following comes from here:

  An alternating register automaton over A consists of: a finite set $Q$ of states with a distinguished
  initial state $q_0 ∈ Q$ and a set of accepting states $F ⊆ Q$, a finite set $R$ of registers, and a transition
  function
  $$δ : Q×A×Tests(\mathscr{R}) → B+(Q×P(\mathscr{R}))$$...

Register automata have a "memory" which I associate with state, but it seems clear it is separate from the actual states in $Q$. Just looking for the data structure for state, if it's just an incremented integer, a string label, or something else, typically.

As you say, the state of an automaton is just an abstract, unstructured value. As such, you don't need a data structure per se: you just need a variable type that can store different values, such as an integer.


Multi-qubit gates matrix representation Consider the gate used in Simon's Algorithm. It operates on a control register and target register, changing state like: $|\textbf{x}\rangle|\textbf{y}\rangle->|\textbf{x}\rangle|\textbf{y}\oplus f(x)\rangle$.

As I am working on an universal way to simulate operations on qubits, I've been using a matrix representation of gates, which allowed me to transform even pretty complicated states without much concern about transform's correctness. However, I can't really see how would I represent a gate like shown above with a matrix (or how would I build such a matrix knowing x, y and f(x)?)

How can such gates operating on multiple qubits be represented with matrices?

Alternatively, having a vector states representing x and y and knowing f how can I transform y? (If all qubits in x are set in equally-weighted superposition of 0 and 1, I guess I'd need to calculate f for all possible x states, but how should I apply the results to y then?)

The first thing to recognize is that this is a permutation matrix where each row and column contains a single $1$ entry with the remaining entries being $0$.  This follows from the fact that $x$ and $y$ represent classical bit strings and $f$ is a classical boolean function.

Let's take the basic case where $x$ is from the space of $n$ bit strings, $y$ is a single bit, and $\mathcal{f}$ maps $\{0,1\}^n$ to $\{0,1\}$. The operation then functions on $n+1$ bits and is represented by a $2^{n+1} \times 2^{n+1}$ matrix. If you let the binary number $xy$ index the matrix columns, then for column $xy$ set row $x(f(x) \oplus y)$ to 1 and all other rows to 0.

Let's look at an example from Deutsch's algorithm. Let $x$ be from $\{0,1\}$ and $f$ be bit negation, i.e. $f(0) = 1$ and $f(1) = 0$.  From here we compute, for each row, the column number containing the 1.

$\begin{array}{cc}
\mbox{column} & \mbox{row with 1} \\
00 & 0(0 \oplus 1) = 01 \\
01 & 0(1 \oplus 1) = 00 \\
10 & 1(1 \oplus 1) = 10 \\
11 & 1(1 \oplus 0) = 11
\end{array} $

This gives us the matrix

$ \left( \begin{array}{cc}
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{array} \right) $

This generalizes to when $y$ is more than a single bit.


Can one find the minima of a convex function efficiently? Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$ and let $f'$ be its restriction on the discrete hypercube $\{-1,1\}^n$.

Is there any $poly(n)$ algorithm that for any class of $f$ (and $f'$) can find the minima of it?
Is there any relation known between the point where $f$ minimizes and the vertex where $f'$ minimizes?  Like if knowing one of them helps find the other in $poly(n)$ time?

Minimizing a submodular function can be done in polynomial time.  This applies to functions on the discrete hypercube $\{-1,1\}^n$.


Is this the correct way to use the pumping lemma? I've been watching lectures from Coderisland on YouTube about finite state machines, DFAs and NFAs, and in one discussion he talks about how to use the pumping lemma to show how a language is not regular. I don't know quite how to apply the lemma and want to understand if I'm doing it right. If I had something like:

w = {anbk, n =/= k}

am I correct in that I can say that:

h = {anbn + r, r > 0} is a subset of w, and thus if I show by the lemma that h is not regular, that w must not be regular since h is a subset of w.

The way I would show this is as follows:

h = xyz
|xy| <= n
x = an-r
y = ar
z = bn + r
xyz = an-rarbn + r
xy2z = an-ra2rbn + r = an + rbn + r

Thus h cannot be regular since an + rbn + r is not of the form {anbn + r, r > 0}, and since h is not regular w must not be regular, since h is an element of w.

Have I applied it correctly? I understand how to apply it for an easy language like {anbn}, because I can apply the lemma directly to this language, but the only way I could think of for my language was to create a subset that belongs to my language, and apply the lemma to that.

If I haven't applied it correctly, is there a way to show that my language is not regular (or regular), using another lemma, or perhaps with closure properties?

This is a really awesome topic, even if I don't understand the pumping lemma fully, I'm excited to explore it further!

A subset of a regular language could be non-regular, so the entire line of reasoning is flawed. As an example, every non-regular language over $\{0,1\}$ is a subset of the regular language $(0+1)^*$.

Regarding the language $H$, you'd do better writing your proof in paragraph-style rather than as a cryptic list. In addition, you made the following mistakes:

You never mention which $h$ you take.
You don't get to choose the decomposition $h = xyz$. The proof has to work for every such decomposition satisfying the properties given in the lemma ($|xy| \leq n$, where $n$ is the "pumping constant").

Several ways of showing that your original language is not regular are given in this answer.


Doubt on declaring an array in pseudocode So here's the code:-

DECLARE number as INTEGER

PRINT "Enter a number"

INPUT number

DECLARE randomarray [1:number] AS INTEGER

Is this possible? i.e whilst declaring arrays, can we use variables?

Note:The question is strictly limited to pseudocode or general programming language

Pseudocode is not a formally defined programming language. Rather, it refers to textual description of code that is not in "paragraph" form but rather in "code" form. (Paraphrasing Molière, it is a third form of expression, after prose and poetry.)

The only rule in pseudocode is that it should be self-explanatory. If there is anything that the reader might misunderstand, you have to explain it. Otherwise, it's up to you how you write pseudocode, though it's good measure to be consistent in your paper.

Your pseudocode is self-explanatory. You have declared a variable "number" of type integer, printer "Enter a number", read a number from the input into "number", and then declared an integer array "randomarray" of length "number". Moreover, your array is "1-based" (i.e., the first index is 1). If this is what you intended to convey, then you were successful and there is nothing wrong with your pseudocode.

It's good practice to try to emulate the way other people in your field write pseudocode. This will cause your code to look more "standard", and so more "professional" and easier to read. But it's definitely not necessary, and you are encouraged to write the pseudocode in whatever way seems best or nicest to you.


MST Of An Almost Tree A graph $G = (V,E)$ is called an almost tree if it is connected and has most $n + c$ edges where $n = |V|$ and $c$ is a small constant number. How would I go about designing an algorithm for a given almost tree graph $G$ with distinct edge weight costs that computes a minimum spanning tree of $G$ in time $O(n)$?

Here is the description of a desired algorithm in Python style pseudocode.

Generate a spanning tree T of G
Put all remaining edges that are not in T in a list L
For each edge e in L:
  Find the cycle C in the graph that is T plus edge e.
  If e is lighter than the heaviest edge e' in C:
    add e to T and remove e' from T

It requires $O(n)$ operations to generate a spanning tree. It requires $O(n)$ operations to find a cycle when you add an edge to a tree and $O(n)$ operations to find the heaviest edge in a cycle. Since there were total $c+1$ edges remaining, where $c+1$ is a constant, the for loop requires $O(n)$ operations. Adding up other operations of small time, we find that the time-complexity of the algorithm is $O(n)$.

The correctness of the above algorithm has been proved in my answer to turn MST of G to MST of G with one new edge. Note that initially T is its own MST.


Space complexity for finding the minimum number outside the list of numbers We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$.

We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$.

  What is the space complexity of this problem ? (The space to store the input, $L$, does not count.) What if the input $L$ is in a stream which you can only read from left to right for at most constant number of passes ?

The obvious way to solve this is just to copy $L$ into the working memory and then (in-place) sort $L$, and find $x$ in the obvious way. This algorithm uses space of size $n$.

Can we do better ?

You can solve this in time $O(n\log B)$ and constant space (assuming a machine word can store numbers up to $\max(n,B)$) using binary search.

Edit: Here are some more details. I am making the assumption that no number appears twice - perhaps that's an unfounded assumption. Given $K$, we can check whether $K<L$, $K=L$ or $K>L$ by counting how many numbers smaller than $K$ appear in the input, and whether $K$ itself appears in the input. This takes $O(n)$.

Edit 2: Following eig's suggestion, since we know that the missing number is smaller than $n+2$, this actually takes time $O(n\log n)$.


Dijikstra implementation in books subtly different I was reading about Dijkstra algorithm and was referring two books
1) Introduction to Algorithms by Cormen Section 24.3
2) Algorithm design by Kleignberg Section 4.4

And found a subtle difference in their way of show Dijkstra algorithm

book 1:

Dijkstra(G, w, s)
Initialize(G,s) d(s) = 0 initialize others to inf
S = {}
Q = G.V
while Q not equal to {}:
    u = Extract-Min(Q)
    S = S U {u}
    for each vertect v belonging to G.Adj[u] // all edges emanating from u
        Relax(u,v,w)

Note : the word in for each loop : G.Adj[u]

original snip from book

book 2:

Dijkstra(G, w, s)
Initialize(G,s) d(s) = 0 initialize others to inf
S = {}
Q = G.V
while S not equal to V:
    Select node v that is not yet added to S with at least one edge ***from S*** for which
         d'(v) = min of (d(u) + le)  // computed over all edges that
                                     // emanate from all possible
                                     // nodes in S
    Add v to S and make d(v) = d'(v)

Note : the word in for each loop : from S

original snip from book

Only I find one difference.

in book1 they are computing the neighbors of only the recently added node u. and in book2 they are computing neighbors of entire set S (see the highlighted portion "from S") (and that is not in S).

Yes, both works.

But why is there two implementations of Dijstra algorithm. Any reason
why each book has adopted a different way ?
Why should we do from entire S when we can easily do from last computed node as that is the one with the last node in the longest of the shortest path and that will decide everything ?
Am I missing something ?

Usually algorithms are specified in a somewhat high level format. Later one might fine tune some of the implementation details to get the complexity right.
Usually we call the various implementations all Dijkstra's algorithm. (And yes, I consider those implementation details, even though we are not coding in a specific language.)

How do we store the distances so that we easily find the one with shortest distance from the start node?
How do we store the graph: adjacency lists or adjacency matrix?
It might be a good idea to compute 'temporary' distances for nodes not yet completed, so that we do not have to look at all edges between nodes that are completed and those that are not yet completed.

In the special case of Dijkstra's algorithm the type of graphs we consider might influence the implementation details. We might choose a certain type of priority queue when the graphs are sparse or not.


conversion to base-R numbers I am reading Algorithms 4th edition by Robert Sedgewick and am stumped at a particular problem. On page 460 of the book the author is describing a technique to hash strings and use prime numbers for modular hashing. Starting from the fourth line:

 If R is greater than any character value, this computation would
 be equivalent to treating the String as an N-digit base-R integer,
 computing the remainder that results when dividing that number by M.

Where the algorithm being used to hash a N-character long String is:

int hash = 0;
for (int i = 0; i < s.length(); i++)
   hash = (R * hash + s.charAt(i)) % M;

How does the above algorithm result in a base-R integer?

Here M and R are integers (random) and s is the string of length N.

I am assuming that by the 'above computation' the author means the computation within the parentheses => R*hash + s.charAt(i)

The iteration results in :

(R^2*C + R^1*B + R^0*A + some constant)mod(M) for the string ABC, the value inside the brackets is a base 16 representation of CBA plus some constant value.


Do Core Computer Programs Have To Function By Powers Of 2? As an example, the sRGB Gamut is 256 x 256 x 256 (all powers of 2). I'm aware that computers are generally binary. However, is it simply a matter of simplicity that sRGB was made this way, or was it ESSENTIAL? After all, it probably could've safely provided just as many detectable colors with 192 X 192 X 192.

It is not essential. Most computers can handle no data smaller than a byte without extra effort (i.e. the memory is addressed by byte, not by bit). Hence there is generally no point in using less than a byte for anything, unless you're in a situation where memory consumption is crucial, such as network communication.


Algorithm to test a graph for $t$-transitivity I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive.

I am also interested in knowing if this problem is in P, NP, NPC or some other interesting facts about its complexity class.

If you had an oracle from Graph Isomorphism, then for constant $t$ you can check whether a graph is $t$-transitive. For example, to check if a graph is $1$-transitive, for every vertex $i$ create a variant $G_i$ of your original graph by attaching an "appendage" at vertex $i$, say a very long path or a very large star. The graph is transitive if all $G_i,G_j$ are isomorphic.


Solving recurrence relation with two recursive calls I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very.

In order to do this I ask myself the question what the runtime $T(n, p)$ would be in the case quicksort always happens to partition in some fraction $0 < p \leq {1\over 2}$ such that $\lfloor{p(n-1)}\rfloor$ elements are in the left partition and $\lceil(1 - p)(n - 1)\rceil$ are in the right partition (leaving $1$ element, the pivot, in the middle).

It shouldn't be hard to see that $T(n, p)$ gives an upper bound for the worst case where $p$ is the maximally unbalanced allowed partition, as any partition with fraction $> p$ will be more balanced and have a smaller runtime, and any fraction $<p$ is not allowed.

It's obvious that $T(n, {1 \over 2})$ is the best case and $T(n, 0)$ is the worst case of quicksort. Both have easy recurrence relations that are found in any educational resource. But I have no clue how to study $T(n, p)$ in general. The obvious relation would be:

$$T(n, p) = n + T(\lfloor{p(n-1)}\rfloor, p) + T(\lceil(1 - p)(n - 1)\rceil, p)$$

Here I get stuck. I've tried searching around, but all literature that I could understand about divide and conquer algorithms took the "divide" literally and "cheated" the analysis using the fact that the partitions are always equal in size, merging the terms into one times a constant.

I do not know how to deal with two recursive calls, and I do not know if it is safe to remove the rounding. Is this possible to solve analytically, and if yes, how?

P.S.: I'm not interested in asymptotics (which is easy to show $\Theta(n \log n)$ for any constant $p$). I am interested in how much slower quicksort becomes as $p$ gets smaller, for example I'm interested in the ratio $T(n, 0.25) \over T(n, 0.5)$.

P.P.S: As an undergraduate student I apologize if I've made obvious things too lengthy or underexplained nontrivialities. And while I don't know if it's looked down upon here so much as other SE sites, I'll note that this is personal interest, not homework.

As you mention, the Akra–Bazzi theorem shows that the solution to the recurrence $T(n,p)$ is $O(n\log n)$ for all $p \in (0,1)$. However, this does not reveal the nature of the dependence on $p$. To determine the latter, we can use a recursion tree approach.

At the root of the recursion tree is the interval $\{1,\ldots n\}$. Its two children are the intervals $\{1,\ldots,pn\}$ and $\{pn+1,\ldots,n\}$, whose total length is again $n$. Each of these nodes has two children (assuming $n$ is large enough), and so on. For simplicity we ignore rounding errors, that is, we assume that $pn$ is an integer; this is just a technicality, and I wouldn't worry about it. We stop the process whenever a node has length at most $1$. The complexity of the algorithm is proportional to the total length of intervals in the tree. When $p \neq 1/2$, the leaves (nodes at which we stop the process) have different depth, and that makes it more difficult to determine the overall complexity.

We can obtain a simple upper bound by noting that the tree has at most $\log_{1-p} (1/n)$ levels: each node is at least a factor of $1-p$ smaller than its parent. Just like in the analysis for $p = 1/2$, the total length of intervals at any level is at most $n$, and we obtain an upper bound of $O(n\log_{1-p} (1/n))$ on the running time. Since $\log_{1-p} (1/n) = \log n/\log (1-p)^{-1}$ and $\log (1-p)^{-1} = -\log (1-p) = p \pm O(p^2)$ for small $p$, we can write this as $O(n\log n/p)$.

Here is a more accurate calculation. Consider level $t$. Suppose we don't stop the process upon reaching a small interval. We can generate a random vertex by taking $t$ steps, in each of which we go left (say) with probability $p$ and right (say) with probability $1-p$. Each time we take a left step the log of the length of the interval decreases by $-\log p$, and each time we take a right step it decreases by $-\log (1-p)$. A vertex is in the actual tree of the log of the length decreased by at most $\log n$. The total weight of intervals on level $t$ of the tree is exactly the probability that a vertex generated according to this process correspond to a decrease of at most $\log n$. That is, if $D$ is the distribution which is equal to $-\log p$ with probability $p$ and to $-\log(1-p)$ with probability $1-p$, and $X_1,\ldots,X_t \sim D$ are independent, then the total weight of level $t$ is $\Pr[X_1+\cdots+X_t \leq \log n]$. For super-constant $t$, the random variable $X_1+\cdots+X_t$ is roughly normally distributed with mean $[-p\log p-(1-p)\log(1-p)]t$ and variance linear in $t$, so for $t$ satisfying $[-p\log p-(1-p)\log(1-p)]t \leq (\log n)/2$, say, the probability will be very close to $1$, while for $t$ satisfying $[-p\log p-(1-p)\log(1-p)]t \geq 2\log n$, say, it will be very close to zero. Defining $h(p) = -p\log p-(1-p)\log(1-p)$ (known as the binary entropy function), we conclude that the running time is $\Theta(n\log n/h(p))$ (uniform in $p$, as $n\to\infty$). As $p\to 0$ we have $h(p) \approx -p\log p$, and so our earlier estimate was not tight.

Another way of looking at the same analysis is by having an infinite sequence of independent random variables $X_1,X_2,\ldots$ as before, and defining a stopping time $T$ to be the first time $t$ such that $X_1 + \cdots + X_t \geq \log n$. The running time is then proportional to $n\mathbb{E}[T]$. The elementary renewal theorem then states that $\lim_{n\to\infty} \mathbb{E}[T]/\log n = 1/\mathbb{E}[D] = 1/h(p)$, implying that the total size of intervals equals $(1+o(1))n\log n/h(p)$. More accurately, for every constant $p$ the total size of intervals is $(1+\alpha_p(n))n\log n/h(p)$, where $\alpha_p(n) = o(n)$. The convergence in the elementary renewal theorem is exponential in the time parameter — $\log n$ in our case — so should be polynomial in $n$, that is, $\alpha_p(n) = O(n^{-C_p})$. The convergence is also probably uniform for $p \in (\delta,1-\delta)$ for any $\delta > 0$.

Summarizing, the total length of intervals in the recursion tree, which is proportional to the running time, is of the following form for every $p$: $$ T(n,p) = (1+o(1)) \frac{n\log n}{h(p)}, $$ where $\log n$ and $h(p) = -p\log p-(1-p)\log(1-p)$ are taken to the same base, and the $o(1)$ is a function depending on $p$ and tending to $0$ with $n$.

Moreover, it is probably true that for any $\delta > 0$ and any $p \in (\delta,1-\delta)$ it is true that the total length of intervals is of the form $$T(n,p) = (1+O(n^{-C_\delta})) \frac{n\log n}{h(p)}, $$ where $C_\delta > 0$ and the hidden big O constant depend only on $\delta$. In particular, it should be the case that for all constant $p_1,p_2$,
$$\lim_{n\to\infty} \frac{T(n,p_1)}{T(n,p_2)} = \frac{h(p_2)}{h(p_1)}, $$
and the convergence is polynomially fast.


Question on the "Tutorial implementation of dependently typed lambda calculus" I have a slight technical struggle with this marvelous tutorial. On page 5 the tutorial talks about typing rules for Simply Typed Lambdas and presents following judgement as derivable via rules on figure 3.
I was unable to prove neither id nor const by the same reason. Take for instance the id example.

Say I am looking on type checking rule CHK. It says that in order to check types I should first perform inference and then compare result with what I expect.
To do the inference on application, I have to use the APP rule that immediately forces me to infer the type of the left hand side of the application, namely (id :: α -> α)
To do that I am using the ANN rule that forces me to check that α -> α is a type (and I can prove it no problem). Then I got this naked id symbol and have to prove it's type to be α -> α.
Finally, here is a problem. In order to do that I will have to use var rule, which requires the type of id to be set in the context Gamma explicitly, but it is not done, therefore the proof is falling apart.

$\mathsf{id}$ and $\mathsf{const}$ are not variables of the calculus, but syntactic sugar for $\lambda x \rightarrow x$ and $\lambda x \rightarrow \lambda y \rightarrow x$ respectively. This is stated at the end of §2.2 and subtly conveyed by the use of a sans-serif font rather than italics (this is a typographic convention of this particular document, not a common convention).
So for example the type judgement
$$
\alpha :: \ast, y :: \alpha \vdash (\mathsf{id} :: \alpha \rightarrow \alpha) \: y :: \rightarrow \alpha
$$
is also the type judgement
$$
\alpha :: \ast, y :: \alpha \vdash (\lambda x \rightarrow x :: \alpha \rightarrow \alpha) \: y :: \rightarrow \alpha
.
$$
It's a different notation for the same mathematical object.


Big O of multiple variables in a logarithm: is $(2n+m)\log(2n+m) = O((n+m)\log(n+m))$? I am computing the count of the amount of intersections between disjoint horizontal line segments and disjoint vertical line segments. The algorithm I have come up with runs in $(2n+m)\log(2n+m)$ time. I was wondering if the Big-O for this is $O((n+m)\log(n+m))$? I don't know how constants in the interior of logs with multiple variables could be bounded, if at all. How would I prove this?

Classical way is same as when we consider double limit $\lim\limits_{(n,m) \to \infty}f(n,m)=A$, which use intention to infinity by squares  i.e. for $\forall \varepsilon>0$ $\exists \delta>0$ such that for $\forall n > \delta$ and $\forall m > \delta$ holds $|f(n,m)-A|< \varepsilon$. Using maximum norm conception we can write $\left\Vert(m,n)\right\Vert = \max\{n,m \}> \delta$. It is also known Chebyshev norm and the infinity norm terms for this conception and notation $\left\Vert \cdot \right\Vert_\infty$. Let me say, that this is same as intention to infinity by rectangles i.e. when we require $\exists \delta_1>0, \exists \delta_2>0$ and consider $\forall n > \delta_1$ and $\forall m > \delta_2$.
Applying to big-$O$ we can write that $O(f(n,m)),(n,m) \to \infty$ is set of functions $g$, such, that $\exists C_g>0$ and $\exists M_g>0$ such that for $\forall \left\Vert  (n,m)\right\Vert_\infty > M_g$ holds $g(n,m) \leqslant C_g f(n,m)$.
In your case $(2n+m)\log(2n+m) \leqslant 2(n+m)\log [2(n+m)] \leqslant 4(n+m)\log (n+m)$ using $1+\frac{\log 2}{\log (n+m)} \leqslant 2$, when $n>1,m>1$.
For completeness let me also note, that definition from one variable can be expanded to two or multi  variables in different ways, for example, we can consider intention to infinity by circles i.e. when we consider $\sqrt{n^2+m^2} \to \infty$. Is known intention to infinity by triangles i.e. $n+m \to \infty $ etc.


How can unifying 2 sentences in first-order logic result in a variable becoming 2 different things? I'm working on a program which must use inference in first-order logic, and everything is working great except for 1 thing which I don't understand.

The book I'm using, "Artificial Intelligence A Modern Approach" by Russell and Norvig, shows a proof on page 349 which has me confused.
They combine the two following sentences:
~Loves(x,F(x)) v Loves(G(x),x)
~Animal(x) v Loves(Jack,x)
And they combine into:
~Animal(F(Jack)) v Loves(G(Jack),Jack)

This makes absolutely no sense to me because the variable "x" becomes both "F(Jack)" and "Jack", and that seems wrong to me.

Using the Unify function which I created by following the pseudocode provided in the book returns a failed substitution, but if the combination of the previously mentioned sentences is correct then what kind of substitution would need to be returned? (I know it's not just {x/Jack} because that would result in the sentence "~Animal(Jack) v Loves(G(Jack),Jack)", Animal would be missing the function F as shown in the example.)

Any help would be extremely appreciated!

The variables called x in the two sentences are not related. We can rename them to make it clear:

~Loves(x1,F(x1)) v Loves(G(x1),x1)
~Animal(x2) v Loves(Jack,x2)

Now when matching ~Loves(x1,F(x1)) and Loves(Jack,x2), you can see you'll get Jack/x1, F(Jack)/x2 and the final result as in the book.


Simplify Boolean expression The following Boolean expression is simplified into its minimal number of literals:
$$x'y' + yz +x'yz' \implies x'+yz.$$
How do you logically conclude this using the Boolean Laws?

$$
\begin{align*}
x'y' + yz + x'yz' &=
x'y' (z+z') + (x+x')yz +x'yz' &\mbox{(identity)} \\&=
x' y' z  + x' y' z' + xyz + x'yz + x'yz' &\mbox{(distributivity)} \\&=
x' y' z  + x' y' z' + xyz + x'yz + x'yz  + x'yz' &\mbox{(idempotence)} \\&=
x'(y' z + y' z' + y z + y z') + (x+x')yz &\mbox{(distributivity)} \\&=
x'+yz. &\mbox{(identity)}
\end{align*}
$$


How can mainstream OO languages support strong binary operations by classes? Section 24.2  in Types and Programming Languages by Pierce compares ADT and existential objects,in terms of how well they support strong binary operations:

  Other binary operations cannot be implemented without concrete, privileged access to the representations of both abstract values. For example,
  suppose we are implementing an abstraction representing sets of numbers. After scouring several algorithms textbooks, we choose a concrete representation of sets as labeled trees obeying some particular complex
  invariant. An eﬃcient implementation of the union operation on two sets
  will need to view both of them concretely, as trees. However, we do not
  want to expose this concrete representation anywhere in the public interface to our set abstraction. So we will need to arrange for union to have
  privileged access to both of its arguments that is not available to ordinary client code—i.e., the union operation must live inside the abstraction
  boundary. We call such operations strong binary operations.

and says strong binary operations can't be expressed as methods of existential objects:

  Strong binary operations, on the other hand, cannot be expressed as
  methods of objects in our model. We can express their types just as we
  did for weak binary methods above:

NatSet = {∃X, {state:X, methods: {empty:X, singleton:Nat→X,
member:X→Nat→Bool,
union:X→NatSet→X}}}

  . But there is no satisfactory way to implement an object of this
  type: all we know about the second argument of the union operation is
  that it provides the operations of NatSet, but these do not give us
  any way to ﬁnd out what its elements are so that we can compute the
  union.

but then says that mainstream OO languages provide support for strong binary operations by classes (instances of which are supposedly existential objects):

  The
  classes in mainstream object-oriented languages like C++ and Java are designed to allow some forms of strong binary methods, and are actually best
  described as a kind of compromise between the pure objects and pure ADTs
  that we have seen in this chapter. In these languages, the type of an object
  is exactly the name of the class from which it was instantiated, and this type
  is considered distinct from the names of other classes, even if they provide
  exactly the same operations (cf. §19.3). That is, a given object type in these
  languages has a single implementation given by the corresponding class declaration. Moreover, subclasses in these languages can add instance variables
  only to those inherited from superclasses. These constraints mean that every
  object belonging to type C is guaranteed to have all the instance variables
  deﬁned by the (unique) declaration of class C (and possibly some more). It
  now makes sense for a method of such an object to take another C as an argument and concretely access its instance variables, as long as it uses only
  instance variables deﬁned by C. This permits strong binary operations such as
  set union to be deﬁned as methods.

When a method in a class has an argument which is another object of the same class, how can the method "concretely access the instance variables" of the other object?

Does the book assume that the class makes the instance variables only privately accessible, and doesn't provide public accessible methods to access the instance variables? (I guess yes, because it seems to me that the third quote has the same situation as   the second quote where it be impossible for union method on existential objects.)

Thanks.

I will attempt an answer, though, the discussion in comments with @yuval-filmus seems to be going in the right way.

Let's recap: The book discusses ADTs against objects in their strictest sense.

ADTs are entirely public about their unique representation. Belonging in the ADT means satisfying said representation, and so binary methods can rightfully assume that both operands have that exact representation.

Objects are entirely opaque about their non-unique representation. Belonging in the object type means satisfying its interface, with no guarantees as to how this is achieved internally, and so binary methods may only assume that the two objects can respond to the same set of messages, but are quite possibly implemented entirely differently.

Even if the interface has a getter getFoo, that is no guarantee that the object has a foo field that you could poke at directly. Maybe some mock object is faking it with a method that returns a constant Foo. All you know as a client is that it supports a getFoo call.

Where the class-based object approach differs from the pure object approach is that the knowledge of the type of an object (the class it belongs to) gives you some guarantees about the structure of the object, and so, allows you to partially break the abstraction barrier.  Because all objects of a class must have been built with, at least, a call to the constructor of that class, you can guarantee the presence of some fields (initialized during that constructor), and so the language lets you access those directly, foregoing the mandatory message-passing of the pure object style.

This is a strength and a weakness:

because you have access to the concrete representation, you might be able to implement operations more efficiently,
but because you ask for a member of the class, a "mock" implementation is no longer a valid object for this operation: if you want to allow such an object, you must define an interface, and you are effectively back to a pure-object approach.

As in my other answer to one of your question, this paper is extremely relevant:

http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf
"On Understanding Data Abstraction, Revisited", by William R. Cook

Of particular interest are section 3.3 on autognosis, which hints at why binary methods in the ADT style are strong, whereas in the object style are weak, and section 5 which explains a bit the difference between what is considered a pure object approach and the more general objects available in Java. (You can program in the pure object style in Java, but you have to follow a given discipline about not breaking certain abstraction boundaries, which relates to the discussion you've had in the comments)

I hope this makes sense, I'm sorry you had trouble with my other answer, this is a hard topic to get your head around, but once you have fixed your misunderstandings you will see it is not that complex!


Cyclic tour minimizing total weight I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant.
I saw the question below on an old stack exchange question when looking to understand NP-completeness. At first, I thought I understood it so I gave it a go but ended up more confused than before (I'm a maths student and computational complexity is my first foray into CS and I'm struggling to get to grips with it).
Question is as below:

Given as inputs integers $a, b$ and $c(i,j)$ for each $i,j \leq a$, decide if there is a permutation $\tau$ of $\{1,2,\dots,a\}$ such that
$$
c(\tau(a),\tau(1))+\sum_{i=1}^{a-1}c((\tau(i),\tau(i+1))\leq b
$$
Prove this problem is NP-complete. Hint: find a reduction from the Hamiltonian circuit decision problem (given a graph, decide whether it contains a Hamiltonian circuit).

It seems very similar to the decision version of TSP (where given a set of cities with the distances between each pair of cities, and a length $k$, does there exist a circuit connecting all cities of length less than $k$).
I've read the proof for NP-completeness of TSP and I feel like I understand the reduction from Hamiltonian circuit decision problem to TSP, but I can't get it to translate into a reduction from HC to this problem.
My understanding to compare this to TSP, is that $a$ is the number of cities, each $c(i,j)$ represents the distance between city $i$ and $j$.
My (fairly poor) attempt at this reduction is as follows;
The problem is clearly in NP as we can non-deterministically "guess" a permutation and calculate the given sum and verify that it's at most $b$ in polynomial time.
Then, given a graph $G=\langle V,E\rangle$ where there are $a$ vertices, say $1,2,\ldots,a$, and $b$ edges of length $c(i,j)$, where $i \neq j$ and $i,j\leq a$, construct the completion of $G'$ of $G$ and a weight function that assigns any edge of $G'$ a 1 if the edge is present in $G$ and 2 if not. This can be computed in polynomial time.
Then if $G$ contains a Hamiltonian circuit (consisting of $b$ edges), this path has weight at most $b$ in $G'$ and so the sum of the lengths of this path is at most $b$ and so the permutation corresponding to the order of this path satisfies the original decision problem for these numbers $a,b$ and $c(i,j)$.
Conversely, if given the numbers $a,b$ and $c(i,j)$ and a permutation $\tau$ that satisfy the problem the associated graph G contains a path starting at $\tau(a)$ and finishing at $\tau(b)$. Thus G has a Hamiltonian circuit.
Thus HC reduces to this problem and hence it is NP-hard and so NP-complete.
I can tell it's wrong but I'm not sure how to properly describe a function relating to Hamiltonian circuits and lengths into weights in $G'$.
Any advice and or pointers would be much appreciated.

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


Computational complexity of finding a spanning tree in planar hybergraphs Using a bipartite graph to represent hypergraphs as described by Wikipedia :

  A hypergraph $H$ may be represented by a bipartite graph $BG$ as follows:
  the sets $X$ and $E$ are the partitions of $BG$, and ($x_1$, $e_1$) are
  connected with an edge if and only if vertex $x_1$ is contained in edge $e_1$
  in H.
  Conversely, any bipartite graph with fixed parts and no unconnected
  nodes in the second part represents some hypergraph in the manner
  described above. This bipartite graph is also called incidence graph.

Now if we assume that a hybergraph is planar if and only if it can be represented by a planar bipartite graph. What is the complexity of finding a spanning tree in planar hybergraphs? It is also ok if you can provide any source on how to approach this problem.

Note: It is known that the spanning tree problem of general hybergraphs is $NP$-complete, while spanning tree of $3$-uniform hypergraphs, where all hyperedges are of size $3$, has a polynomial algorithm using matroid matching [ref].

Note: Under the bipartite representation of hypergraphs the problem of spanning tree becomes equivalent to the problem of finding a subset of vertices that induces a tree such that the tree contains all vertices of one of the bipartitions of the bipartite graph. The problem is a bit similar to the Induced-Tree problem defined in this paper, but in this problem the induced tree must contain any set $S$ of vertices as part of the problem input. The Induced-Tree problem is $NP$-complete even for planar bipartite cubic graphs.

The answer is in this paper "Tree-Residue Vertex-Breaking: a new tool for proving hardness"

  The Hypergraph Spanning Tree problem in $k$-uniform $2$-regular
  hypergraphs is $NP$-complete for any $k≥4$, even when the incidence graph
  of the hypergraph is planar.

Basically, they define a new problem:

  Tree-Residue Vertex-Breaking (TRVB): given a multigraph $G$ some of
  whose vertices are marked "breakable," is it possible to convert $G$
  into a tree via a sequence of "vertex-breaking" operations (replacing
  a degree-$k$ breakable vertex by $k$ degree-$1$ vertices, disconnecting the
  k incident edges)?

Proving this:

  For any k≥4, TRVB is NP-complete when the given multigraph is
  restricted to be planar and consists entirely of degree-k breakable
  vertices.

You can see that solving TRVB for the incidence graph of a hypergraph corresponds to solving SPANING TREE in hypergraphs. Where the incidence graph of a hypergraph is isomorphic to the bipartite representation of the hypergraph described above.


What is the best way to algorithmically sort physical boxes? I work part time at UPS. Part of my job consists of taking boxes from in front of me, determining if the correct cage (1 of 6 moving cages) is behind me (true about 50% of the time), and then putting the box down either in the cage or back in front of me. There can be 6-20 boxes in front of me at any given time depending on box size (essentially the available storage for the sorting algorithm). Each time a box is removed it is replaced with another random box, if there is room for that box. If the next box is particularly large, 3-4 boxes may need to be removed first (meaning that removing a box does not guarantee a new box will appear unless the total number of boxes is sufficiently small). The number of boxes can be considered infinite (UPS does ship nearly all of Amazon’s boxes, after all).

I’m trying to figure out the best strategy for sorting these boxes, partially to work faster and partially for fun.

A few more details

2 boxes cannot be picked up at the same time (they can be up to 70 lbs). The boxes can, however, be slid sideways. This means a box can be picked up and inserted between other boxes, but two non-adjacent boxes cannot be swapped in a single movement.
Boxes can be stacked. However, the stack still needs to be put into the cages one by one. Stacking can reduce the number of comparisons needed (because you know all boxes in a given stack go to a certain cage), but not the number of movements required.
Boxes must be picked up to be evaluated
1 cage will disappear and a new cage will appear every 10 seconds, in a predictable order
If the correct cage is not behind me, I must either wait for the cage or set down the box on the shelf and select a new box

Computational time (seconds)

Picking up a box: 1
Evaluating a box: 2
Placing a box in its original location: 0
Placing a box in a new location: 1

Examples:

Picking up a box, determining that the correct cage is not behind me, and putting the box back where it came from: 3 seconds
Picking up a box, determining the correct cage is behind me, placing the box in the cage: 4 seconds
Picking up a box from a presorted pile and placing it in the correct cage: 2 seconds
Picking up a box and placing it in a cage without sorting: 2 seconds (plus the time to find a new job)

For context, the current rate is around 700 boxes per hour (5.14seconds/box). So reducing the average time per box by only 0.5 seconds is a fairly significant change.

What is the most time-efficient way to move the boxes from the shelf to the correct cage? Solutions to simplified versions of this problem are also welcome.

I'll analyze some basic strategies, show that always stacking is best in your model, and then discuss a more sophisticated strategy.

Analysis of basic strategies: never stack

The simplest strategy is one where you never stack boxes: when you pick it up, if it doesn't belong to a cage behind you, you put it back down where it was.  Heuristically, I expect the "never-stack" strategy requires an average of 7 seconds per box.  Not good.

Why?  We can model the number of times we pick up a box as a geometric distribution with parameter $0.5$; thus the average number of times you need to pick it up is 2.  You spend 3 seconds each time you pick it up, including the time to evaluate it; plus 1 second more to place it into the cage, for a total of $2 \times 3 + 1 = 7$ seconds.

I'm making an assumption here that might not be quite right... but it's probably in the ballpark.  Anyway, it suggests that "never stack" probably isn't a good strategy.

Analysis of basic strategies: always stack

The other extreme is to always stack boxes that can't be placed into the cage behind you.  I will assume that, as you specified in a comment, for each stacked box you perfectly remember what cage it belongs to, so once a box is stacked you never need to evaluate it again.

This strategy takes 5 seconds per box, which seems pretty good.  Why?  Look first at the boxes that end up getting stacked.  We've spent $1+2+1=4$ seconds for each box in the stack to move it into the stack, and we'll spend $1+1=2$ more seconds per box in the stack to move them all to their cage when it arrives, for a total of $6$ seconds per box.  50% of the boxes get stacked.  The total time per unstacked box is 4 seconds, and the total time per stacked box is 6 seconds, for an average time per box of $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Not bad.  The great thing about always stacking is that you avoid ever evaluating any box twice.

If we think about it a bit more, it appears that "always stack" is the optimal strategy: it's not possible to lower the time per box any further.  Once you've picked up a box and know it doesn't belong into a cage behind you, what are your options?  You can either stack it or not.  If you stack it, it'll take only 2 seconds more to deal with that box in the future.  If you don't stack it, it's guaranteed to take at least 3 seconds more to deal with it again in the future, no matter what, maybe more (1 second to pick it up again, 2 seconds to evaluate it).  So given your assumption that you memorize the cage number of each stacked box, but don't memorize the cage number of boxes that you didn't stack and put back in their original place -- always stacking is optimal.

So what's wrong with always stacking?  Why wouldn't you always want to stack?    Stacking does have a cost.  It requires enough shelf space for all possible stacks.  If shelf space is limited, that might potentially be an issue.  Also in practice if you make the shelf too large, then that'll presumably increase the time it takes to pick up boxes and put them down somewhere else (since you have to walk further to reach the place where the stack belongs), so eventually that will be counterproductive.  Also, the more stacks you have, the more the burden on your memory (since you have to remember the cage number for each stack), which presumably isn't realistic once the number of stacks gets too large.

So perhaps we should consider "shelf space" or "number of stacks" as a limited resource as well, and consider whether we can construct a strategy that is almost as fast as always stacking, but doesn't require as many stacks.  With that motivation, I propose a more complicated strategy, next.

More sophisticated strategy: limited number of stacks

I'll describe a possible strategy where we try to achieve close to the same efficiency as always stacking, but with a limit on the maximum number of stacks we'll ever have.  This allows a tradeoff between shelf space vs time spent per box.

Divide the shelf into two zones, an arrival zone and a holding zone.  Divide the holding zone into 10 regions, labelled 0-9.  Each region can hold one stack, so at any point we'll have at most 10 stacks.  New boxes show up at the arrival zone.  I will assume that the cages are numbered sequentially (e.g., currently cages $i,i+1,\dots,i+5$ are behind you and cage $i+6$ will be the next to appear, and cage $i+7$ will be the next after that, and so on).

At each step, pick up a box from the arrival zone.  You can pick any one arbitrarily.  Evaluate it.  If it belongs to one of the cages behind you, put it there.  Otherwise, if it belongs to one of the next 10 cages to appear, put it into the holding zone.  Select the region corresponding to the last digit of the cage it belongs to.  For instance, if it belongs to cage 176, put it in the region labelled 6 of the holding zone.

When a new cage arrives, go to the corresponding region in the holding zone, pick up all of the boxes and place them into the cage.  There is no need to evaluate any of them -- you already evaluated them and know which cage they belong in.

In this way, each box gets evaluated only once.  It'll either be picked up once and evaluated and placed into its correct cage immediately (takes $1+2+1=4$ seconds), or picked up once, evaluated, moved to a new location, then picked up again and placed into the cage (takes $1+2+1+1+1=6$ seconds).  You said about 50% of the time a box can go into its correct cage immediately, so we should expect that the average time per box is $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Now here's what I admit this is a little bit of a lie.  I oversimplified.  I assumed that if you pick up a package and it isn't in the cage behind you, then it will belong to one of the next 10 cages.  But what if it doesn't?  What if it belongs to a cage that won't appear until even further in the future?  This is the bad case.  In this bad case, all you can do in this strategy is put it back into the arrival zone.  Eventually, at some point in the future it'll be picked up again, and maybe then you can do something more productive with it.  The cost, though, is that this means occasionally a box will have to be evaluated more than once.

So in reality, the actual average time per box will be more than 5 seconds per box.  It might not be too much more.  But exactly how much more depends on how often you pick up a box and discover it belongs to a cage that won't appear for a long time (how often the bad case occurs).

Of course the number 10 (the number of regions in the holding zone) is arbitrary and can be tuned.  You can make it larger, to reduce how often the bad case arises; this will reduce the average time per box, at the cost of increasing the amount of shelf space you need.  Of course, in practice if you make the shelf too large, then that'll actually increase the time it takes to pick up boxes and put them down somewhere else, so eventually that will be counterproductive.  Alternatively, you can make that number smaller; this will reduce the amount of shelf space needed, at the cost of increasing the average time per box.

So I think this is worth a try.  Its effectiveness will depend on details of the distribution of when boxes arrived vs when their cage appears, which aren't specified in the question, but if you have data on that, you should be able to simulate this strategy and see how well it will work.

Second-level refinement of the above strategy

If you like this strategy, there is a refined version of it you could also consider.  The refined version is more complicated but might reduce time per box even a little further.  Divide the shelf into three zones, an arrival zone, a holding zone, and purgatory.  The holding zone is divided into 10 regions, labelled 0-9, as before.  Purgatory is also divided into 10 regions, labelled 0-9.

The scheme is exactly as before.  The only difference is what we do if you pick up a box and discover its correct cage is at least 10 cages into the future, but less than 100 cages into the future.  In that case, you put it into purgatory.  You place it into the region corresponding to the next-to-last digit of the cage it belongs to.  For instance, if you currently handling cages 112-117, and you pick up a box that belongs to cage 176, then you can't put it into the holding zone, but you can put it into purgatory; and you put it into the region labelled 7 of the purgatory.

Now, when a new cage arrives, do the same as before to move all boxes from the corresponding region of the holding zone into the cage.  Also, for every 10th cage that arrives -- in particular, when a cage arrives whose last digit is 5 -- go to the corresponding region in purgatory and sort all of those boxes into the cages or the holding zone.  About 60% of those boxes can be placed directly into a cage behind you, and the remaining 40% can go into the holding zone.

Again, there is nothing special about the numbers 10 here.  You can adjust the number of regions in the holding zone, and the number of regions in purgatory (they don't need to be the same number, either), to trade off shelf space vs time per box.  I don't know whether the extra complexity of this scheme will be worthwhile, but it's a natural extension to the idea above.


Can someone provide an introductory example of a certificate in complexity theory? Just stepping into complexity theory, I am befuddled by this notion of a certificate and can't find any utility of this concept.

From my understanding, a certificate is used when you are trying to ascertain whether a problem is NP...a problem is NP if you can verify a p-time solution exist or not (co-NP). I cannot see why you would need a certificate to perform this solution finding. And how is certificate different from "verification".

For example, if I were to try to prove whether all elements in a set is divisible by some number (say 3). Say I then brute force divide all elements by 3 and sees that indeed all elements in this set is divisible by 3. Now where in this process would a certificate come into play?

Also, how would you go about to physically construct a certificate?

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

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

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


Enforcing application layer consensus on top of a distributed consensus protocol If I understand correctly, the term "consensus" in distributed consensus algorithms means that all the participants ("peers") achieve a common understanding of some data value.  Different algorithms can handle different types of failures or misbehavior by some of the peers, network disconnections or partitions, lost messages, and so on.  For example, PBFT has the property that any small group of peers (less than a third) cannot prevent the remaining peers from achieving a common understanding of the data value.

BUT there is nothing in these algorithms that prevents any peer from setting the data to a value that they shouldn't set it to.  So "consensus" just means we all agree that the value has been set to X.  It does not mean we all agree that X is the correct value.

Is that right?  And, if so, is there some general research into how to enforce a set of application-specific rules about who is allowed to set the data to a given value?

For example, Bitcoin has a set of rules that ensure that only "valid" transactions are accepted by the network.  So, for example, Joe can't give Fred the same bitcoin that he's already given to Mary.  Joe can't give Fred a bitcoin unless someone else already gave Joe that bitcoin, or Joe earned that bitcoin by mining.  And so on...

So what we have in Bitcoin are a set of application-layer rules that make sense for money, and these rules are embedded in the distributed consensus protocol used by Bitcoin (i.e. blockchain and proof-of-work and the bitcoin reference implementation).

However, what if I have a different set of rules that make sense in MY application - how can I ensure that a distributed consensus protocol (e.g. PBFT) not only ensures consensus across all peers about what the data value is, handling various failures and misbehavior by peers, and ALSO ensures that only "legal" values are set by the peers.

For example, I might have rules like: The value can only increase - nobody is allowed to decrease it.  Except on Sundays, when it can be decreased, but must only be set to an even value.  Except peer P can set it to whatever value they want to.  And if the value=5, then peer Q is the only one who can change it.  And so on...  (Believe me, I have a real-world problem that requires this kind of complexity.)

Ideally, the rules would be expressed in a formal language, and the distributed consensus protocol would reject any attempts by any peers to change the data value in a way that does not conform to the rules.

Could I do this by implementing PBFT and adding in a check where each peer checks that a proposed new value is consistent with the rules, and then refusing to accept (possibly broadcasting a NACK) if the proposed change is not valid?

I'm wondering if this has already been studied.  Perhaps this is the same as the concept of "consistency" in a distributed database, but I don't want to use a database replication solution, because I want eventual consistency, not strong consistency, and I want the kind of fault-tolerance that PBFT provides.

Thanks!

Duncan

You've asked multiple questions here.  I'll answer the first one.

Typically consensus means that all the honest participants have the same view of the state of the system.  There's not necessarily a guarantee that this state is "correct" in any sense (some protocols might also provide that guarantee, but it is in some sense a separate or additional request).

Often there are some rules about what kinds of state changes are "valid" or "allowed", and the honest participants are also tasked with ensuring that every state transition is valid; they won't generate or request transitions that aren't valid, and they won't accept transitions from others that are invalid.  If you do this right then you get the additional guarantee that all the honest participants have the same view of the state of the system, and this state is valid.

There are multiple ways to define which states or transitions are valid.  One way is by defining a state machine (like a DFA) that represents which state changes are valid; then the protocol provides a distributed implementation of the state machine.

I'm not an expert, but if you want to get a more authoritative answer, you could read the literature about state machine replication.  It's probably worth reading the PBFT paper, which is presented as an instance of state machine replication.


Understanding the binary and hexadecimal representations of UTF-8 Here is a code point: U+091D. The symbol it represents in UTF-8 is झ. In hex the symbol requires three bytes: e0 a4 9d. But it looks like the number 091D requires two bytes. So why do we need three bytes to encode the symbol? Probably due to

  the restriction of the Unicode code-space to 21-bit values in 2003

Please see the beginning of the description section. OK, but why did they restrict the code-space to 21 bits?

I converted e0 a4 9d to binary, and the result is

  11100000 10100100 10011101

Then I converted 091D to binary and got

  00001001 00011101

The two binary results seems to have little in common. So how did 091D become e0 a4 9d?

Where the 21 bits come from: The idea of unicode is based on the Universal Coded Character Sets (short UCS). It's a concept for a 31bit character set ordered as a 4D hypercube where the first three dimensions use 8bit and the fourth uses 7bit. Per row there are $2^8$ characters. Per plane there are $2^8$ rows $=65.536$ characters. Per cube there are $2^8$ planes and there are $2^7$ cubes. Unicode decided to just use a mere 17 planes (the code space 0 - 10FFFF), which corresponds to the 21bits.

UTF-8 is a variable length encoding mostly used for encoding unicode. Variable length means that it uses 1 to 4 byte to represent a certain code point, depending on its number of significant bits.

The scheme looks as following:

1 byte: At most 7 significant bits. From U+0000 to U+007F.
Scheme: 0xxxxxxx.

2 bytes: At most 11 significant bits. From U+0080 to U+07FF.
Scheme: 110xxxxx 10xxxxxx

3 bytes: At most 16 significant bits. From U+0800 to U+FFFF.
Scheme: 1110xxxx 10xxxxxx 10xxxxxx

4 bytes: At most 21 significant bits. From U+10000 to U+10FFFF.
Scheme: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

In your example you have 12 significant bits and therefore the 3 bytes used for encoding.

For further details see https://en.wikipedia.org/wiki/UTF-8.


Why is my trivial reasoning for $PSPACE = PH$ wrong? If $\sum_i^p$ denotes $ith$ polynomial hierarchy. And $\sum_i TIME( T(n) )$ denotes set of languages accepted by $T(n)$ time alternating Turing machine $M$ whose initial state is labeled $\exists$ and sequence of choices leads $M$ to change at most $i-1$ times from states with one label to another.

Then I know $\sum_i^p= \cup_c\sum_i Time ( n^c)$. Then by taking summation on $i$ both sides we get $PH=\cup_i \sum_i^p=\cup_i\cup_c \sum_i TIME(n^c)=\cup_c\cup_i \sum_i TIME(n^c)=\cup_c \sum_i TIME(n^c)=\cup_c \ TIME(n^c)=AP=PSPACE$
where $AP=\cup_c ATIME(n^c)$ ie. set of languages having polynomial runtime using an alternating Turing machine.
Thus we get $PH=PSPACE$, which I know does not have a proof. I am misunderstanding something trivial, but cant figure out what ?

Alternating polynomial time allows for an unbounded number of alternations. In contrast, every level of the polynomial hierarchy only allows for a fixed number of alternations. Therefore your argument only shows that $\mathsf{PH} \subseteq \mathsf{AP}=\mathsf{PSPACE}$.


Reduction to complement of Accept Problem I am reducing a given Turing Machine to the complement of the known undecidable problem,
$$ Complement(A_{TM}) = \{ \langle M,w \rangle \mid M  \text{ is TM}, w \not\in L(M) \}$$

To this Turing Machine, known as SPARSE TM:
$$
SPARSE_{TM} = \{ \langle M \rangle \mid M \text{ is 1-tape TM}, |L(M)| \leq 1000\}
$$

Here is what I have so far, but I think I need help because one of the statements I make seems fishy.

Assume there is a TM S that decides the complement of the accept TM and a TM R that decides SPARSE. Then S looks like:

S = "On input `<M,w>`:
    Construct M':
        M' = "On input x:
            if x in L(M):  #Fishy statement
                accept
            else: reject
     Run R on <M'>
     if R accepts: accept; if R rejects: reject

This (if right) would then reduce the SPARSE TM and prove that it is undeciable, right? Any help would be appreciated.

When reducing $L_1$ to $L_2$, we need to come up with a computable mapping $f$ such that $x \in L_1$ iff $f(x) \in L_2$. We don't start with a Turing machine deciding $L_2$ and then construct one for deciding $L_1$, although this construction can easily be accomplished using the mapping $f$. The reason we refrain from doing so is that sometimes we already know that $L_2$ is undecidable, and yet there is merit in saying that $L_1$ reduces to $L_2$, since $L_1$ might have an even strong guarantee of "hardness"; this sort of thinking leads to classical recursion theory.

Regarding your construction, there are two problems: (1) it doesn't involve $w$, (2) when you write "if $x \in L(M)$", you actually mean "simulate $M$ on $x$"; this simulation could halt, or it could never halt. Generally speaking, when a Turing machine never halts, then we say that it rejects. See if this fits with what you were trying to accomplish.


Bounding the recurrence $f(n)=2f(n-1)+2f(n/2)$ I met a recurrence equation for my algorithm
$$ f(n) = 2\cdot \left( f(n-1) + f(\frac{n}{2}) \right)$$
with $f(1)=1$, $f(2)=4$, $f(3)=10$.

I guess it is $\Theta((2+\epsilon)^n)$, where $\epsilon$ ban be arbitrarily close to 0.
I want to have an asymptotic formula of $f(n)$. I do not know how to prove or disprove my guess.

For concreteness, let's assume that your recurrence is really
$$ f(n) = 2f(n-1) + f(\lfloor n/2 \rfloor) + f(\lceil n/2 \rceil). $$
Define $g(n) = f(n)/2^n$. Then
$$ g(n) = g(n-1) + 2^{\lfloor n/2 \rfloor + 1 - n} g(\lfloor n/2 \rfloor) + 2^{\lceil n/2 \rceil + 1 - n} g(\lceil n/2 \rceil). $$
In particular,
$$ g(n) \leq (1 + 2^{\lfloor n/2 \rfloor + 1 - n} + 2^{\lceil n/2 \rceil + 1 - n}) g(n-1). $$
Taking logarithms,
$$ \log g(n) \leq \log g(n-1) + O(2^{\lfloor n/2 \rfloor + 1 - n} + 2^{\lceil n/2 \rceil + 1 - n}). $$
We conclude that
$$ \log g(n) \leq O(1) + O(1) \sum_{m=c}^n [2^{\lfloor m/2 \rfloor + 1 - m} + 2^{\lceil m/2 \rceil + 1 - m}] = O(1), $$
where $c$ is some arbitrary starting point.
Therefore $\log g(n)$, and so $g(n)$, is bounded. Since clearly $g(n)$ is monotone increasing, we deduce that $g(n)$ tends to some constant $C$. We conclude that
$$ f(n) \sim C 2^n. $$


Non-integer $a$ in Master method According to CLRS the master method requires the recurrence to be of form $T(n) = aT(n/b) + f(n)$ where $a \ge 1 $ and $b > 1$ are constants and $f(n)$ is asymptotically positive.

This makes it sound like even $a \not\in \mathbb{Z}_+$ is a legitimate value of $a$ as long as $a \ge 1$.

I have trouble visualising what kind of an algorithm would have, say, $a = 1.5$. Can anyone provide an example of an algorithm with non-integer $a$?

The first thing that comes to mind would be a divide-and-conquer method where, for some reason, 50% of the time you only need to do one subproblem, and the other 50% of the time you need to do both subproblems.

The recursion for the average case runtime would be

$$ T(n) = 0.5 \cdot T(n/2) + 0.5 \cdot (2 \cdot T(n/2)) + f(n) = 1.5 \cdot T(n/2) + f(n) $$

(the fine print: this require some assumption of independence between the probability you have to do both problems and the runtime of the subproblems)

That said, the master theorem is for asymptotically solving recurrences. Not every recurrence solving problem is about the runtime of an algorithm.

Furthermore, there is no point in going out of your way to excluding cases. Insisting that $a$ is an integer doesn't simplify anything at all, so all it achieves is to make the statement (and proof too, probably) more complicated, and to frustrate those people who find a use for those cases anyways.


Possibility of using loops instead of traps Draw DFA for the language of all strings starting with $a$ and ending with $b$.
Now what I have done is

Here I used q3 as a trap.
But could I do this instead?

I have not used trap in the 2nd solution and used a self loop instead.

Your first DFA is minimal. To see this, for each pair of states $q_i \neq q_j$ we need to come up with a word $w$ such that $\delta(q_i,w) \in F$ and $\delta(q_j,w) \notin F$, or vice versa, where $F$ is the set of accepting states.
Here is such a list of words:

$q_0,q_1$: $\delta(q_0,b) \notin F$ and $\delta(q_1,b) \in F$.
$q_0,q_2$: $\delta(q_0,\epsilon) \notin F$ and $\delta(q_2,\epsilon) \in F$.
$q_0,q_3$: $\delta(q_0,ab) \in F$ and $\delta(q_3,ab) \notin F$.
$q_1,q_2$: $\delta(q_1,\epsilon) \notin F$ and $\delta(q_2,\epsilon) \in F$.
$q_1,q_3$: $\delta(q_1,b) \in F$ and $\delta(q_3,b) \notin F$.
$q_2,q_3$: $\delta(q_2,\epsilon) \in F$ and $\delta(q_3,\epsilon) \notin F$.


identities property of squaring functor? From page 31 of The algebra of programming :

  Next, consider the squaring functor $()^2: Fun \leftarrow Fun$ defined
  by

  $$ A^2 = \{(a, b) | a \in A, b \in B\} \\ f^2(a, b) = (f a, f b) $$

Functors are required to preserve identities and composition:

$$
F(id_A) = id_{FA} \\
F(f \circ g) = Ff \circ Fg
$$

The second property is easy:

$$
(f \circ g)^2 (a, b) = ((f\circ g) (a), (f\circ g) b) \\
(f^2 \circ g^2) (a, b) = f^2 (g (a), g (b)) = ((f\circ g) (a), (f\circ g) (b))
$$

But I can't figure out how the squaring functor preserve the identity property. Could anyone help?

Ok, I have worked it out:

$$
id^2 (a, b) = (id(a), id(b)) = (a, b) = id_{A^2} (a, b)
$$


efficiently minimizing quasiconvex function The problem is as follows: given black box access to a strictly quasiconvex (or unimodal) function $f$ on an interval, say [0, 1], query $f$ repeatedly at various points to find a subinterval containing the minimum. After $n$ queries to $f$, if the interval's length is reduced by a factor of $t$, the algorithm's score is $\sqrt[n]{t}$, which is the amortized factor by which each query to $f$ reduces the length of the interval.

For example, standard ternary search starts with $f(0)$ and $f(1)$, additionally queries $f(\frac{1}{3})$ and $f(\frac{2}{3})$, and obtains a subinterval with size $\frac{2}{3}$. It then iterates and each subsequent iteration starts with $f$ evaluated at the endpoints of the subinterval and reduces the subinterval's length by a factor of $\frac{2}{3}$. Thus the score is $\sqrt{\frac{2}{3}}$.

A better ternary search instead queries at $\frac{1}{2}-\varepsilon$ and $\frac{1}{2}+\varepsilon$ and iterates for a score of $\sqrt{\frac{1}{2}+\varepsilon}$.

An even better algorithm is "pentanary search", starting with $f(0)$, $f(\frac{1}{2})$, and $f(1)$ and querying $f(\frac{1}{4})$ and $f(\frac{3}{4})$ to obtain a subinterval that is the first, middle, or last half of $[0, 1]$. It then iterates. The key is that 3 points from each iteration can be used in the next. Thus the score is $\sqrt{\frac{1}{2}}$.

The best I know of, "golden search", starts with $f(0)$, $f(1)$, and either $f(1-\frac{1}{\phi})$ or $f(\frac{1}{\phi})$, querying for the other of those two, where $\phi$ is the golden ratio. The subinterval is either $[0, \frac{1}{\phi}]$ or $[1-\frac{1}{\phi}, 1]$ and 3 values from the previous iteration can be reused, achieving a score of $\frac{1}{\phi}$.

Can we do better than "golden search"? Do we know the optimal score for this problem?

Avriel and Wilde, in their article Optimality proof for the symmetric Fibonacci search technique, showed that Fibonacci search is optimal in the following sense: if you want to bracket the minimum in an interval of length $\delta$ using at most $k$ evaluations, then Fibonacci search maximizes the length of your initial interval.


Minimum unweighted anticlique (independent set) cover / partition Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously respects the constraint that no two overlapping intervals are put into the same row, but it is hard to read because the number of rows is $O(\mathrm{\#\,\,of\,\,intervals})$.

In general, I think the minimum number of rows can be calculated by finding the size of the largest clique in the graph whose nodes are intervals that has an edge iff two intervals overlap. Is there an efficient (polynomial-time, approximate if necessary) algorithm, that, given a set of integer intervals, returns a minimum sized partition of the intervals into "y-axis values" such that no two elements of a subset overlap?

I suspect this problem is equivalent to the following (but disregard this if you disagree): is there an efficient way to compute an exact vertex cover $C$ of an interval graph $G = (V, E)$ such that $\forall I \in C. I^2 \cap E = \emptyset$ and $|C|$ is minimized? It seems like this is closely related to the maximum independent set problem.

This is precisely the graph coloring problem. Each subset of $C$ is a color, and we are trying to prevent adjacent vertices from having the same color, while minimizing the number of colors used. According to these lecture notes there is a polynomial-time greedy algorithm for coloring interval graphs based on the fact that every interval graph has a perfect elimination ordering.


How to correctly define the ratio of an approximation algorithm? For a maximization problem $P$, I know that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|OPT|\ge |S| \ge \gamma\cdot|OPT|$ for $\gamma <1$ and $OPT$ the optimal solution for $P$.

Is there an alternative definition?

For example, can we say that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|S| \le \gamma\cdot|OPT|\le |OPT|$ for $\gamma<1$.

No, your definition isn't very useful. A $\gamma$-approximation algorithm is an algorithm that produces a solution which is not too bad compared to the optimal solution. In contrast, under your definition you are guaranteed to produce a solution which is somewhat worse than the optimal one.

Let's take as an example the maximum clique problem. Here is a $\gamma$-approximation algorithm for maximum clique under your definition: output an empty clique. This works for any $\gamma < 1$.

I suspect that what you intended to capture was that $\gamma$ is the "tight" approximation ratio of the algorithm. That is, you want $\gamma$ to be the supremal $\gamma$ such that the solution $S$ produced by the algorithm always satisfied $|S| \geq \gamma |OPT|$.

I just gave one definition of the tight approximation ratio, but here is another (equivalent) one. We say that $\gamma$ is the tight approximation ratio of the algorithm if the algorithm is a $\gamma$ approximation (under the usual definition), and for every $\epsilon > 0$ there is an instance on which the solution satisfies $|S| \leq (\gamma + \epsilon)|OPT|$. It's important here to include both parts of the definition.


Formally describing a new domain specific programming language I am about to implement a domain specific language for representation of social learning conventions. Part of the implementation is a formal description of a language - its 'calculus', symbols and logical expressions.

My approach would be to describe the language by describing its grammar but there are also concepts such as relations, dialogs, expectations that require more theoretic approach and the description of the logic.

I would like to ask for an example and a literature recommendation (papers, books) that would help me with this description. I feel relatively competent approaching this task so I am not asking for a total hand holding, but help from a theoretician in this area would be GREATLY appreciated.

There are two parts of the semantics you will need to describe:

static semantics: structure of well formed programs
dynamic semantics: meaning of running programmings

Static semantics usually take the form of type systems. I'd recommend looking at the books by Benjamin C Pierce and Robert Harper. Alternatively, you could write the rules of well-formed programs as a collection of (formal or informal) statements describing the validity conditions of your program. The formal approach taken by type systems provides a well-known framework for such specifications.

There are many formalisms for expressing the dynamic semantics to consider as your basis:

denotational semantics --- gives meaning  in terms of semantic domains
operational semantics --- gives meaning in terms changes to an abstract machine states
axiomatic semantics --- gives meaning in terms of assertions about the state of the machine
algebraic semantics --- semantics is defined in terms of algebraic laws.

There should be plenty of books out there on these topics. A good broad introductory one is
Nielson and Nielson's Semantics with Applications. A downloadable version is available from the authors' site.
There is also a newer edition, but I haven't seen it.

Within each of these, there are choices to make. For example, if you decide to use operational semantics, there are large-step semantics, small step semantics, semantics based on labelled transition systems, semantics based on rewriting logic.

In Composing contracts: an adventure in financial engineering,
Simon Peyton Jones et al gives denotational semantics to a financial DSL.
The Denotational and Static Semantics of a Domain-Speciﬁc
Language for Flow-Network Design by
Assaf Kfoury presents a denotational semantics for a flow network DSL
Andrei Lapets' thesis Algebraic Semantics of Domain-Specific Languages
discusses algebraic semantics of DSLs.
There are many more: this, that, one in terms of abstract machines, another one.

What kind of approach you should take will depend on what kind of language your DSL is, what kind of experience you have with designing semantics, and your personal preference.

Without any concrete details, I can help no further.


Need help understanding regular expressions I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗+(0+1)∗0

This is how I think it works:

The first and last 0 indicates where these two characters must be present. In other words, the string this expression describes must start and end with one 0. (0+1)* describes any combination of 0's and 1's (including none at all), and the plus in between each of these sets of brackets ((0+1)* +(0+1) *) describes a concatenation of these two strings. Therefore, this expression applies to any binary string that begins and ends with a 0.

If this is indeed how the expression works, wouldn't 0(0+1)*0 achieve the same thing?

(Also, is there a site I can check these sorts of expressions? I tried this expression in sites like regex101.com but it didn't work on any of them. This isn't important, I was just curious)

There are three standard regular expression operators: concatenation, alternation, and Kleene closure. (Note that we're talking about regular expressions in the formal mathematical sense, not the random collections of hacks which comprise typical regex libraries.)

These can be thought of as operators on (possibly infinite sets); alternation is set union, and concatenation of two sets is the Cartesian product; in this sense,
alternation and concatenation correspond to addition and multiplication. Alternation is generally written as $+$ (although $\mid$ is also common, because of its use in regexes) while concatenation is generally written without an explicit operator symbol, much the same as mulitiplication.

Kleene closure is a unary operator which produces the arbitrary application of any number of concatenation operations on the same set; in effect, an arbitrarily long concatenation of elements of the set. (It includes 0 concatenations, which is always the empty string.) Kleene closure is always written as a postfix $^*$.

As with algebra, there is a standard operator precedence; Kleene closure binds the most tightly, followed by concatenation, followed by alternation. If you need different binding, you can use parentheses. So $ab^*+cd^*$ should be read as $(a(b^*))+(c(d^*))$, much as you would read the algebraic expression $ab^2+cd^2$

So the expression you ask about:

$$0(0+1)^∗+(0+1)^∗0$$

is the union of two subexpressions: $0(0+1)^∗$ and $(0+1)^∗0$. The first of these is any binary string starting with $0$ and the second is any binary string ending with $0$, so the union is any binary string which starts or ends with $0$; in other words, any binary string which doesn't both start and end with $1$.


Trouble seeing the contradiction in diagonalization proof I've seen the proof on a pdf online, and I'm having trouble seeing the contradiction.
If $(\langle T\rangle,z)=w \in D$, so when we emulate $T(w)$ with $U$ (universal machine), it accepts within the time bound,  so $M_D(w)=1$ and also $T(w)=1$.
Aren't you supposed to define $D$ as above, but accept only $x=(\langle M\rangle,z)$ where $M$ rejects $x$ within the time bound?

There is no contradiction, and the proof does not hold water. You are right: 'accepts' should be changed to 'rejects', and $D$ should be defined as

$$D=\{\langle M, x\rangle \quad | \quad M \underline{\underline{\text{ rejects }}}\langle M, x \rangle \text{ within }n\log(n) \text{ steps} \} $$

with $n=|\langle M, x\rangle|$, the length of the input. This way, the proof goes according to plan:

Proof. Suppose a $an+b$-time machine $T$ solves $D$. Take a sufficiently long $x$. Does $T$ accept input $\langle T, x\rangle$?

Suppose yes. Then $T$ accepts its input $\langle T,x\rangle$ within $an+b$, so $T$ accepts within $n\log(n)$. That's a contradiction, because by definition of $D$, $\langle T,x\rangle \in D \implies T \text{ rejects } x$.

Suppose no. Then $T$ rejects its input $\langle T, x\rangle$ within $n\log(n)$ steps, so $\langle T, x\rangle$ should be an element of $D$, so $T$ should have accepted. Contradiction $\square$


How close are common programming languages to not being Turing complete? The term "Turing completeness" has been discussed in several of the Computer Science classes that I've taken. However, I've never gotten an intuitive feel for what Turing completeness actually requires. I found this question, but the answers are a bit more mathematical than what I am looking for.

Take a common programming language, such as C++, Python, Java or Lisp. How close are these languages to being not Turing complete? Do these languages have elementary features that if removed would make the language not Turing complete? Or could you change a property of the language (for example, making something random) and by doing that make the language not Turing complete?

Common programming languages are very firmly Turing-complete, if you take an idealized view where programs can use an arbitrary large amount of memory. There typically isn't a single feature that you can isolate without which the language wouldn't be Turing-complete.

Intuitively speaking, Turing completeness requires two things:

A way for programs to manipulate an amount of memory that doesn't solely depend on the size of the input. Any form of object creation that can build bigger objects from smaller objects is suitable: objects, structures, pairs, lists, malloc, new, etc. Even stack-based allocation is enough provided that there is a way to access objects at any distance from the top of the stack (with only stack-based allocation and only access to the top of the stack, you only get a pushdown automaton). Many weaker forms of data manipulation are also suitable: for example, in a language like Lisp or Python where integers don't have a limited size, the basic integer operations alone are enough for Turing completeness.
A way for programs to keep running or halt based on some part of the data. While loops, recursion plus some form of conditional (e.g. if or case/switch) and goto plus some form of conditional are the three common ways, but there are others.

I think that the best way to understand what makes a language Turing-complete is to look at examples of languages that are powerful, but not Turing-complete. I'll give two examples that illustrate the two main families of such languages (other than languages that operate in bounded memory).

Consider an imperative language with integer operations and arrays, but only for loops (for i = 1 to n, where i cannot be modified during the loop), not arbitrary (while) loops and no recursion. BlooP and early versions of FORTRAN are examples. In such a language, you can only express primitive recursive functions — functions where the amount of computation is bounded in the size of the input. The language is not Turing-complete — cannot express arbitrary recursive functions — because of the bound on computation time.

A functional language can be made non-Turing-complete by restricting recursion through a type system that restricts all functions to be terminating. If the type system is decidable (i.e. if it is decidable whether the program is well-typed), then such a language cannot be Turing-complete (because the halting problem is undecidable). Languages used for theorem proving, such as Coq and Agda, are of this kind.

See also What can Idris not do by giving up Turing completeness?

On a side note, theorem provers require the user to input termination proofs (i.e. they don't find them themselves). So you could make a theorem prover with an undecidable type system: if you get a correct proof accepted, you're happy, otherwise you give up after a while. But it wouldn't be user-friendly. Most theorem provers have a decidable type system: you enter a term, and either it's accepted or you get a type error back. What theorem provers don't have is decidable type inference: if you type a term with partial type information and it's rejected, you don't know whether it's because the term cannot be typed or because the inference engine wasn't smart enough.


Recurrence for quaternary search algorithm I have to come up with the recurrence for the quaternary search algorithm.

My initial thought is $T(n)=4T(\frac{n}{4})+c$ because the algorithm examines all four subproblems, and each is one quarter the size of the entire array. But this can't be right because that yields a complexity of $O(n)$. I looked on Google and the complexity of quaternary searches are supposed to be $\log_4n$, but I don't know what the recurrence would be to get me that complexity.

Any help would be greatly appreciated. Thanks!

Your recurrence is wrong, which is why you get the wrong answer. I suspect that the reason your recurrence is wrong is that you don't quite understand the algorithm. Try mimicking your reasoning on binary search until you successfully get the correct running time in that case.

Moreover, as mentioned in the comments, the running time (assuming constant-time comparisons and the RAM machine model) is $\Theta(\log n)$, but cannot get more accurate than that. To get $\log_4 n$ you need to count something more specific, such as the number of comparisons performed by the algorithm.