Termination in infinite-time Does it make sense to speak of algorithms that take an infinite amount of time to terminate?

In particular, suppose we have a loop with a bound function that is initially positive and is decreased by the loop body each time. Furthermore, suppose that termination of the loop implies that bound function is non-positive. (Ie almost all assumptions of The Invariance Theorem are satisfied.)

Here's the rub, initially the value of the bound function is the cardinality of the natural numbers.

What can be said in such situations?

Any help or direction is most welcome; thank you!

A big thing that is studied in higher type computability is infinite streams. Others have talked about hyper computation but this isn't quite the same. For starters the objects and functions studied in higher type computability are all things you can do in Haskell or some other such real programing language. These functions DO terminate in finite time thanks to laziness.

Exact real arithmetic is arithmetic that is performed on infinite binary streams or other kinds of infinite streams (dyadic digits and more commonly having both negative and positive digits). Addition of such streams terminates in finite time but produces another object which is infinite. The trick here is that the infinite streams are definable by computable functions that have finite construction. It turns out that classically there exist certain infinite streams that we can't define. For instance a computable real on the range $[0, 1]$ can be defined by a function $f : Nat \to Bool$. If we have an undecidable set $S$ then if we consider $f(x) = 1$ if and only if $x \in S$ then $f$ defines a real number but NOT a computable real number. It seems to turn out that there are no natural examples of such numbers coming up in practice however.

For more information take a look at one of my favorite blog posts: seemingly impossible functional programs


Is model checking PSpace-hard *in formula size*? Sistla/Clarke proved [SC82] that the LTL model-checking problem is PSpace-complete.
Sometimes people write that this problem is "PSpace-hard in $|\phi|$" (e.g. [LP85]). What does this mean formally?

How to prove that a decision problem that has several parameters (here, $\phi$ and system) is PSpace-hard in one of the parameters? I guess we would need to poly-time reduce some PSpace-complete problem to our problem with the unintereseting parameter being fixed, while the interesting parameter can vary.

But the original proof of Sistla/Clarke [Lemma 4.4, SC82] does not do the thing above! In their proof, both parameters of the resulting LTL model-checking problem instance depend on $n$, where $n$ is the TM tape bound. Is there a proof that fixes one of the parameters?

You are certainly right that the level of rigor found in old papers making such claims can be a bit low at times when viewed from today's perspective.

The claim is correct anyway, even if it does not follow from Sistla/Clarke's proof. The reason is that LTL satisfiability checking is also PSPACE-complete. You can see satisfiability checking as a special case of model checking.

More formally, you want to prove the following: There exists a fixed model such that given an LTL formula, checking if the formula holds on the model is PSPACE-hard. Now the satisfiability checking problem does not restrict the number of atomic propositions, so a fixed model does not do the trick. However, S. Demri and P. Schnoebelen show in the paper "The complexity of propositional linear temporal logics in simple cases" (Inf. Comput., 174(1):84–103, 2002) that the satisfiability problem is hard even if we only have a single atomic proposition.


Linear Discriminant Method as Pre-processing for inputs going into a Neural Network? As the title suggests, I am curious whether Linear Discriminant Method can be performed on a dataset as pre-processing before putting the reduced-dimensional data as input for a neural network for creating the mapping function/ surrogate model.
Thanks!

This is not a useful method.  LDA is basically a two-class classifier, which works under certain assumptions on the distribution of the data.  If those assumptions hold, LDA is optimal and there is no reason to use a neural network.  If those assumptions don't hold, LDA might not be a useful tool.  Even if you do use LDA, LDA maps each data point to one of two classes, so there is no information left for the neural network to do any further processing.
In short: LDA is not useful as a preprocessing step before a classifier; you either use LDA as the classifier itself, or you don't use LDA at all.


Analysing the algorithm of a language called CONNECTED in Sipser to show that it belongs to class P The question and its answer is given in the following picture:

But I do not understand why stage 2 causes at most $n+1$ repetitions, and why stage 3 uses at most $O(n^2)$ steps, and I understand that the algorithm runs in $O(n^4)$ time not $O(n^3)$ as written, am I right?

Step 2 causes at most $n$ repetitions since each repetition other than the last one marks a node which wasn't previously marked. Since there are only $n$ nodes and one of them is marked in Step 1, there are at most $n-1$ repetitions which mark a new node, and one more which doesn't (and so moves to Step 4).

In Step 3, we go over all nodes in $G$ ($n$ nodes), and check all its neighbors ($n-1$ neighbors), so there are at most $n(n-1)$ repetitions of the inner part.

As for how many steps does this take when implemented on a Turing machine, this depends on the implementation. Outside of introductory courses on theory of computation, we almost never consider Turing machines, preferring instead to work with more intuitive models such as the RAM machine. Therefore mastering the intricacies of Turing machine behavior is not so important.


Equivalence of independent set and set packing According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent.

The Independent Set search problem is: given a graph $G(V,E)$ and an integer $n$, find $n$ vertices no two of which are adjacent.

The Set Packing search problem is: given a finite collection $C$ of finite sets and an integer $n$, find $n$ sets that are pairwise disjoint.

I think they are equivalent based on the following bidirectional reduction:

→: Given an independent set problem on a graph $G(V,E)$, create a collection of $C$ of sets, where for each vertex $v \in V$ there is a set $S_v \in C$ containing all edges adjacent to $v$. Now, every set packing in $C$ corresponds to a set of vertices no two of which have an edge in common, i.e., this is an independent set in $G$ of the same size.

←: Given a set packing problem on a collection $C$, create a graph $G(V,E)$ where for every set $S \in C$ there is a vertex $v_S \in V$, and there is an edge between $v_{S_1}$ and $v_{S_2}$ iff the sets $S_1$ and $S_2$ intersect. Now, every independent vertex set in $G$ corresponds to a set of sets from $C$ no two of which intersect, i.e., this is a set packing in $C$ of the same size.

My question is: is my reduction correct? If so, are these problem equivalent? Is it possible to use approximation algorithms for one problem on the other problem?

The exact meaning of "equivalent" isn't obvious but you have shown something deeper than the normal equivalence under reductions considered for NP-complete problems.

You've demonstrated what's known as a parsimonious reduction between the two problems.  Ordinarily, reductions between NP-complete problems are many-one reductions: they only have the property that problem A has a solution if, and only if, problem B has a solution. For example, when you reduce 3SAT to 3-Colourability, you produce a graph $G$ that is 3-colourable if, and only if, the original formula $\varphi$ is satisfiable. However, if $\varphi$ has $N$ variables, the number of satisfying assignments could be anything between zero and $2^N$, inclusive, whereas the number of 3-colourings of any graph is a multiple of six because of permutations of the set of colours.

The point about parsimonious reductions is that they're one-to-one. Your reduction sets up a bijection between solutions of the independent set problem and solutions of the corresponding set packing problem. Parsimonious reductions are useful because they preserve optimization and (approximate) counting versions of the problem. So your reduction also shows that the problem of finding the biggest independent set is as hard as finding the set packing using the most sets and that the problem of counting all the independent sets is as hard as to counting all the set packings.

There is a wider class of reductions that also preserve counting and approximate counting. These are the approximation-preserving reductions of Dyer et al. [1]. These are oracle reductions and relax the one-to-one requirement of parsimonious reductions to what is, essentially, "If you know (an approximation of) one, you can easily compute (an approximation of) the other." In particular, AP reductions can easily deal with the factor of $q!$ that's inherent in any reduction to the $q$-colouring problem.  As the name suggests, AP reductions preserve approximability, in the sense that, if there's an AP-reduction from A to B and there's an FPRAS for B, then there's an FPRAS for A, too.

[1] Dyer, Goldberg, Greenhill, Jerrum. The relative complexity of approximate counting problems. Algorithmica 38(3):471–500, 2003. DOI; free PDF


How did they cancel out O-terms in this fraction? While reading a book about algorithms, I came across this derivation:

$$
\frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)} =
\frac{2\ln(2N) + O(1)}{\ln N+O(1)} =
2 + O\left(\frac{1}{\log N}\right).
$$

Could somebody please explain to me how we went from the left to the right?

First, let me mention that judging from the final result, in this context $O(f(N))$ means a function $g(N)$ such that $|g(N)| \leq Cf(N)$ for some $C>0$ and all $N$.

The first step is simple: we divide both numerator and denominator by $2a_0 N$. This gives us
$$
\frac{2\ln(2N) + O(2N)/2a_0N}{\ln N + O(N)/2a_0N}.
$$
Now if $f(N) = O(N)$ then $f(N)/2a_0N = O(1)$, since $2a_0$ is a constant. This is how we get to the second fraction.

Getting to the final expression takes more work. First, notice that
$$
\frac{2\ln(2N) + O(1)}{\ln N + O(1)} = \frac{2\ln N + O(1)}{\ln N + O(1)},
$$
since $2\ln 2$ is a constant. Denote now by $B(N)$ the $O(1)$ function in the numerator, and by $C(N)$ the $O(1)$ function in the denominator. Then
$$
\frac{2\ln N + B(N)}{\ln N + C(N)} =
2 + \frac{B(N) - 2C(N)}{\ln N + C(N)} = \\
2 + [B(N) - 2C(N)] \frac{\ln N}{\ln N + C(N)} \frac{1}{\ln N} = \\
2 + [B(N) - 2C(N)] \left(1 - \frac{C(N)}{\ln N + C(N)}\right) \frac{1}{\ln N}.
$$
We need to show that the second term is $O(1/\log N)$. By definition, $|B(N)-2C(N)|$ is bounded by some constant. The same can be said about the second factor, since it tends to 1 as $N \to \infty$. Hence the entire second term is bounded in absolute value by a constant times $1/\ln N$, i.e., it is $O(1/\log N)$.


how do you define functions with denotational semantics? Denotational semantics are abstract functions that give meaning to statements of a programming language. They accept an expression and return a value.

But how do you define denotational semantics for languages that define, for example, functions (and later use these functions), or global variables, and change some global state of the program?

I think the simplest way to do it would be to define the semantics function so that it returns a pair of values and a "global state" instead of just a value.

But is there a place I can read about it some more? I am sure someone have done something like that. For example, is there denotational semantics for languages like Java or C?

It would be nice to find a book that focuses on denotational semantics for programming languages which are not necessarily purely functional (though I think functional languages, like LISP, can also change a global state).

People have been writing denotational semantics for all kinds of
languages since the late seventies.  The list must now be quite long,
and include large real languages, but I never tried to check what is in
it. The number of books is probably large too.  What you want is to look at toy
examples.  Anything real is not a good idea for a start. Some are probably in (text)books.

There were some references to such examples in A simple programming language?
You may try it ... I did not check the answers.

In some cases people had to write a formal semantics because they
wanted to prove correctness of the compiler. Still much research on this.

  Denotational semantics are abstract functions that give meaning to
  statements of a programming language. They accept an expression and
  return a value.

Well, only in the sense that any well formed program fragment may be seen syntactically as an expression (a formula), and anything may be seen as a value in
denotational semantics, including functions (values belong to domains ... which you can understand approximately as types). Actually the semantics
function takes a syntactic formula (you can read "formula" as
"abstract syntax tree") and returns a function expressing what that
formula is supposed to mean ...  or to do when run as (part of) a complete
program.

How you write the semantics, and what domains you use is highly
dependent on what kind of features exist in you language. For example,
if you have exceptions, things may get a bit more complicated.

But just try toy examples to begin with.  And then more.


Minimal complexity for pairing two comparable sets with comparability restrictions A project at university (whose deadline has passed by now) presented the following problem:

  Consider two finite sequences of (not necessarily distinct) real
  numbers $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ such that the $b_k$'s
  are a permutation of the $a_k$'s. The aim is to create an algorithm
  which returns a permutation which maps the sequence $(a_k)$ onto
  $(b_k)$. In order to find such permutation it is necessary to compare
  some numbers during the algorithm. The restriction is that one cannot
  compare any $a_x$ with an $a_y$ or a $b_x$ with a $b_y$: all that is
  allowed is to compare a number of the first sequence with one of the
  second sequence.

I am wondering what would be the minimal (worst-case) complexity of the number of comparisons. It's not hard to get $O(n^2)$: for every $a_x$, search brute-force for a corresponding $b_y$, which costs $O(n)$ comparisons giving a total of $O(n^2)$.
A bit smarter would be to adapt the familiar QuickSort algorithm, in the recursions step taking as a pivot a couple $(a_x,b_y=a_x)$ (which can be found in $O(n)$ comparisons) and partitioning both sequences using this 'pivot'. This gives $\Theta(n\log n)$ comparisons in average, but still $\Theta(n^2)$ worst-case (as usual with QuickSort).

It's not hard to see that $\Omega(n\log n)$ is a minimum: represent a given algorithm as a binary decision tree with a comparison at each node. Since the total number of leaves can reach $\Theta(n!)$ (the number of permutations in case all the $a_k$ are different) the height of the tree is at least $\Omega(\log_2(n!))=\Omega(n\log n)$.

It seems likely that a $O(n\log n)$ algorithm exist, but I have not been able to find one. I have tried adapting MergeSort, but a problem during the merging arises giving a worst-case of $\Theta(n^2)$ nonetheless.

Is this a known problem? Does a $O(n\log n)$ algorithm exist? Do you have suggestions for other known sorting algorithms which might be adapted without increasing their complexity?

This is the famous "nuts and bolts" problem.  Yes, there is a randomized algorithm with expected running time $O(n \lg n)$, using a QuickSort-like algorithm.

The problem is famous because there is a simple randomized algorithm that achieves $O(n \lg n)$ expected running time.  However, it's very challenging to find a deterministic algorithm with a $O(n \lg n)$ time running bound.  Therefore, it makes a nice illustration of the utility of randomness.

The problem is described in several algorithms textbooks, including CLRS and Skienna's textbook.


How to remember NFA's choice on a certain computation? I'm working on solving the question answered at this page but with different values at the table, my alphabet is {a,b,c}
Words that have the same right- and left-associative product

Currently I'm in the stage where I have drawn the DFA of the multiplication table, found its reverse which was an NFA.

Here is the NFA I got by reversing the multiplication table's DFA

I apology for the miss draw, but I hope its readable.

Now I have taken the input "abcb" and applied it on the above NFA, and I have gone through this tree

As you can see here that the input is all consumed at the branch "C" and I could reach the Final State. Would someone elaborate to me how can I backtrack from that branch which is "C" in this case and indicate that the "C" is the state which shall be marked as the Final State my NFA?

Hint: Let the input be $x_1,\ldots,x_n$. As you mention, it is easy to compute the left-associative product $L_n$ "as you go": $L_{m+1} = L_m x_{m+1}$. The right-associative product recurrence has the wrong direction: $R_m = x_{m+1} R_{m+1}$. To cope with that, at each step you have to guess the value of $R_{m+1}$; it needs to be a value which conforms to your earlier guess of $R_m$ and to the value of $x_{m+1}$. At the end, compare your initial guess of $R_1$ to the value of $L_n$. Arrange things so that you only need to keep track of finitely many values of products.


3-SAT reduction to jobs scheduling problem (np-completeness) In this paper with the title of "NP-Complete Scheduling Problem" by J. D. Ullman, I am trying to understand the reduction from 3-SAT problem to a scheduling problem in order to prove the later is also np-complete. An instance of 3-SAT is given as below:

and this is the instance of the scheduling problem defined as: Single Execution Time Scheduling Problem with a variable number of processors.

I can not totally understand the mapping between the two problems. Any hints that could help me getting the idea?

I see that you have posted this question before with no luck, and I think that this might be due to the amount of work needed to the answer such an open question. I looked at it also when you posted the first time, but needed a couple of hours to read through the proof and would have needed another couple of hours if I should have written a clear explanation for you (I know you are just asking for hints, but they are hard to give when I do not know which parts you already understand and which you don't). I at least, for one, would have been more inclined to write you an answer if you had asked more specific questions to the reductions, like e.g. what a role of a certain job is, or the like.

Also, your question does not contain all the info needed to answer, so one has to download the paper to find the relevant information oneself, and many people probably never go to that step, even when they are actually able to answer. You should have posted at least the definition of P4 and the time limits, and preferably also the example you posted in your last post, but with the explanation of the example and not just the table.

But, alas, after all this explanation of why you might not have gotten any answers, I really like these puzzle-y reductions so seeing that you posted again I made this little picture that can hopefully be of some help.

If you have questions after this, you are very welcome to write some (specific) questions, and I shall see if I can answer.


Decidable properties of computable reals Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true?

Does this correspond in some direct way to the connectedness of the reals?

Yes, Rice's theorem for reals holds in every reasonable version of computable reals.

I will first prove a certain theorem and a corollary, and explain what it has to do with computability later.

Theorem: Suppose $p : \mathbb{R} \to \{0,1\}$ is a map and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then there exists a Cauchy sequence $(x_i)_i$ such that $p(\lim_i x_i) \neq p(x_j)$ for all $j \in \mathbb{N}$.

Proof. We construct a sequence of pairs of reals $(y_i, z_i)_i$ as follows:
\begin{align*}
(y_0, z_0) &= (a, b) \\
(y_{i+1}, z_{i+1}) &=
\begin{cases}
(y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\
((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\
\end{cases}
\end{align*}
Observe that for all $i \in \mathbb{N}$:

$p(y_i) = 0$ and $p(z_i) = 1$
$|z_i - y_i| = |b - a| \cdot 2^{-i}$
$|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
$|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Thus the sequences $(y_i)_i$ and $(z_i)_i$ are Cauchy and they converge to a common point $c = \lim_i y_i = \lim_i z_i$. If $p(c) = 0$ then we take $(x_i)_i = (z_i)_i$, and if $p(c) = 1$ then we take $(x_i)_i = (y_i)_i$. $\square$

Corollary: Suppose $p : \mathbb{R} \to \{0,1\}$ and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then every Turing machine either runs forever or it does not run forever.

Proof.
By the theorem, there is a Cauchy sequence $(x_i)_i$ such that $p(x_j) \neq p(\lim_i x_i)$ for all $j \in \mathbb{B}$. Without loss of generality we may assume that $p(x_j) = 1$ and $p(\lim_i x_i) = 0$.

Let $T$ be a Turing machine. Define a sequence $y_i$ by
$$y_i =
\begin{cases}
x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\
x_i & \text{if $T$ does not halt within $i$ steps}
\end{cases}
$$
The sequence is well-defined because we may simulate $T$ up to $i$ steps and decide whether it has stopped or not within that many steps. Next, observe that $(y_i)_i$ is a Cauchy sequence because $(x_i)_i$ is a Cauchy sequence (we leave this as an exercise). Let $z = \lim_i y_i$. Either $p(z) = 0$ or $p(z) = 1$:

if $p(z) = 0$ then $T$ runs forever. Indeed, if it stopped after $j$ steps, then we would have $z = x_j$, and so $p(z) = p(x_j) = 1$ would contradict $p(z) = 0$.
if $p(z) = 1$ then $T$ does not run forever. Indeed, if it did, then we would have $z = \lim_i x_i$, and so $p(z) = p(\lim_i x_i) = 0$, contradicting $p(z) = 0$.
$\square$

Now we can explain why this gives us Rice's theorem for real numbers. The proofs are constructive, therefore they yield computable procedures. This is true of any model of computability and any compute structure of reals that deserve to be so called. In fact, you can go back and read the proof as instructions for building a program -- all the steps are computable.

Thus, if we had a computable map $p : \mathbb{R} \to \{0,1\}$ and computable $a, b \in \mathbb{R}$ such that $p(a) = 0$ and $p(1) = 1$, then we could apply the computable procedures arising from the constructive proofs of the theorem and the corollary to create the Halting oracle. But the Halting oracle does not exist, therefore, every computable map $p : \mathbb{R} \to \{0,1\}$ is constant.

Supplemental: There was also a question about whether Rice's theorem is related to connectedness of the reals. Yes, it is essentially the statement that the reals are connected.

Let us first observe that a continuous map $p : X \to \{0,1\}$ (we take the discrete topology on $\{0,1\}$) corresponds to a pair of disjoint clopen (closed and open) sets $U, V \subseteq X$ such that $U \cup V = X$. Indeed, take $U = p^{-1}(\{0\})$ and $V = p^{-1}(\{1\})$. Because $p$ is continuous and $\{0\}$ and $\{1\}$ are open, $U$ and $V$ will be open, disjoint, and they obviously cover all of $X$. Conversely, any pair $(U,V)$ of disjoint clopens that cover $X$ determines a continuous map $p : X \to \{0,1\}$ that maps elements of $U$ to $0$ and elements of $V$ to $1$.

From this we learn that a space $X$ is disconnected if, and only if, there exists a continuous map $p : X \to \{0,1\}$ and $a, b \in X$ such that $p(a) = 0$ and $p(1) = b$ (we need $a$ and $b$ so that we get a non-trivial decomposition of $X$). There is another way to say the same thing: a space $X$ is connected if, and only if, all continuous maps $X \to \{0,1\}$ are constant.

In computable mathematics we have a basic theorem: every computable map is continuous. So, as long as we are within the realm of computable objects, Rice's theorem does in fact state that a certain space is connected. In the case of the classic Rice's theorem the space in question is the space of partial computable functions $\mathbb{N} \to \mathbb{N}$.


2D peak reasoning to move to a half You have a 2D integer matrix given. An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A[i][j] are A[i-1][j], A[i+1][j], A[i][j-1] and A[i][j+1]. For corner elements, missing neighbors are considered of negative infinite value.

If someone has any understanding please share on how it decides which side to pick as that reduces complexity to $O(n \log n)$.

Solution is to consider the middle column, find its 1d maximum, then if it's not the peak, look at left and right side and pick a side which is larger. My doubt is, why is this algorithm correct?

Related material:

A) geeks link:
https://www.geeksforgeeks.org/find-peak-element-2d-array/

B) mit
This was shared in mit slides where it talks about 1d peak and then 2d peak
1)  https://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

2) its second link gives an working example but not the reasoning
http://courses.csail.mit.edu/6.006/fall11/lectures/lecture1.pdf
shows a working

C) Stackoverflow
There is also a StackOverflow discussion
https://stackoverflow.com/questions/23120300/2d-peak-finding-algorithm-in-on-worst-case-time

My doubt is How Can it predict based on seeing left and right element accurately that it has to go to the bigger half. I tried it a lot of times and it always works. So  I know it to be true. I then tried to create a counter example but I couldn't .

It's a very old question :
I initiated a chat but it didnt helped so asking question here : https://chat.stackoverflow.com/rooms/192196/2d-peak

The point is that we are not trying to find the global maximum element of the array, only a peak (that is, a local maximum).

Let's say that you look at the middle column and find its global maximum, and this maximum is not a peak, because the value to its left is larger. Then you know that the left half of the matrix contains a value that is larger than all of the elements of the middle column. Hence there is always a peak in the left half (for example, the global maximum of the left half, but we do not necessarily search for that).

The values in the right half are irrelevant; they could be larger or smaller, but we don't care. We only want to be sure that we do not recurse into a half that contains 0 peaks.


Decimal to Binary converter with a flaw Hi I wrote the following recursive decimal to binary function while studying for Andela.

def binary_converter(q):
    if q>255 or not isinstance(q, int) or q<0:
        return "Invalid input"
    if q==0:
        return '0'
    elif q!=0:
        q, r = divmod(q, 2)
        return str(r)+binary_converter(q)

The code works for the most part, except I haven't figured out a way to get rid of any preceding zeros to the final result.

For example:

      binary_converter(62)
      '0111110'
      That's 0111110 with a preceding 0.

How in the world do I get rid of it without breaking the code?

I've tried returning an empty string for the if condition but that breaks my ability to convert the decimal 0 to it's binary which is still 0.

Edit:
Here's the working code, updated with D.W's answer

def binary_converter_for_realz(q):
    if q>255 or not isinstance(q, int) or q<0:
        return "Invalid input"
    if q==0:
        return ''
    elif q!=0:
        q, r = divmod(q, 2)
        return binary_converter_for_realz(q)+str(r)

def binary_converter(q):
    if q==0:
        return '0'
    else:
        return binary_converter_for_realz(q)

Change your code for binary_converter() to return the empty string ('') instead of '0', when you pass it the input zero.

Then, write a new function binary_converter_for_realz(), which checks whether the input is zero; if passed zero, it just returns '0', otherwise it invokes binary_converter() and returns whatever it returns.

This basically treats 0 as a special case, which it is: we don't want a leading zero, except when the integer is zero, in which case we do.


Algorithm for producing array of objects according to the given distribution I have a set of objects, and each object has (let's say) a color. Given a distribution such as:

red : 50%
green : 30%
blue : 20%

I need to produce an N-length array of objects with a color distribution as close to this as possible. It is possible that the length of the original
list is smaller than N, so duplicates may be required.

Is there an efficient algorithm that might be suited for this kind of task? I imagine there is, but I'm lacking the terminology to find it.

Do you need to guarantee that, in every sample, 50% of the objects are red, 30% are green and 20% are blue? If so, just make your array consist of $0.5\,N$ red objects chosen uniformly at random, followed by $0.3\,N$ green and $0.2\,N$ blue. You'll need to deal with the rounding error if $N$ isn't divisible by $10$.  You can always shuffle the array if it's not desirable to have it sorted by colour.

If you only need to guarantee that the proportions of the colours are correct in the long-run, Apass.Jack's solution will do the job.  If $N$ is very large, then each array generation is "the long-run" and will be close to the correct proportions (but not guaranteed to be exact).


Shifting and adding to get multiplication values? multiplying by 33 --> $2^5 + 2^0$
is same as (num << 5) + 1

and by 65599 as (num << 16) + (num << 6) - (num << 0)

How do you get these numbers though i.e. 16,6?? I know log can be used but Is there any other quicker way to do this?

EDITED___________________

what I need to do is create a hash function such that I have to recursively multiply with numbers like 65599 or 33... hence the shift might be a better option

Shifting left is the same as multiply by two.
Take number, say in your example 33, convert to binary, 100001, here 1<< 6 is the leftmost bit and 1 is rightmost bit. As you have noticed it is $2^0$.

Second example is handled manually, it is 10000000000111111, so at first you set leftmost bit, then notice that consecutive ones could be converted to 1000000 - 1.

Standard usage is to speed up multiplication by constant, so you precompute it and use in your code. It makes sense until additions, subtractions and bit shifts are cheaper on target machine than one vanilla multiplication.
Some bit twidlings are already present in compilers, other may break compilers ability to optimise more.

Such operation is good in static, compiled languages, like C. It may work on managed ones (with platform independent emulation of arithmetic operations), but makes little sense on interpreted languages like Python (unless you compile it).


can more than two arrows point towards the same state from other states in a DFA? Is something like this possible:

You have state A,B,C all pointing towards accepting state D.
Is this allowed?
Where online can I find a list of rules that define how an automata must be drawn or conceived?

Yes, this is allowed (and in fact, you lose a lot of computational power without it)

here is a definition of DFA (both formal and as drawings) + an example


Is the buckets of water problem in NP? Continuing from this question: the buckets of water problem.
(All the definitions can be found there, so I will not repeat them).
As seen there by Yuval's answer, the problem is NP-Hard.
I was attempting to prove its NP-completeness, and while doing so - I was suddenly not sure whether or not it belongs to NP.
Because the witness is most likely to be a series of actions (filling buckets etc ...), and that might be too long.
Of course, we can change the definition of the language, in such a way we will limit the number of actions to be polynomial or make it part of the input (with a slight adjustment to represent the number of actions in unary, so it won't be log of the number's value).
But, I find it interesting to ask if this is a must?
And if we do not change anything - Can we tell for sure it is not NP? That there is no better (polynomial) witness.

This problem is in NP, because it is "exactly as hard" as SUBSET-SUM problem. Moreover, it is, in some sense, the SUBSET-SUM problem in disguise! Let's show that.
Denote the number of buckets by $n$, their capacities by $c_1 \leqslant c_2 \leqslant \ldots \leqslant c_n$ and the original quantities of water in them by $a_1, a_2, \ldots, a_n$ (here I assume without loss of generality that the buckets are sorted by their capacities). I claim that the following statements are equivalent:

There exists a way to get exactly $m \in [0, c_n]$ water in some bucket.
There exists a subset $S$ of $\{1, 2, \ldots, n\}$, such that $\sum\limits_{i \in S} a_i \equiv m \pmod{\gcd(c_1, c_2, \ldots, c_n)}$.

To prove the $1 \Rightarrow 2$ implication, let's notice that, at every moment of time, the quantity of water in each bucket can be expressed as "sum of $a_i$ over some subset of $\{1, 2, \ldots, n\}$" $+$ "some integer linear combination of $c_i$, with negative coefficients allowed". Indeed, we can check that all three allowed operations preserve this property. The latter part is divisible by $\gcd(c_1, c_2, \ldots, c_n)$, hence $m$ being possible to obtain implies the condition $2$.
The $2 \Rightarrow 1$ implication follows from the same type of the argument as I presented in the comments. I will reproduce it here for completeness. Indeed, suppose that $m \equiv \sum\limits_{i \in S} a_i \pmod{\gcd(c_1, c_2, \ldots, c_n)}$. Because $\gcd(c_1, c_2, \ldots, c_n)$ is representable as a linear combination of $c_i$, we can represent $m$ as an integer linear combination of $c_i$ and $a_i$, with all coefficients before $a_i$ being $0$ or $1$.
Clearly, it is enough to obtain $m \bmod c_1$ water somehow (after doing that, we can just repeatedly add $c_1$ of water). But, as long as we are interested in obtaining something only modulo $c_1$, we can replace all negative coefficients before $c_i$ in this sum with nonnegative ones (by adding $c_1$ appropriate number of times). Hence, we have a representation $m \equiv \sum\limits_{i \in S} a_i + \sum\limits_{i = 2}^n k_i c_i \pmod{c_1}$, where $k_i$ are some nonnegative integers.
Now, suppose that we have $x$ water in the $i$-th bucket and $y$ water in the first bucket. Then, we can get $(x + y) \bmod c_1$ water in the first bucket and make the $i$-th bucket empty. Indeed, try to move all the water from $i$-th bucket to the first. If $x + y < c_1$, then we are done. Otherwise, the first bucket is full now and the $i$-th bucket contains $x + y - c_1$ water. Empty the first bucket and repeatedly drain $c_1$ of water from the $i$-th bucket, until there is only $(x + y) \bmod c_1$ water left. Then move all the water to the first bucket.
By doing the operation from the previous paragraph for all $i$ in $S$, we can get $\left( \sum\limits_{i \in S} a_i \right) \bmod c_1$ water in the first bucket (if $1$ is not in S, we need to empty the first bucket beforehand). Now, for each $i$ from $2$ to $n$, repeat the same operation $k_i$ times, but now fill the $i$-th bucket before the operation. In the end, the first bucket will contain exactly $\left( \sum\limits_{i \in S} a_i + \sum\limits_{i=2}^n k_i c_i \right) \bmod c_1 = m \bmod c_1$ water.
Hence, this problem is equivalent to some kind of "modular subset sum", with modulo being equal to $\gcd(c_1, c_2, \ldots, c_n)$. As for NP witness, any witness for "modular subset sum" problem will do, for example the set $S$.
A more natural witness in the context of the original problem is a "compressed sequence of operations", in the sense that we allow commands of the type "repeat a given sequence of operations a given number of times". The proof above can be translated into such a witness, and a particularly simple one (no nested block commands, we repeat only some fixed short blocks, et cetera). I am not 100% sure whether it is possible to simulate a general compressed sequence of operations in polynomial time, but I am inclined to believe that the answer is "yes, it is possible". However, it is definitely possible to simulate sequences arising from the above proof quickly, though requiring that makes the witness much less natural.
Indeed, the second part of the proof constructs a sequence of operations of polynomial length, but with a catch that the following two "mega-operations" are also allowed:

Given a bucket with $x$ water, repeatedly drain it by $c_1$, till there is only $x \bmod c_1$ water left. The first (the smallest) bucket should be empty before this operation. This operation is used repeatedly thorough the proof
If we have $m \mod c_1$ water in the first bucket, empty the largest bucket, move $m \mod c_1$ water into it and repeatedly add $c_1$ water until there is $m$ water in the largest bucket. Used only once in the end.

These "mega-operations" correspond to some simple arithmetical operations on the quantities of waters in the buckets and $c_i$'s, hence they can be carried quickly in the model of computation we are using, despite the fact that they take very large number of elementary operations with buckets.


Decomposing a closed walk in a directed graph into cycles Let's say I have a closed walk $W$ in a directed graph $D$. Represent $W$ as a list of arcs $(a_1, a_2, \dots, a_k)$. Since it's a closed walk, there may be repeated edges, but the source vertex of $a_1$ must equal the target vertex of $a_k$. My claim is that the multiset of arcs $W'=\{a_1, a_2, \dots, a_k\}$ can be partitioned into sets (not multisets) $W'_1, W'_2, \dots, W'_m$ such that the arcs in each $W'_i$ form a simple cycle.

There is a simple algorithm to output these cycles. Travel along $W$ until you visit a vertex $v$ for the second time. Output the arcs between the two occurrences of $v$ (which form a cycle). Repeat this process until the walk is empty.

I'm using this "walk decomposition" lemma in a paper, and it seems like something that should be easy to find in the literature, but I can't find it anywhere. Can anyone point me in the right direction?

The problem stated in the question is also presented in the exercise of the book.

If you are writing a research paper, due to the is simplicity of the solution, you may even skip the explanation.


Solving functional equations for unknown functions in lambda calculus Are there any techniques for solving functional equations for unknown functions in lambda calculus?

Suppose I have the identity function defined extensionally as such:

$I x = x$

(that is, by writing down an equation for the expected behaviour of that function) and now I want to solve it for $I$ by doing some algebraical transformation to get the intensional formula for that function:

$I = \lambda x.x$

that tells how exactly does the function do what was expected (that is, how to implement it in lambda calculus).

Of course the identity function is used just as an example. I'm interested in more general methods of solving such equations. In particular, I would like to find a function $B$ that satisfies the following requirement:

$B\;f\;(\lambda x.M) = (\lambda x.f M)$

that is, "injects" the given function $f$ into  the given lambda function $(\lambda x.M)$ before its "body" $M$ (which is some arbitrary lambda expression), possibly by taking it apart and constructing a new one, so that it became a parameter the function $f$ is applied to.

This is a known problem, known as Higher Order Unification.

Unfortunately, this problem is undecidable in general. There is a decidable fragment, known as Miller's Pattern Fragment. It's used extensively in, among other things, typechecking of dependently-typed programs with metavariables or pattern matching. This fragment is where unification variables are applied only to distinct bound program variables.

This paper provides a great tutorial of how higher order unification works, and walks through a (relatively) simple implementation of it.

Unfortunately, it doesn't look like your function falls into this pattern fragment. That said, what I'm looking seeing is pretty similar to function composition. Does the following function satisfy your property?

$B = \lambda f\ g\ x\ \ldotp f\ (g\ x) $

We have:

$B\ f\ (\lambda x . M)$
$= B\ f\ (\lambda y . [y/x]M)$ by $\alpha$-equivalence
$ = \lambda x . f\ ((\lambda y. [y/x]M) x) $
$= \lambda x . f\ ([x/y][y/x]M)$
$= \lambda x . f\ M$


Approximation of Set Cover I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better than $\log n$. So we can use Vertex Cover algorithm to solve Set Cover problem and get a better approximation ratio. Can anyone explain this to me?
Thanks in advance

Dinur and Steurer [1] showed that assuming $P \neq NP$, there is no polynomial time algorithm which approximates set cover by a $(1-\epsilon)\ln(n)$ factor, for any constant $\epsilon > 0$.
[1] https://arxiv.org/pdf/1305.1979.pdf


Why can't we derandomize the PCP theorem by iterating over all possible $\log n$ random strings? Let's say I can solve problem $A$ in polynomial time using only $\log n$ bits of randomness, with a $\ge \frac{2}{3}$ chance of a correct answer.  Then surely I can solve $A$ determistically by running my algorithm for $A$ over all random strings of length $\log n$ (of which there are a polynomial number) and take a popular vote of the outcomes.

I don't understand, then, why we would ever talk about $O(\log n)$ amounts of randomness in complexity classes that are closed under polynomial factors.  More specifically, the PCP theorem says $NP = PCP[O(\log n), O(1)]$ - why isn't that the same as $PCP[0, O(1)]$?

We can! However, the PCP theorem does not say that we can solve the problem using $\log n$ bits of randomness. It says that we can verify a solution with $\log n$ bits.

Recall that a standard definition of NP is the class of languages for which there is a deterministic, polynomial-time verifier: For each $x$ in the language, there is a certificate $y$ so that the verifier accepts $\langle x,y \rangle$, and there is no such $y$ if $x$ is outside the language.

The PCP theorem says that we could also define NP as the class of languages for which there is a randomized, polynomial-time verifier that uses $\log n$ bits of randomness and reads only a constant number of bits of the certificate $y$.

Notice that if you derandomize the $\log n$ bits of randomness by enumerating them all and running this verifier on each one, you end up with a deterministic algorithm that will read the entire certificate $y$, which matches the standard definition of NP above.


In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness? The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test:

  It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for the compositeness of $n$.

In the Fermat primality test, if $n$ is not a Carmichael number, at least half of the bases $a$ are Fermat witnesses. Testing for non-trivial roots in the Miller-Rabin primality test however increases the minimum number of witnesses to $\frac{3}{4}$.

Here are the three tests you're (implicitly) considering:

Fermat: test whether $a^{n-1} \equiv 1 \pmod{n}$
Solovay-Strassen: test whether $a^{(n-1)/2} \equiv \left( \dfrac{a}{n} \right) \pmod{n}$ (where $\left( \dfrac{a}{n} \right)$ is a Jacobi symbol, which can be calculated using quadratic reciprocity via a GCD-like algorithm)
Miller-Rabin: suppose $n-1 = 2^k m$. Test whether the list $a^m,a^{2m},\ldots,a^{2^km} \pmod{n}$ consists of a (possibly empty) string of $-1$s followed by a string of $1$s

Each test is stronger than the previous one: if $a$ passes Fermat's test, it will satisfy Solovay-Strassen, and if it passes Solovay-Strassen then it passes Miller-Rabin. In the first two tests, the set of $a$ which pass the test form a group. Therefore, unless all $a$s pass the test, at most half of them do. For Solovay-Strassen, one can show that if $n$ is composite, then some $a$ (which can be constructed explicitly) doesn't pass the test.

For Miller-Rabin, the argument is more complicated. The most difficult case turns out to be $n = pq$, where $p,q$ are different primes. The argument uses the Chinese Remainder Theorem to consider what happens modulo $p$ and modulo $q$ separately. For $a$ to pass the test, it must behave in exactly the same way under both primes, and that's the intuitive reason that makes it harder to pass the test. For a proof, check Schoof's paper, for example.


How does Bifunctor in Haskell work? I was reading 'Category Theory for Programmers' by Bartosz Milewski and got really confused by the implementation of bimap in Bifunctor typeclass.

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
    bimap g h = first g . second h
    first :: (a -> c) -> f a b -> f c b
    first g = bimap g id
    second :: (b -> d) -> f a b -> f a d
    second = bimap id

This is the definition of the Bifunctor typeclass taken directly from the library Control. If bimap evaluates to first and second, which in turn evaluates to bimap itself, how is this supposed to end? Could you please explain how the evaluation of bimap works? Thank you!

A Haskell type class defines a set of functions (sometimes called methods) that belong to the type class. In most cases, specific instances must supply specific implementations of one or more of these.

An instance can implement all methods, or just enough to make the instance work. If an instance doesn't implement all methods, the default implementations are used.

Type classes are typically documented with the minimal implementation required. This is also true for Bifunctors:

Minimal complete definition

bimap | first, second

This means that an instance must implement either bimap, or both first and second. An instance can also implement all three, but that's not required.

The tuple instance, for example, is implemented using bimap:

instance Bifunctor (,) where
  bimap f g ~(a, b) = (f a, g b)

This means that the first and second implementations are the default implementations you quoted above. They call the instance's bimap implementation.


Is Virtual Memory unreliable? I have a question regarding multilevel page tables. As far as I know, in most 64 bit systems only 48 bits are used in page tables which would allow for 256TB of virtual memory to be addressed.

For personal computers, I don't understand how they would ever be able to support that amount of memory being virtualized. If the processes currently running on your computer think they have a total of 256TB available, if they do end up using all that memory, the contents would eventually need to be flushed back to disk. This is not possible since your disk can't possibly hold that much memory.

I'm thinking on an analogy to a bank that tells its customers they can each take out loans of 1,000 gold bars. They give their customers a note saying they have 1,000 gold bars worth of funds. Now say that the customers have used their loans to obtain different goods which they want to store in the bank. The bank would not be able to hold all those goods, and the people (processes) wouldn't be able to hold those goods either since once a computer is shut off all the memory not on disk is volatile. In a sense the bank is offering more than it can really hold.

For a more practical example, say I have 1GB of disk memory available and my virtual memory system is able to virtualize 3GB of memory. Now say I open 3 text files and start typing stuff into them, eventually reaching that 3GB limit. Now I want to save those files, but I only have 1GB available on disk!

Isn't virtual memory unreliable from a process point of view since it's saying "I can store all this stuff for you" but at the end of the day it doesn't have the resources to do so?

At a hardware level, virtual memory means, essentially, a mapping from a virtual address space to a physical address space, the data structures and instructions to maintain them, and a facility to trap to the operating system if a mapping is not valid. This mapping is at the page level: a page maps to a page frame.

At the operating system level, we usually conceptualise a virtual address space as a collection of segments. A segment could represent part of a file which resides on secondary storage (e.g. disk). This could be program text, or a memory-mapped file. Or it could represent anonymous memory, that is, memory which is allocated by a process and may be swapped to secondary storage if not needed. Anonymous segments are often zero-fill, which isn't backed by physical memory until it is first used. Or it could represent a memory-mapped I/O area, or an operating system device, or an operating system data structure (e.g. the "u area" in Unix).

Segments can be shared between address spaces (e.g. after the Unix fork system call). They can be copy-on-write. And so on and so forth.

There are enough "things" that can be mapped which aren't really "memory" that you can't really say that virtual address space is only as useful as the amount of physical stuff that can be mapped to it.

One more thing: Another advantage of a large virtual address space is reduced external fragmentation. You see, the segments that comprise a virtual address space need to be allocated and deallocated just like anything else, and you can't really move them within the address space. So having a large virtual address makes it easier to allocate within it.


Language acceptance by DFA I have some questions regarding acceptance of a language by DFA

Whether more that one dfa accept a language
Whether a dfa can accept more than one language

Yes, there can be many DFAs for a language. Many will be silly though, one way to get another is to add unreachable states to any DFA for the language). It is also possible to have more than one sensible DFA:

These two DFAs both accept $\{a,b\}^{\ast}$.
On the other hand each DFA accepts exactly one language (i.e. no DFA accepts zero languages, or two or more languages) .


Are functions in O(n) that are nor in o(n) all in Θ(n)? One of my lectures makes the following statement:

$$( f(n)=O(n) \land f(n)\neq o(n) )\implies f(n)=\Theta(n)$$

Maybe I'm missing something in the definitions, but for example bubble sort is $O(n^2)$ and not $o(n^2)$ but it's also not $\theta(n^2)$ since it's best case run time $\Omega(n)$.

What am I missing here?

Tell the lecturer they're wrong. Take the function
$$ f(n) = \begin{cases} n & n \text{ is even}, \\ 1 & n \text { is odd}. \end{cases} $$
This function is $O(n)$ but neither $o(n)$ nor $\Theta(n)$.

Here is a monotone example, which might be more convincing:
$$ g(n) = \exp \exp \lfloor \ln \ln n \rfloor. $$


Traversing a graph with respect to some partial order Recently I was faced with the following Graph traversal problem:
"Given an arrangement of buildings in form of a DAG. All the buildings have to be colored, but there is an order for that represented by edges in the DAG. If there is an edge from A->B, this would mean building B can only be colored after building 'A' has been colored. Also given is an array which provides the initial cost of coloring each building (vertex) in the graph. The actual cost of coloring a building 'v' is I(v) * C(v), where 'I(v)' is the number of buildings colored before 'v' plus '1' and C(v) is its initial cost of coloring provided in the array. Find the minimum actual cost of coloring all the buildings in the graph."

If there an is an edge from A->B, building B can be colored only after building A has been colored. Of course, there can be multiple routes to B in the graph, for instance from A->B and C->B. In this case if the provided array is (2,1,3) for coloring (A, B, C), and we choose to color building in the order of (A, B, c) then total cost = 1*C(A) + 2*C(B) + 3*C(C) = 1*2 + 2*1 + 3*3 = 13. However we cannot have an ordering where B is colored first.

I came up with a brute force solution to this problem. Topological sorting might help, but I couldn't really figure out how. Any suggestions?

This is a job-shop scheduling problem, known as $1|\textrm{prec},p_i=1|\Sigma w_i C_i$. It is $NP$-complete.

Lenstra, J.K. and Rinnooy Kan, A.H.G.: Complexity of Scheduling under Precedence Constraints. In Operations Research, vol. 26, pp. 22-35 (1978)

Sadly the paper is not open-access. They show $NP$-hardness by reduction from Linear Arrangement (also known as Graph Bandwidth)


How to show independence and uniform distribution of hash codes from k-wise independent hash functions? Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\dots, x_k \in D$ and $y_1, y_2,\dots, y_k \in R$,
$$\mathbb{P}_{h \in H}(h(x_1) = y_1, h(x_2) = y_2, \dots, h(x_k) = y_k) = \frac{1}{|R|^k}$$
The Wikipedia article on k-wise independent hash functions (which uses the above definition) claims that the definition is equivalent to the following two conditions:
(i) For all $x \in D$, $h(x)$ is uniformly distributed in $R$ given that $h$ is randomly chosen from $H$.
(ii) For any fixed distinct keys $x_1, x_2,\dots, x_k \in D$, as $h$ is randomly drawn from $H$, the hash codes $h(x_1), h(x_2), \dots, h(x_k)$ are independent random variables.
It is not obvious to me how one proves (i) from the above definition without explicitly assuming (ii) in the definition as well (and vice-versa). How is the definition sufficient for proving both (i) and (ii)?

Throughout, we assume that $|D| \geq k$.
Suppose that $H$ satisfies, for all distinct $x_1,\dots,x_k \in D$ and all $y_1,\ldots,y_k \in R$,
$$
\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k}.
$$
Now let $x \in D$ be arbitrary. Since $|D| \geq k$, we can find $x_2,\ldots,x_k \in D$ such that $x,x_2,\ldots,x_k$ are distinct. For each $y \in R$,
$$
\Pr_{h \in H}[h(x)=y] =
\sum_{y_2,\ldots,y_k \in R} \Pr_{h \in H}[h(x)=y,h(x_2)=y_2,\ldots,h(x_k)=y_k] = \\
\sum_{y_2,\ldots,y_k \in R} \frac{1}{|R|^k} = \frac{|R|^{k-1}}{|R|^k} = \frac{1}{|R|}.
$$
This proves (i). To see (ii), let $x_1,\ldots,x_k \in D$ be distinct. Then for all $y_1,\ldots,y_k$,
$$
\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k} = \prod_{i=1}^k \frac{1}{|R|} = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i].
$$
In the other direction, suppose that (i) and (ii) hold. Then for all distinct $x_1,\ldots,x_k \in D$ and $y_1,\ldots,y_k \in R$,
$$
\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i] = \prod_{i=1}^k \frac{1}{|R|} = \frac{1}{|R|^k} .
$$


An infinite subsequence of random numbers in Kolmogorov sense Is it possible to construct an infinite increasing sequence of random naturals (in Kolmogorov sense) that is a subsequence of another sequence? Ok, in general I suppose not, e.g. for prime numbers. But:

I want to prove that sequence $\{ax+b\}_{x\in\mathbb{N}}$ contains an infinite subsequence of random numbers. (This is, more-or-less, a statement in an exercise).

EDIT: The actual statement is to show that $\limsup\limits_{x\to\infty}\frac{C_U(ax+b)}{\log (ax+b)}=1$.

I believe the existance of infinitely many random numbers in general, stems from the fact that for a given $k$ we have $|\{x\in\{0,1\}^k: C_U(x)< k\}|< 2^k$ because there are less binary strings of length $\leq k-1$ which may represent input to $U$. So no matter how large a binary representation, we can always find a random number with such a representation (in terms of its length). So, assuming longer $x$ means larger number it represents, we have infinitely many random numbers.

But what about here? We'd want those numbers to be of very specific form. Is there a way to do that? Could you give me a hint?

If $x$ is Kolmogorov random then $C_U(ax+b) \geq \log x - O(\log a + \log b + 1)$ (why?), and so
$$
\frac{C_U(ax+b)}{\log (ax+b)} \geq \frac{\log x - O(\log a + \log b + 1)}{\log x + O(\log a + \log b + 1)} = 1 - O\left(\frac{\log a + \log b + 1}{\log x}\right).
$$
Since there are infinitely many Kolmogorov random numbers $x$, your result follows.


Any CPUs using value prediction, dynamic instruction reuse? There is a lot of research about techniques that try to reuse the previous result of an instruction, either memory loads or arithmetic, such as dynamic instruction reuse, value prediction, based on the concept of value locality.

What I wonder if there is any commercial CPU from Intel/AMD/ARM that actually uses any of these techniques, or are they still far away from being implemented in CPUs?

I mostly see these techniques as the runtime, CPU version of compiler optimizations such as common-subexpression elimination, loop invariant code motion, redundant load removal, catching cases that cannot be handled due to pointer aliasing, side-effects, etc.

Two of the papers that seem to have introduced these ideas:
Dynamic instruction reuse
Value Locality and Load Value Prediction

Modern Intel processors use prediction of values in several situations.

One, when the target of a branch instruction is stored in memory including the location where the return address of a call is stored, that value is predicted.

Second, when a store is followed by a load, it is predicted whether the addresses are the same (or overlapping) or not. That allows the load to be performed speculatively even before the value to be stored is calculated, if it is predicted that the addresses are different.


Shouldn't every algorithm run in pseudo-polynomial time? Wiki says
a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it.

This answer very well explains why primality test algorithm of running time $O(n)$ is actually pseudo-polynomial time. Simply put A very simple way of thinking about it is that if you double the limit, the size of the input only increases by one bit (since the limit is part of the input), while the run time is doubled. That is clearly exponential behavior with respect to the input size.

That is, add one extra bit in the bit representation of your input and the running time will increase exponentially.

Okaaay, My doubt is, isn't it applicable to every algorithm then? Like in sorting. One might say "The main difference is that, in pseudo-polynomial time algorithms, n represents a number in the input, while in other algorithms (sorting) n represents the number of things"

To which I think, how does that matter? Searching maximum in an unsorted array of size $n$ takes $O(n)$ time, add one extra bit to $n$ and the running time will grow exponentially. Hence Shouldn't every algorithm run in pseudo-polynomial time?

The running time is always considered with respect to the length of the input.

If the input is a natural number $N\in\mathbb{N}$, then the length of the input is $n=\log N$. In that case, running time of $\Theta(N)$ is actually exponential in the length of the input, $n$.

Suppose now that we're dealing with a problem where the input is a collection of $n$ elements. For simplicity, assume each member in the collection can be represented by a constant number of bits, independent of the input. Lets denote this constant by $c$, so the number of bits required to represent this collection is at most $cn$. In that case, if upon receiving a collection with $n$ elements (which is a $cn$ length input) you preform only $O(n)$ operations, then the running time is linear.

When saying the input is a number $N$, or a list of size $n$, we already talk about the semantics of the input (how we intend to interpret the given sequence of bits). You can count the running time in terms of those "interpretations", e.g. $O(N)$ for naive primality testing, or $O(n)$ for finding a maximum in a list, but in the end you have to remember how those objects relate to the actual input's size. If we denote the length of the input by $l$, for primality testing we have $l=\log N$, so $T(l)=N(l)=2^l$, and for finding maximum $T(l)=n(l)=\frac{1}{c}l$.


Why do ¬, ∀ and ∃ have the same precedence? I thought the order of precedence of operators and quantifiers was arbitrary, but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have precedence over ∧, but not over ∀). This leads to the rule being that ¬, ∀ and ∃ will bind to the closest predicate on their right (if I understood correctly). Why is this?

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

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


Building a tree with the heap property from an array and preserving its order How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array?

For example, if I have:

  2 1 5 6 2 3

I want to build:

  1
 / \
2   2
   / \
  5   3
   \
    6

Because it has the heap property and its inorder is the original array 2 1 5 6 2 3.

An O(n)-time algorithm for the problem has been published by Gabow et al. (1984) in the context of "Cartesian trees": https://dl.acm.org/doi/10.1145/800057.808675
As pointed out above by Raphael, there is a close relationship to treaps.
You may also want to visit the corresponding Wikipedia entry: https://en.wikipedia.org/wiki/Cartesian_tree


Why are threads called the unit of dispatch? Threads called the "unit of dispatch" but what does that mean? I was looking over the web and two operating systems books but I can't find the answer. It seems that processes are defined by two characteristics: resource ownership and scheduling/execution. I understand that threads are within processes, and that there must be at least one thread. Can someone explain this to me please?

"Unit of dispatch" just means "the thing that gets scheduled."


Probability that a uniformly random sequence is already sorted Now I tried tackling this question from different perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ideas).

Let there be $k, n \in\mathbb{Z_+}$. These are fixed.

Consider a set of $k$ integers $S=\{0, 1, 2, ... k-1\}$.

We form a sequence  $a_1, a_2, ..., a_n$ by picking numbers from $S$ at random with equal probability $1/k$.

The question is - what is the probability of that sequence to be sorted ascending, i.e. $a_1 \leq a_2 \leq ... \leq a_n$?

Case $k \to \infty$:

This allows us to assume (with probability tending to $1$) that all elements $a_1, ..., a_n$ are different. It means that only one ordering out of $n!$ possible is sorted ascending.

And since all orderings are equally likely (not sure why though), the probability of the sequence to be sorted is

$$\frac{1}{n!}.$$

Case k = 2:

Now we have zeroes and ones which come to the resulting sequence with probability $0.5$ each. So the probability of any particular n-sequence is $\frac{1}{2^n}$.

Let us count the number of possible sorted sequences:

$$0, 0, 0, \ldots, 0, 0$$
$$0, 0, 0, \ldots, 0, 1$$
$$0, 0, 0, \ldots, 1, 1$$
$$\ldots$$
$$0, 0, 1, \ldots, 1, 1$$
$$0, 1, 1, \ldots, 1, 1$$
$$1, 1, 1, \ldots, 1, 1$$

These total to $(n+1)$ possible sequences. Now again, any sequence is equally likely, so the probability of the sequence to be sorted is

$$ \frac{n+1}{2^n}. $$

Question:

I have no idea how to generalize it well for arbitrary $k, n$. Maybe we can tackle it together since my mathematical skills aren't really that high.

You can have $k^n$ possibilities of generating a sequence.

Now, there are only $^{n+k-1}C_{k-1}$ favorable outcomes .

So, the probability that your sequence is already sorted is: $$ \frac{^{n+k-1}C_{k-1}}{k^n}$$


What are examples of $\mathsf{NL}$-complete problems? Wikipedia lists exactly two problems as $\mathsf{NL}$-complete - 2-satisfiability and St-connectivity (although stating that there are "several"):

https://en.wikipedia.org/wiki/Category:NL-complete_problems

My old literature on complexity (from study) also has no additional examples. And the complexity zoo also lists the graph reachability problem as sole example:

https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N

So, are there any other problems known to be $\mathsf{NL}$-complete?

Here are three more examples, taken from an assignment by Trevisan:

Given an NFA and a word, determining whether the NFA accepts the word.
Reachability in DAGs.
Determining whether a digraph is strongly connected.

Planken shows that the Simple Temporal Problem with bounded weights is NL-complete (see the link for definitions).

There are likely many others. Schaefer's dichotomy theorem, in particular, gives many examples.


Voronoi cells for rectangles I am looking for a reference on the following variant of a Voronoi diagram:

Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint.
Instead of Euclidean distance, we are interested in Manhattan distance.

The goal is to partition the plane into regions, such that the points in each region $i$ are closer (in Manhattan distance) to rectangle $i$ than to every other rectangle.

What would such cells look like? Are there algorithms for finding them?

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

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

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

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


Inorder Traversal of the Ternary Tree According to wikipedia , Definition of In-order Traversal on Binary Tree :-

1) Check if the current node is empty or null.
2) Traverse the left subtree by recursively calling the in-order function.
3) Display the data part of the root (or current node).
4) Traverse the right subtree by recursively calling the in-order function.

I want to find the similar In-order Traversal definition on Ternary Tree. I was referring the Professor Robert Sedgewick's lecture of Ternary Search Tries.
I found that if I do the In-order traversal on the Ternary Search Tree(a type of Trie data structure) for a particular searched string then visiting order of nodes should be :-

1) Check if the current node is empty or null.
2) Traverse the left subtree recursively calling in-order function.
3) Display the data part of the current node.
4) Traverse the middle subtree by recursively calling the in-order function.
5) Traverse the right subtree by recursively calling the in-order function.

Now , while solving one homework problem , I got different result from the given solution.
The problem was :- Find the In-order Traversal of the following tree :-

According to me answer should be :- AKBJCLIEDHFG
But given answer is :- AKBJCLIDEHFG

I also faced one similar question in one competitive exam as :-

According to me , Answer should be :- $QSPTRUWV$
But given answer is :- $SQPTRWUV$
Please verify whether my answers are correct or not and If I am wrong somewhere then please correct me.

According to me answer should be :- AKBJCLIEDHFG

Your answer is ((A)  (K)  ((B) (J) (C)))   (L)   (I)   (((E) (D))  (H)  (F) (G))

Please take a close look at the part ((E) (D)). Here lies the ambiguity/confusion/uncertainty. The ambiguity is whether D is the left subtree or the middle subtree or the right subtree of E.

Because of the limited drawing spaces that shows the tree, it can be argued in a few ways. I could swear that D is meant to be the left subtree or E. On a different day, I might, agreeing with you, insist that D is so apparently the middle subtree of E. On another day, I could stretch myself a little bit, unabashedly claiming that D is in fact the right subtree of E. Unless there are some kind of instructions such as your textbook or whatever material you have been using has defined the rules how to tell the class of subtree from the way is drawn in case of ambiguity, it is impossible to conclude which subtree of E D is.

So your question is reduced to whether there are those kind of rules in your material. Or in your instructor's notes or oral guide. Or, what is general convention in your culture or your context to interpret "left", "middle" and "right". This question is not so much of computer science, but more about linguistics and drawings and culture.

If I had to pick one solution out of no context, I would be very frustrated on deciding whether D is a left subtree or right subtree of E. I would choose one of many possible actions below, without any particular preference.

try finding the context or the rules.
just choose left subtree.
just choose middle subtree.
wave my hands, declaring no value to solve a question that is not well-formed.
presenting two solutions or three solutions, each with its assumption stated clearly.
redraw the graph in the question.
raise a question about that question to seek other's judgements as you just did
had I been a student, my TA should have been my savior and my professor should have been the ultimate arbitrator.
the last option that stands for all the remaining possibilities.

(By the way, I just searched the lecture briefly. I have not found any definitive guide on how to tell left or middle or right subtree. Of course, I might have missed some hints or conspicuous rules.)


Adder circuit with sign bit (not twos complement) I've found and implemented a full adder to be able to do unsigned or two's complement addition on wikipedia:
https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder

However, in my particular case, I'd like to use a sign bit instead of twos complement, due to there being a variable (unbounded) number of bits involved.

How can i do addition and subtraction with binary numbers using a sign bit? (say, it's a separate bit, not one of the binary digits per se).

I also only have access to AND and XOR.

Edit: Potatoswatter suggested that twos complement is still able to be done with an unbounded number of bits.  What do you do when you want to add 6 bits and 8 bits together?  Also, is multiply, divide and modulo easily done in twos complement?  Keep in mind i have only AND and XOR, so don't have the ability to do if statements, the logic needs to be "branchless".

Thanks!!

This is called "sign-magnitide" or "signed-magnitude" representation. A Google search for "sign-magnitude adder" gives lots of useful results. I know this doesn't answer your question directly (I don't have enough reputation to simply comment your post), but you will find the answer there.

As for only having AND and XOR, this is the classic result that any logic gate can be constructed from AND and NOT. Note that XOR(1,a) = NOT(a). Now you have NAND and NXOR. NOR(a,b) = AND(NOT(a),NOT(b)). Now you have OR by negating NOR. All other gates can be constructed by negating inputs of these gates.


Need help understanding the tuple relational calculus We say that a query in a TRC is a statement of the form $\{T: P(T)\}$, where $T$ is a tuple variable and $P(T)$ is a formula.

Now my question is, what are the possible tuples $T$ to be tested i.e., what are the types and values for tested tuples.

As far as I know in set theory and in particular in set builder notation the variables should come from another well-defined set.

From Wikipedia:

A tuple is of the form $T=(D,R,h)$ where $D$ is the domain, $R$ is a set of relation names, and $h$ is a mapping that associates a column name to each relation in $R$. To represent a tuple, we can see $D$ as the set of keys, and $R$ the table associated with those set of keys, and $h$ the column names of the table.


How can I tell if a bit pattern can represent offset gray-code? I have a very poor understanding of gray code in general and I find it to be a difficult thing to learn. While trying to learn about it I stumbled upon this seemingly looking trivial question that I can't answer.
Can the bit pattern 01110011 represent offset gray-code?
What is "gray-code" and how do I construct it and recognize offset gray-code?

Yes. Any bit pattern can represent an offset gray-code number. Gray code is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).To fully understand it you need and example and compare with default binary.
In binary:
1-> 0001
2-> 0010
3-> 0011

You can see that in binary when incrementing from 1 to 2, there are happening two bit operations. One is that the first bit turns off and second the 2'nd bit lights up. So this violates the rule of gray-code - "two successive values differ in only one bit".
In gray code it would look like this:
1-> 0001
2-> 0011
3-> 0010

Can you see the difference?
When we incremented from 1 to 2, the first bit didn't turned off anymore and the second lighted up. So only one bit operation happened.
You can also check out this article which has a C program that generates gray-codes between 1-32 bits.
Using-Gray-Codes


Proving the regularity of the following language I have a question about the following problem:

  Prove that the language $\{a^nva^n | v \in \Sigma^*, n \ge 1\}$ is regular over
  $\Sigma = \{a,b\}.$

I know that in proving a language is regular I can either construct a DFA, give a regular expression or show the Nerode-Relation has finite index.

My main problem is, that I cannot understand why this should be a regular language, since $\{a^nb^n | n \ge 1\}$ is not regular and of similar form. Also, I do not understand how a DFA should recognize the same amount of a's at the front and at the end of a word.

You can always take $n = 1$ for any string in your language...


GCD of a pair of products I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use of the partial factorization I have to speed up the process?

In particular, each larger number is the product of $2^{15}$ smaller numbers, each of which is on the order of $2^{4000}$. I don't know anything about the factorization of the smaller numbers.

Edit:
While the input numbers are about 120,000,000 bits, the GCD is about 500,000 bits. The factors of the numbers are in particular in sequence. They are all integers in a consecutive range.

All of the GCD algorithms I've seen make use of the numbers directly, not in a partially factored form or anything. Are there any algorithms which could incorporate this information to speed things up?

You can compute the pairwise GCDs of the factors. You have to divide out the GCDs from the factors to avoid finding the same GCD factor twice:

a[1...m] = [given factors of A]
b[1...n] = [given factors of B]
g = 1
for i from 1 to m do
    c = a[i]
    for j from 1 to n do
        d = gcd(c, b[j])
        g = g * d
        c = a[i] / d
        b[j] = b[j] / d
return g

Unfortunately, I don't think that this is not notably faster than the computation of the GCD of the two numbers A and B.


The read tape in the definition of L and NL (logarithmic space) (DLOGSPACE, NLOGSPACE) (sublinear space) By the definition of L=DLOGSPACE or of NL=NLOGSPACE (or any sublinear space class) there is an extra tape (for the Turing machine): the input tape, which is only for reading  - but for arbitrary reading. The machine can read the first 10 cells and then maybe go back to read the 1st und 2nd cell.

My question is: If we restrict the way of reading that every cell is read only one time (in one direction: the 1st, 2nd, 3rd,... to the last cell of the input - and then nothing can be read of the input tape!), will we get same classes L and NL or will we lose some languages?

For a complexity class $\mathcal{C}$, we can define read-$k$-times $\mathcal{C}$ to be the set of problems $S \in \mathcal{C}$ for which there exists a $k$ such that an accepting computation for $S$ on input $w$ reads each bit at most $k$.

A consequence of a result from On lower bounds for read-$k$-times branching programs (1991) by Borodin, Razborov and Smolensky gives a separation between deterministic log space with unbounded reads and non-deterministic log space with bounded reads:

Proposition: There is a problem $S$ for which $S \in L$ but $S \not\in \text{read-}k\text{-times } NL$.

This means, to answer your question, we lose some languages since $L \not\subseteq \text{read-}k\text{-times }NL$ but $L \subseteq NL$.

My source of this proposition is from DynFO: A Parallel, Dynamic Complexity Class due to Patnaik & Immerman, who cite the BRS paper.


Converting function to bitwise only? I have a function to count upper bits of a 32 bit value. So if a number is 11100011111..., the result is 3 as there are 3 ones in the most significant place before a 0 is hit.

I need to convert the function to use only bitwise operations (no if statements or while loops) and the total number of operations should be lesser than 50.

Question: How can this be converted to bitwise operations only while keeping less than 50 ops?

Here is the Code:

  int count = 0;
  int i = 28;

  while(i >= 0) {
    int temp = (x>>i) & 0xF;
    i-=4;
    if(temp == 0xF) count+=4;
    else {
      int mask = 0x1;
      int a = (temp>>3) & mask;
      int b = (temp>>2) & mask;
      int c = (temp>>1) & mask;
      int d = temp & mask;

      if (a != 1) break;
        count+=1;
      if (b != 1) break;
        count+=1;
      if (c != 1) break;
        count+=1;
      if (d != 1) break;
        count+=1;
    }

Notations: I'll use the C notations for bitwise operations: $a \mathbin\& b$ (bitwise and), $a \mathbin| b$ (bitwise or), $a \mathbin\ll b$ (shift left), $a \mathbin\gg b$ (shift right). The shift operators are left-associative (e.g. $x \mathbin\gg m \mathbin\gg n = (x \mathbin\gg m) \mathbin\gg n$). The shift operations put zeroes in newly created bit positions: $a \mathbin\ll b = a \times 2^b$ and $a \mathbin\gg b = \lfloor a \times 2^{-b} \rfloor$. Sequences of digits with a line above (e.g. $\overline{11101000}$, $\overline{z^4z^3z^2z^1z^0}$) represent a number written in base 2 (binary).

If $x$ is an integer between $0$ and $2^N-1$, we say that $x$ is an $N$-bit number, and write $x = \overline{x^{N-1}x^{N-2}\ldots x^1x^0}$, i.e. $x^k$ is bit $k$ of $x$. Bits $k-1$ through $0$ constitute the $k$ least significant bits of $x$, and bits $N-1$ through $N-k$ constitute the $k$ most significant bits of $x$ (where $x$ is considered as an $N$-bit number).

Intuition

With 32 bits and 50 operations, an approach that looks at one bit of the input at a time isn't going to work. The next obvious thing to try is a recursive (dive-and-conquer approach) where you work on half the bits at a time. There are two simple ways to divide an $N$-bit number: into the $N/2$ most significant bits and the $N/2$ least significant bits, or into odd and even positions. Most/least significant looks promising, because the result counts how many most significant bits are 1.

Or we could approach the problem the other way: the result is a number between 0 and 32, a 6-bit number (for all but one input values, it's a 5-bit number). Can we find the bits of the result, one at a time?

Let $a$ be the input (a 32-bit number) and $z$ the output. Bit $5$ of $z$ is 1 iff $a$ is all-bits-1. Bit $4$ of $z$ is 1 iff the 16 most significant bits of $a$ are all 1 and $a$ is not all-bits-1. What about bit $3$? We have to discriminate on bit $4$: if it's 0, we look at the $8$ most significant bits of $a$ (with an exception when $a$ is all-bits-1); if it's 1, we look at bits $8$ through $15$ instead.

Expression in terms of bitwise operations

Let's express this in terms of bitwise operations. For the time being, assume we have a primitive operation $A_N$ on $N$-bit numbers such that $A_N(x) = 1$ if $x = 2^N-1$ (i.e. $x$ is all-bits-1) and $A_N(x) = 0$ otherwise.

$z^5 = A_{32}(a)$
if $z^5 = 0$ then $z^4 = 0$, else
$z^4 = A_{16}(a \mathbin\gg 16)$
if $z^5 = 0$ then $z^4 = 0$, else
if $z^4 = 0$ then $z^3 = A_8(a \mathbin\gg (16+8))$, else
$z^3 = A_8((a \mathbin\& \overline{1111111100000000}) \mathbin\gg 8)$

That's not very orderly: at this point we're looking to express $z^4$ and $z^3$ in similar way so that a recursion pattern can emerge. Furthermore we've used conditional statements which we're going to have to eliminate somehow. What seems constant is that $z^k$ is $A_{2^k}$ of some number. So what number? At each stage, we cut some number which is a slice of $a$ in half. To compute the next bit of the result we're looking at the most significant half of one of the halves from the previous step. Let's write $a_{k+1}$ for the input to the step that computes $z^k$ (so that we start with $a_6 = a$ to compute $z_5$). Then, leaving aside for a moment the case when $a = 2^{32}-1$ (in other words, we leave aside the case when $z^5=1$):

$a_5 = a_6$
$z^4 = A_{16}(a_5 \mathbin\gg 16)$
If $z^4 = 1$ then $a_4 = a_5 \mathbin\& (2^{16}-1)$, else $a_4 = a_5 \mathbin\gg 16$. It's awfully tempting to turn that 16 into $z^4 \mathbin\ll 4$, but it's on the wrong side. We could flip a bit (using xor), but this complicates the expression; instead, let's shift the other way: $a_4 = (a_5 \mathbin\& (2^{16}-1)) \mathbin\ll (z^4 \mathbin\ll 4) \mathbin\gg 4$.

And thus a pattern emerges:
$$\begin{align*}
  z^k &= A_{2^k}(a_{k+1} \mathbin\gg 2^k) \\
  a_k &= (a_{k+1} \mathbin\& (2^{2^k}-1)) \mathbin\ll (z^k \mathbin\ll k) \mathbin\gg k \\
\end{align*}$$

A simpler recursion

The initial case $z^5$ isn't right. It would be a simple matter to adjust the recursion pattern to accommodate it, but before doing that, I prefer to tweak the notation to reduce the number of shifts. When we compute $a_k$, we're aligning the extracted number to the right. Let's instead align to the left. Furthermore, let's drop the masking: we'll use a new predicate $B_m$ instead of $A_m$ which looks only at the appropriate bits. Define
$$ b_{k-1} = b_k \mathbin\ll (z^k \mathbin\ll k) $$
Define $B^n_m(x) = 1$ if the $2^n$-bit number $x$ has its $m$ most significant bits all set, and $B^n_m(x) = 0$ otherwise.
$$ z^k = B^n_{2^k}(b_k) $$

For a 32-bit number ($n=5$), we start with $b_5 = a$ and $z^5 = B^5_{32}(b_5)$ (check all 32 bits). Next we compute $b_4 = b_5 \mathbin\ll (z^5 \mathbin\ll 5)$; when $z^5=1$ (i.e. $a=2^n-1$) that sets $b_4 = 0$. We can then compute $z^4 = B^5_{16}(b_4)$ (look at the most significant 16 bits), then either $b_3 = b_4$ or $b_3 = b_4 \mathbin\ll 16$ depending on $z^4$, and so on until we find $z^0$.

Testing for all-bits-1

We're getting close. We still need to express that $B$ function in terms of bitwise operators. Note that so far, we've used 10 operations (2 shifts per step to compute $b_4$ through $b_0$). That leaves 40 operations to do the all-bits-1 check.

$B^n_1$ is easy: take the most significant bit and shift it into place, i.e. $B^n_1(x) = x \mathbin\gg (2^n-1)$. For $B^n_2$, we need to and the two most significant bits of $x$ together: $B^n_2(x) = (x \mathbin\gg (2^n-1)) \mathbin\& (x \mathbin\gg (2^n-2))$. Going on, we have $B^n_3(x) = (x \mathbin\gg (2^n-1)) \mathbin\& (x \mathbin\gg (2^n-2)) \mathbin\& (x \mathbin\gg (2^n-3))$. A recursive pattern emerges, but it's expensive: one shift and one and per bit. Linear is too slow, we need to go exponential.

Above we were taking the and of a single bit at a time. This is a waste: we can operate on $2^n$ bits in one go. Take $x$, shift left by $m$ and and with $x$: the result has its $m$ most significant bits all-1 iff $x$ has its $2m$ most significant bits all-1. Or in other words:
$$B^n_{2m}(x) = B^n_m(x \mathbin\& (x \mathbin\ll m))$$
Recall that $B^n_1(x) = x \mathbin\gg (2^n-1)$. We can compute $B^n_{2^k}$ in $2k+1$ operations. Thus we can compute $z^k$ from $b_{k+1}$ in $2k+1$; for $z^0$ through $z^n$, that's a total of $\sum_{k=0}^n (2k+1) = (n+1)^2$ operations.

Optimizing some shifts

We have a complete algorithm now, but it's a bit slow, we need to do a little optimization. Notice that we only ever use $z^k$ in the expression $z^k \mathbin\ll 2^k$. So instead of computing $z^k$, we'll directly compute that bit at its final position:
$$y_k = z^k \mathbin\ll k = \hat B^n_{2^k}(b_k) \mathbin\& (1 \mathbin\ll k)$$
where $\hat B^n_{m}(b_k)$ is computed as described above for $B^n_{2^k}(b_k)$, except that for the last shift (resulting from the expansion of $B^n_{1}(c)$ for some $c$), instead of taking $c \mathbin\gg (2^n-1)$, we take $c \mathbin\gg (2^n-1-k)$. Note that $b_{k-1} = b_k \mathbin\ll y_k$.

The cost so far:

one operation per result bit except the most significant one to compute $b_k$ (one shift) → $n$
1 operation per result bit except one to or everything together ($z = y_5 \mathbin| y_4 \mathbin| \ldots \mathbin| y_0$) → $n$
$(n+1)^2$ operations to compute the $B^n_{2^k}(b_k)$ values as seen above, plus one more to get $\hat B^n_{2^k}(b_k)$. That's one shift plus one and, times $(k+1)$ for each $k$, with $k$ ranging from $0$ to $n$. → $(n+1)(n+2)$

The total is $C(n) = (n+1)^2 + 3n + 1$ operations. For $n=5$, that's 52. We're almost there!

Further optimizations in the last steps

Let's see the last few operations once we get to $b_1$ (given here with $n=5$ as an example, but you can generalize to any $n \ge 2$).
$$\begin{gather*}
  c_1 = b_1 \mathbin\& (b_1 \mathbin\ll 1) \\
  y_1 = (c_1 \mathbin\gg 30) \mathbin\& \overline{10} \\
  b_0 = b_1 \mathbin\ll y_1 \\
  y_0 = (b_0 \mathbin\gg 31) \mathbin\& \overline{1} \\
\end{gather*}$$
Let's make this more concrete: let $u = b_1^{31}$ and $v = b_1^{30}$ be the two most significant bits of $b_1$ (i.e. $b_1 = \overline{uv\ldots}$ as a 32-bit number). We need to obtain $y_1 = 2$ if $u=v=1$ and $y_1=0$ otherwise; and $y_0 = 1$ if $u=1$ and $v=0$ and $y_0$ otherwise. At this stage, we can save some operations by aligning on the right instead of on the left. We take advantage of the fact that if you right-shift a 32-bit number by 30, you get a 2-bit number. The sequence of operations above can be replaced by the following sequence:
$$\begin{gather*}
  w = b_1 \mathbin\gg (2^n-2) \\
  y_1 = w \mathbin\& (w \mathbin\ll 1) \\
  b_0 = b_1 \mathbin\ll y_1 \\
  y_0 = b_0 \mathbin\gg (2^n-1) \\
\end{gather*}$$
That's 5 operations instead of 7, bringing us down to 50 for $n=5$, and more generally to $C'(n)=(n+1)^2+3n-1$.

Remarks

By the way, the computation of $b_{k-1}$ from $b_k$ can be done with just two temporary variables. When we obtain $y_k$, we can or it into an accumulator to obtain $z$. So we can do the whole computation with four $2^n$-bit registers.

Code

Here's the 32-bit case played out in Python syntax. The ck_j variables are temporaries used to compute $\hat B^5_{2^k}(b_k)$. I used a single-assignment style, you can get a classical imperative program by stripping all number suffixes from the variable names.

#!/usr/bin/env python
import sys

# Python does bignum arithmetic, but we absolutely need modulo 2^32 arithmetic
# in a few places.
def trim(x): return x & 0xffffffff
def bin5(x): return bin(0x100000000 | trim(x))[3:]

def f5(a, trail_optimization=True, trace=False):
    (y1, y0) = (None, None) # bring these variables to function scope
    b5 = a
    c5_5 = b5
    c5_4 = c5_5 & (c5_5 << 16)
    c5_3 = c5_4 & (c5_4 <<  8)
    c5_2 = c5_3 & (c5_3 <<  4)
    c5_1 = c5_2 & (c5_2 <<  2)
    c5_0 = c5_1 & (c5_1 <<  1)
    y5 = (c5_0 & (2**31)) >> (31 - 5)
    z5 = y5
    b4 = b5 << y5
    c4_4 = b4
    c4_3 = c4_4 & (c4_4 <<  8)
    c4_2 = c4_3 & (c4_3 <<  4)
    c4_1 = c4_2 & (c4_2 <<  2)
    c4_0 = c4_1 & (c4_1 <<  1)
    y4 = (c4_0 & (2**31)) >> (31 - 4)
    z4 = z5 | y4
    b3 = b4 << y4
    c3_3 = b3
    c3_2 = c3_3 & (c3_3 <<  4)
    c3_1 = c3_2 & (c3_2 <<  2)
    c3_0 = c3_1 & (c3_1 <<  1)
    y3 = (c3_0 & (2**31)) >> (31 - 3)
    z3 = z4 | y3
    b2 = b3 << y3
    c2_2 = b2
    c2_1 = c2_2 & (c2_2 <<  2)
    c2_0 = c2_1 & (c2_1 <<  1)
    y2 = (c2_0 & (2**31)) >> (31 - 2)

    z2 = z3 | y2
    b1 = b2 << y2
    if trail_optimization:
        b1 = trim(b1)
        w = b1 >> 30
        #if trace: print 'w=' + bin5(w)[-2:],
        y1 = w & (w << 1)
        b0 = b1 << y1
        b0 = trim(b0)
        y0 = b0 >> 31
    else:
        c1_1 = b1
        c1_0 = c1_1 & (c1_1 <<  1)
        y1 = (c1_0 & (2**31)) >> (31 - 1)
        b0 = b1 << y1
        c0_0 = b0
        y0 = (c0_0 & (2**31)) >> (31 - 0)
    z1 = z2 | y1
    z0 = z1 | y0
    if trace: print 'b5=' + bin5(b5), 'y5=' + str(y5),
    if trace: print 'b4=' + bin5(b4), 'y4=' + str(y4),
    if trace: print 'b3=' + bin5(b3), 'y3=' + str(y3),
    if trace: print 'b2=' + bin5(b2), 'y2=' + str(y2),
    if trace: print 'b1=' + bin5(b1), 'y1=' + str(y1),
    if trace: print 'b0=' + bin5(b0), 'y0=' + str(y0),
    return z0

if __name__ == '__main__':
    for i in xrange(33):
        x = (1 << 32) - (1 << i)
        print bin5(x), f5(x, trace=True)
        if 0 <= i <= 31:
            x = x - 1
            print bin5(x), f5(x, trace=True)


Knapsack problem 0/1 with even number of items So I need to solve the knapsack problem, but I need to make sure that the end solution consists of an even number of items.

I found this on an already existing question:

You can keep two tables with $n$ rows and $C$ columns:

$DP_{even}$ that saves the best knapsack solution with an even number of itens.
$DP_{odd}$ that saves the best knapsack solution with an odd number of itens.

To fill $DP_{even}$ you look at the previous best solution of $DP_{odd}$ plus a new item, or of $DP_{even}$ if you don't take the item:
  $$DP_{even}[i, j] = max(DP_{odd}[i - 1,j - c[i]] +  v[i], DP_{even}[i - 1, j]) $$
The same idea goes for $DP_{odd}$
$$DP_{odd}[i, j] = \max(DP_{even}[i - 1,j - c[i]] +  v[i], DP_{odd}[i - 1, j]) $$

Your solution will be in $DP_{even}[n, C]$

But how do I initialize both arrays, since when I intitialize them with 0 in the first row both arrays are going to be the same? Or am I making a false conclusion?

Edit: I already know how to solve the knapsack problem normally, so you don't need to explain that.

For the base case, the value is often decided manually based on the context of the problem. What should be the base value?

It is easy to see that $DP_{even}[0,0]$ should be $0$, and $DP_{even}[0,j]$ for $j>0$ should be $-\infty$. This is because the highest value you can get with considering none of the items and cost nothing is trivially 0, but the case where you consider none them but still cost something is impossible, hence we can safely assign it $-\infty$.

Now let's look at $DP_{odd}$. You might think that $DP_{odd}[0,0]$ is $0$, but following your definition, $DP_{odd}[0,0]$ means the highest value you can get with considering none of the items, and take an odd number of items and costs nothing. Notice the contradiction in this statement? You don't consider any items, then obviously you couldn't have taken an odd number of items! The same argument holds for all $DP_{odd}[0,j]$ for $j\geq 0$. Hence, they are all assigned $-\infty$.

To summarize, the base case is very similar. Both $DP_{even}[0,j]$ and $DP_{odd}[0,j]$ are mostly $-\infty$, except $DP_{even}[0,0]$ which is $0$. Now, you can safely run your recurrence relations on top of the base cases.


Dynamic Program to solve an NP-complete partitioning problem I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!

Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{N}$ for $i=1,...,n$.

The goal is to determine whether there exist two disjoint subsets $M,N \subset A$ such that the sum of all elements in $M$ is equal to exactly $\textit{twice}$ the sum of all elements in $N,$ and $M \not = \emptyset$ and $N \not = \emptyset.$

Let $\sigma(S)$ denote the sum of all the elements in $S$ and $A_i = \{a_1, \dots, a_i\}$.

Given, $i=0,\dots,n$ and $w \in \mathbb{Z}$,
define $OPT[i,w]$ as the mazimum cardinality of a subset $S \cup S' \subseteq A_i$ where $S \cap S' = \emptyset$
and $\sigma(S) - 2\sigma(S') = w$.
If no possible choice for $S$ and $S'$ exists, then let $OPT[i,w]=-\infty$.

According to the above definition:
$$
OPT[0, w] =
\begin{cases}
0 & \text{if } w=0 \\
-\infty & \text{if } w \neq 0 \\
\end{cases}
$$

For $i>0$:
$$
    OPT[i, w] = \max\{ OPT[i-1, w], 1 + OPT[i-1, w-a_i], 1+ OPT[i-1, w+2a_i] \}.
$$

The answer to your problem is true iff $OPT[n, 0] > 0$.
Each $OPT[i, w]$ can be computed in constant time (if you have already computed the values of $OPT[i-1, \cdot]$).
Moreover, there are only $O(n)$ possible choices for $i$ and $O(t)$ sensible choices for $w$, where $t = \sum_{i=1}^n a_i$.
This gives you a dynamic programming algorithm with time complexity $O(n t)$ and space complexity $O(t)$.


Can we construct a binary tree with width and height Θ(n)? we know this definition:

Given a binary tree, Width of a tree is maximum of widths of all levels.

Let us consider the below example tree.

     1
    /  \
   2    3
 /  \     \
4    5     8
          /  \
         6    7

For the above tree,
width of level 1 is 1,
width of level 2 is 2,
width of level 3 is 3
width of level 4 is 2.

So the maximum width of the tree is 3.

can we have a binary tree with Height $\Theta(n)$  and Width  $\Theta(n)$

My solution:
is YES. for example a binary tree with one-node:

     1

am i right?

Statements about $\Theta$-classes are statements about the behaviour of an algorithm/data structure, as (in this case) $n$ gets large. Thus, a single example can never prove such a statement. You'd have to provide a set that contains examples that become arbitrarily large and behave as desired. (The set, however, doesn't have to contain an example for every value of $n$.)

So you should try to construct such a set of examples. (And if you fail constantly, try to find out why. This might lead to a proof that no such set exists, i.e. the claim is false.)


Generalized Geography with repetitions Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes.  Last player to move wins.

  GG = {  : G is a directed graph, b is a node in G, and the next
                     player to play has a winning strategy for generalized
                     geography from start node b, i.e., there are moves for
                     the next player to win no matter how opponent plays }

This problem is well-known to be in PSPACE and EXPTIME-hard. My question is:
If we allow repetitions in GG, it still belongs to EXPTIME-hard?

If repetitions are allowed, the problem is in P, as the (immediate) losing nodes are the ones with no outgoing edges, first find these, then declare the nodes winning from which you can reach such a node, if you can reach only winning ones, its a losing node, and so on, rest are drawing.