Is GAP NP-hard with at most two balls per bins? The generalized assignment problem (GAP) [1] is given by:

Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and for each item $i$ and bin $j$, we are given a size $s(i, j)$ and a profit $p(i, j)$.
Objective: Find a subset $U ⊆ S$ that has a feasible packing in $B$ and maximizes the profit of the packing.

In [1], the authors proved that GAP is NP-hard even when:

$p(i,j) = 1$ for all items $i$ and bins $j$.
$s(i,j)=1$ or $s(i,j)=1+δ$ for all items $i$ and bins $j$.
$c(j)=3$ for all bins $j$.

Analyzing this instance, I can see that GAP is NP-hard when $p(i,j)=1$ for all items $i$ and bins $j$ and each bin can pack at most three balls. This observation raises the following question for me.

My question: Is GAP NP-hard when $p(i,j) = 1$ for all items $i$ and bins $j$ and each bin can pack at most two balls?

[1] A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

You can reduce numerical 3-dimensional matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\{x_1,\ldots,x_k\},Y=\{y_1,\ldots,y_k\},Z=\{z_1,\ldots,z_k\}$, you can construct $k$ bins with capacities $b-x_1+M+M^2,\ldots,b-x_k+M+M^2$, and $2k$ balls with sizes $y_1+M,\ldots,y_k+M, z_1+M^2,\ldots,z_k+M^2$, where $M$ is a very large number. Now there is a valid solution to the N3DM instance if and only if you can pack all the $2k$ balls.


Are grandparent classes also parents? Let's say I have three classes, Animal, Bird and Pigeon. If Bird extends Animal and Pigeon extends Bird, is Animal the parent class for both or is Bird?

So, for instance, if the constructor for Animal said "hi I am animal" and the  constructor for Bird said "hi am I bird", which will it say in class Pigeon if I call the super constructor?

You cannot answer this question unambiguously. Different  OOP languages implement OOP paradigm differently.

In Ruby you will get only "Hi, I am bird!"

class Animal
  def initialize
    puts "Hi, I am animal!"
  end
end

class Bird < Animal
  def initialize
    puts "Hi, I am bird!"
  end
end

class Pigeon < Bird
  def initialize
    super # <= call to the superclass
  end
end

pg = Pigeon.new

In PHP we get only "Hi, I am bird!"

<?php

   class Animal {

      public function __construct()
      {
        echo "I'm Animal";
      }

    }

    class Bird extends Animal {

       public function __construct()
       {
         echo "I'm Bird";
       }

    }

   class Pigeon extends Bird {

      public function __construct()
      {
         parent::__construct();
      }

    }

   $Pigeon = new Pigeon();

  ?>

While in C++ you will get both "Hi I am animal!" and "Hi I am Bird!"

#include <iostream>
using namespace std;

class Animal
{
   public:
   Animal()
   {
     cout << "Hi I am animal!" << endl;
   }
};

class Bird : public Animal
{
  public:
  Bird()
  {
    cout << "Hi I am Bird!" << endl;
  }
};

class Pigeon : public Bird
{
  public:
  Pigeon():Bird(){} // <= call to the base constructor
};

int main()
{
  Pigeon pg;
}

In Swift (Apple) we get both, too

class Animal {
  public init() {
    print("I'm Animal")
  }
}

class Bird: Animal {
   public override init() {
     print("I'm Bird")
   }
}

class Pigeon: Bird {
   public override init() {
    super.init()
   }
}

var pigeon = Pigeon()

To understand why, you should get into details of how C++ implements OOP (vtables and etc.) and how Ruby classes lookup its methods and constants in the hierarchy, and other languages.

In addition if you want to see Object Oriented "Nightmare" then have a look at Lua, though I like it.

As to your question in the title: "Are grandparent classes also parents",
of course subclasses are related to all super-classes up in the hierarchy chain, but that relationship are implemented differently in different programming languages.


Identical register input operands in assembly The question is not specific to any processor.
Can I have an assembly instruction, like:
 ADD R1 R0 R0

R1 is the destination.
My understanding is that, if the register file in a processor supports 2 simultaneous reads in a clock cycle (i.e. 2 read ports), two different registers can be read. But for 2 same input registers, this case has to be handled explicitly wherein the input can be duplicated after reading the first operand, and if that is not supported, the register file MUST have 2 read ports in one clock cycle, if not it might lead to a structural hazard.
I would like to know if my understanding is right.
EDIT:
And also do, any processors (current/old) handle this case, explicitly.
Thanks in advance.

R1 <- R0 + R0 works in every processor that permits three register operands.  Nothing special needs to be done to deal with the same register driving multiple read ports.

Each register-file read port is just a multiplexer.  If you have $N$ registers driving the $N$ inputs of one $N$-to-$1$ multiplexer and the same $N$ registers driving the $N$ inputs of a different $N$-to-$1$ multiplexer, there's no constraint that says that both multiplexer selects can't be set to the same register.


What can't be done with a neural network This reference from the german wikipedia article on neural networks states:

  There are also many other important problems that are so difficult that a neural network will be unable to learn them without memorizing the entire training set, such as:

  Predicting random or pseudo-random numbers.
  Factoring large integers.
  Determining whether a large integer is prime or composite.
  Decrypting anything encrypted by a good algorithm.

Can someone explain, why this limitation should hold for all kinds of neural networks and for any advances in the future?

Are there any formal possibilities to prove that this problems cant be solved with a neural network?

Lets look at the third note. There are many insights on the distribution of prime numbers and this paper shows, that the calculations for proving that an integer is a prime number, can be done in polynomial time (PRIMES is in P). So why is this problem "to difficult" to be solved by a neural network?

This paper introduces a finite size neural network and proves that it can simulate a Turing Machine, meaning that this NN is Turing complete. Thus anything that may be computed using TMs can be computed by this type of NNs. You may want to read this too.


Hoare partitioning scheme in Quicksort I'm reading about Quicksort algorithm, specifically using the Hoare partitioning scheme.

Wikipedia page says, that when choosing a pivot element one can use both hi and lo indexes. However, when implementing the same code in Python, my code fails in a very specific circumstances. My python code is a translation of the pseudo-code from Wikipedia.

def swap(A, i, j):
   A[i], A[j] = A[j], A[i]

def quick_sort_hoare(A, lo, hi):
    if lo < hi:
        p = hoare_part(A, lo, hi)
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)

def hoare_part(A, lo, hi):
    i = lo - 1
    j = hi + 1

    pivot = A[lo]

    while True:
        while True:
            i += 1
            if A[i] >= pivot:
                break

        while True:
            j -= 1
            if A[j] <= pivot:
                break

        if i >= j:
            return j

        swap(A, i, j)

This particular code works for many-many test-cases generated at random. However if I put  pivot = A[hi] in partitioning, sometimes it fails. Specifically, when the last element(i.e. pviot) appears to be the largest in the array at hand. In that case i appears to be equal the length of the array and everything goes to the infinite recursion.

Furthermore, in Introduction to Algorithms by Cormen et al., we see the following pseudo-code for the same partitioning:

This piece of code seems to be identical to the one from Wikipedia. Moreover, seems like the code would fail on their example. Because I understand this very unlikely to be the case for them to make this mistake, I'm wrong somewhere.

So my questions are:

What am I getting wrong?
Can hi be used for pivoting or there is a very specific fundamental reason to pick A[lo]?

"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.
The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last two lines of code is how to determine the index that will be used by that first two lines of code to split the part of array between lo and hi.
#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.
However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.
When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one splitting index is returned when two indices iand j crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.
#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go over that problem closely.


Is the decision problem, for a Turing Machine are there any input strings rejected decidable? Given a Turing Machine T, are there any input strings rejected by T. I need to decide whether this is decidable or recursively enumerable. I think it's undecidable, but I'm not sure how to prove it.
My initial approach would be to reduce the Halting Problem as either a string will 1)halt on final state i.e accepted or 2)halt on non-final state and go in a loop
Perhaps, there is another approach involving diagonalization where I can prove that the diagonalization language is finite - how do I do that?

Let us start by properly defining your language as say
$$L = \{\langle M \rangle \mid M \text{ rejects some input } x \in \Sigma^\ast\}$$
where $\langle \cdot \rangle$ denotes some suitable encoding over our alphabet $\Sigma$.
To reduce $L$ to the halting problem $\mathrm{Halt} = \{\langle M, w \rangle \mid M \text{ halts on } w\}$ we consider some $\mathrm{Halt}$ instance consisting of a TM $M$ and some input $w$ and define a new TM $M_w$ which always, no matter what input it is given, just simulates the behavior of $M$ on $w$ with the slight change that it rejects if $M$ accepts, i.e. $M_w$ rejects precisely if $M$ halts on $w$ and does not halt if $M$ does not halt on $w$.
Note that $M_w$ can be algorithmically constructed from $M$ and $w$.
We see that $\langle M, w \rangle \in \mathrm{Halt}$ if and only if $\langle M_w \rangle \in L$, i.e. we have shown that the halting problem reduces to $L$ and thus $L$ is undecidable.
However, $L$ is also recursively enumerable: Fix some ordering of $\Sigma^\ast$ and iteratively execute $M$ on the first $n$ strings of $\Sigma^\ast$ for $n$ steps.
If $M$ rejects some string in $\Sigma^\ast$, this procedure will detect it in finitely many steps, showing that $L$ is semi-decidable and hence recursively enumerable.


How to Get Started in Computer Science I am wondering how to get started in studying theoretical computer science and how to apply it to my programming. I am fairly comfortable with basic programming, having been programming in mainly C++ but also Java for the past couple of years, so I don't necessarily need an introduction to programming.

What I am looking for to start is perhaps something fairly broad, so that it gives a wide overview of computer science, as I don't know exactly where I want to study within it yet. But it could also be nice to have directions of where to look to continue studying a specific aspect of it. However, this is just what I think could be helpful, and I am open to any recommendations.

Theoretical computer science means different things to different people. However, here are some areas which are commonly taught in undergraduate theoretical computer science classes:

Combinatorics and elementary set theory. This serves as prerequisite to all that follows.
Data structures and algorithms. One standard textbook is Introduction to algorithms, but it might be too advanced if you're just starting out.
Computability and automata theory. One standard textbook is Introduction to the theory of computation by Michael Sipser.

In some places, another core subject is functional programming and labmda calculus.

An undergraduate degree in computer science typically deals with several other topics, such as operating systems, networking, and sometimes compilation.


If a deterministic finite automaton recognizes a language, must that language contain every accepting input? May a DFA recognize a language which is a proper subset of the set of all accepted inputs?

For instance, if there is a DFA which decides if an input $W$ has $w_0 = w_n$, can it recognize a language $L$ where there is some $\sigma \in \Sigma$ that does not exist in any element of $L$?

No.
The language (only one!) recognized by a DFA is the set of all inputs it accepts.
The definition of a DFA also includes its alphabet, so you have to consider that an intrinsic part of the DFA. If you change the alphabet at all, you now have a new and different DFA, which potentially recognizes a different language.


Where do transformational grammars stand in the Chomsky Hierarchy? From what I understand, natural language are too complicated to be generated by a context-free grammar, yet parsing a context-sensitive grammar is too computationally demanding for our brain to be continuously performing. So it seems that if our brain indeed has a "syntax" module to parse sentences as Chomsky claims it does, then whatever it's doing should sit somewhere between CFGs and CSGs in terms of computational complexity.

I'm really not familiar at all with Linguistics in general and even less so with Chomsky's work, but (correct me if I'm wrong) the point of transformational grammars was to explain this?

For those not familiar, a transformational grammar consists of a CFG to generate syntactically valid sentences, and also on top of this "transformational" rules, that transform these valid trees to form other valid trees. A common example is affirmative->question transformation ("John has eaten all the heirloom tomatoes." -> "Has John eaten all the heirloom tomatoes?").

It is not clear to me why such tree transformations couldn't be integrated into the CFGs by adding more rules (for example, question-form sentences can clearly be generated instead of being transformed from an affirmative sentence).

If I am right (in that transformational grammars sit between CFGs and CSGs), could someone give me an example showing both relations (that TGs are more expressive than CFGs but less expressive than CSGs). If I'm wrong, then please help me increase my knowledge of linguistics by pointing me towards valid readings.

I was taught in linguistics class that Chomsky abandoned his original arbitrary transformations after they were found to produce Turing completeness. See e.g. the Oxford Handbook of Linguistic Interfaces, p. 543; I am unable to locate the original reference.

He subsequently developed a formalism with more restricted transformations; the version I was taught was called Government and Binding Theory.

Some details are in Wikipedia under Transformational grammar.

While searching for references, I ran into a highly readable article on this matter by Geoffrey Pullum, which rejects Chomsky's original notion of transformations for purely linguistic reasons.


Logical characterization of P versus NP problem (and references for least fixed point logic) Wikipedia says the following (and more) about the logical characterization of the P versus NP problem here:

  Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?"

My question is, has there been any work done to tackle the P versus NP problem from this logical angle, by reasoning about existential second-order logic and first-order logic with least fixed point?

And more generally, what are some good references for learning about least fixed point logic?

Your second question first. The context of your question is called descriptive complexity theory. In this context, I would suggest the book Finite Model Theory by Heinz-Dieter Ebbinghaus and Jörg Flum. As far as I recall it thoroughly covers both logics and their connection to P, respectively NP.

Now to your first question. Of course, as soon as both complexity classes had been characterized by logics, there were hopes to settle the P=NP question this way. Yet by now the problem has eluded this approach for several decades. One would need to pick some problem from NP and show that it is not expressible in FO(LFP) (first-order logic with least-fixed point operators). Essentially the only tool for proving non-expressibility are Ehrenfeucht–Fraïssé games. These games are notoriously hard to analyze in the presence of non-monadic second-order variables, which are needed in the case of FO(LFP). See also the paper https://eccc.weizmann.ac.il/report/2013/065/ by Yijia Chen and Jörg Flum.


Data structure for finding nearest squares from current square For my project I can have 0-500 moving squares. The largest possible square width is at most 3 times longer than the smallest possible square width. The squares can move up to 3 of their own body's width per second. About 1 square is added and about 1 square is deleted every second.

What I'm trying to implement now is a neural network to drive the speed and direction of the squares. Each square will have their own neural network which will take the x and y position of the 5 nearest squares to it. To find the nearest squares, I will be taking the euclidean distance from the center of their squares bodies.

My problem is that calculating the distance of each square to every single other square - to find its 5 nearest other squares - is going to make my program run at a snail's pace.

So what is a good data structure I could use to reduce the number of checks I'm performing?

Also I heard that kd-trees were good at finding the nearest neighbor. However, because the squares are going to be moving a lot I'm not sure if it'd actually be the best data structure to use.

Since you only measure distances from the centers of the squares, you can restate your problem as follows:
Maintain a dynamic collection $X$ of $n$ points in Euclidean space so that you can quickly find the $k$ nearest neighbors in $X \setminus \{p\}$ of a query point $p \in X$.

Using the data structure described here you can maintain such a collection in $O(\log^3 n)$ expected amortized time per insertion and $O(\log^6 n)$ expected amortized time per deletion,  after a preproessing requiring $O(n \log^2 n)$ expected time.

The data structure supports nearest neighbor queries (given a point $q$, report the point in $X$ that is closest to $q$) in $O(\log^2 n)$ worst-case time. Then, you can report the $k$ nearest neighbors of $p \in X$ in $O(k \log^6 n)$ expected amortized time as follows:

Delete $p$ from $X$ in $O(\log^6 n)$ expected amortized time.
Repeat $k$ times:

Query the data structure for the nearest neighbor $p' \in X$ of $p$ in $O(\log^2 n)$ worst-case time.
Report $p'$ as one of the $k$ nearest neighbors of $p$.
Delete $p'$ from $X$ in $O(\log^6 n)$ expected amortized time.

Reinsert all deleted points in $X$ in $O(k \log^3 n)$ expected amortized time.


List of major Open Problems in Computational Complexity and their Likelihood? I remember reading an article/paper (or perhaps a talk, most probably by Scott Arranson) where he lists the major open problems and their likelihood of being true or false in a table/graph. This is listed along with the 'surprise factor' of each result if its true/false.

I am unable to locate the article though. I wonder if someone remembers the article and can help. I am aware of a similar one by Ryan Williams but I am looking for the other one.

P.S. I know its a silly request. Apologies. But, still need it.

What you are searching for could be Some Estimated Likelihoods
For Computational Complexity by R. Ryan Williams, 2018.

Here are "Some Estimated Likelihoods for Some Major Open Problems" in that paper. Note that "The numerical values of my 'estimated likelihoods' are (obviously) nothing
too rigorous. What is more important is the relative measure between problems."


Why addition algorithm is not pseudo- polynomial? There is something I don't understand.

In the Subset Sum problem, in the Dynamic Programming solution, because of  binary representation of the sum T, we say it is pseudo-polynomial in run time; we must sum in the worst case from 1 to T.

So I don't understand why the Addition algorithm is not pseudo-polynomial, when we can add great numbers too.

The reason is that the runtime of addition is proportional to the number of digits, not the value of the numbers, as it is for subset sum. Remember that the number of digits is the size of the input.


Do any single-cell organisms exist that approximate NP-hard problems within a factor better than $1/2$ $log$2? I've seen on Wikipedia; that set covering cannot be approximated in polynomial time to within a factor mentioned above. Unless $NP$ has quasipoly-time algorithms.
Now, this must pertain to classical algorithms and does not mention any approximation algorithms that may only work in nature.
(eg. Things like Amoebas solving $TSP$ problems)

Do any single-cell organisms show any promise in solving $NP$-hard problems in polynomial-time?

Or approximating them better than any known classical algorithms?

In the realm of classical physics (where you don't need quantum mechanics to predict what is going on), we have no known method of computation that will be significantly faster than a standard classical computer.  Indeed, it is a standard belief that none exists.
The one exception is quantum mechanics.  Quantum computers are believed to be able to solve some problems significantly faster than classical computers -- though only a few special problems; for most, they offer no benefit (and quantum computers are not expected to offer any significant speedup for NP-complete problems).  It is a standard belief that no physical process that can be described by quantum mechanics offers any significant speedup over a quantum computer (in particular, a quantum computer is universal and can simulate any quantum mechanical process).
In short, the answer to your question is "no, there is no known physical process that holds any promise for solving NP-hard problems in polynomial time".


Generating regular expressions not containing abc Let sigma = {a,b,c}. How do I generate a language L that does not containg abc?
Any guidance is appreciated!

Design a DFA that recognizes "abc" (make sure to include all transitions). Complement it (make accepting states non-accepting, and make non-accepting states accepting) in order to get a DFA for $L = \Sigma^* \setminus \{ abc \}$. Finally, write down the regular expression of the complemented DFA.

As a brute force solution that does not use DFAs: write a regular expression for all words of lengths 0, 1, 2, and more than 3. This should be easy.
Then write, a regular expression for all words of length 3 except abc.
For example:
$(b+c)(a+b+c)^2 + ab(a+b) + a(a+c)(a+b+c)$

Take the union of all the above REs.


Turing machine for $0^{3^k} 1^{p}$ Hey guys so I picked up Introduction to the Theory of Computation and started studying finite automata and Turing machines. I was given the following language as an exercise in class, in which I need to build a Turing machine with only one tape and no extra tape space that accepts the following language:
$$\{0^{3^k} 1^p, \text{ where $k > 0$ and $p$ is a multiple of $k$}\}$$
How can one build a single tape Turing machine that accepts this kind of language without using any extra tape space?
I found an example for $\{0^n 1^n\}$ in Introduction to the Theory of Computation but I cannot figure out how to build a machine for the language mentioned above.

This problem can be solved in two steps. First, you need to work out the $k$ by repeatedly "dividing" the string by $3$, and storing how many times this was repeated. For example, each "division" will process the zeros in triplets. Each triplet will replaced by one zero, and in the first triplet processed you store a "1", as an indicator that you performed one division (since after erasing the first triplet you will have the space to store this "1"). Then you have to bring all the new zeros together and repeat the procedure. The number of ones you have written will be equal to $k$ (and if at some point you cannot perform the division, that is you don't have a power of three - you reject the language).
Next, you begin erasing the ones that come after zeros. Each turn will consist of wiping out exactly $k$ ones - for example the $k$ ones that you have on the left can be replaced by zeros in order to indicate that a one on the right has been erased. At the end of the turn, you replace all the zeros by ones again. Again, if you cannot perform the whole round, you must reject the language.


Difference between the languages accepted by two DFAs with different initial state/accepting states? Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.

Given two DFAs $A = (Q, \Sigma, \delta, q_1, F_1)$ and $B = (Q, \Sigma, \delta, q_2, F_2)$ where the set of states, the input alphabet and the transition function of $A$ and $B$ are the same, the initial states and the final(accepting) states could be different. Let $L_1$ and $L_2$ be the languages accepted by $A$ and $B$, respectively.

There are four cases:

$q_1 = q_2$ and $F_1 = F_2$.
$q_1 \neq q_2$ and $F_1 = F_2$.
$q_1 = q_2$ and $F_1 \neq F_2$.
$q_1 \neq q_2$ and $F_1 \neq F_2$.

My question is

    What are the differences between $L_1$ and $L_2$
     in cases 2, 3 and 4?

I have a more specific question along this line,

The transition monoid of an automaton is the set of all functions on the set of states
induced by input strings. See the page for more details. The transition monoid can be regarded as a monoid acting on the set of states. See this Wiki page for more details.

In many literatures, an automaton is called strongly connected when the monoid action is transitive, i.e. there is always at least one transition (input string) from one state to another state.

    If $A$ and $B$ are strongly connected automata, what are the differences between $L_1$ and $L_2$ in cases 2, 3 and 4 above?

Any literatures discussing these issues in details?

I have searched many books and articles and found nothing helpful so far. I believe I don't have the appropriate key words yet. Thus I am seeking help. Any pointers/references will be appreciated very much.

Since $A,B$ are strongly connected, then if $q_1\neq q_2$, there exist words $p_1,p_2$ such that $\delta(q_1,p_1)=q_2$ and $\delta(q_2,p_2)=q_1$.

Consider case 2, then $w\in L(A)$ iff $p_2w\in L(B)$, and $x\in L(B)$ iff $p_1 x\in L(A)$. So you can add a prefix to switch between languages.

Consider case 3, then again - by strong connectivity there at most $|F_1|$ words $s_1,...,s_k$ such that for every $q_i\in F_1$ you have that $\delta(q_i,s_i)\in F_2$, and similarly for the other direction (from $B$ to $A$).

Thus, you can compose suffixes to switch between languages.

Combining these you can characterize the differences using prefixes and suffixes.
For example, in case 4, $w\in L(B)$ iff $p_1 w s_i$ in $L(A)$ for some $s_i$ in a predetermined finite set.

In fact, you can even say something interesting about these words: define $C$ to be the DFA where $q_1$ is the initial state and $q_2$ is the final state, then in case 2 you have $L(B)=L(C)\cdot L(A)$ (and similarly for the other direction).

As for the suffixes, things are more involved, since you cannot predetermine in which final state you will end. I'm not sure you can write this as a concatenation, but you can write $L(B)=\bigcup_{q\in F_1}L(A_q)\cdot L(E_q)$ where $A_q$ is the DFA obtained from $A$ be setting $F=\{q\}$, and $E_q$ is a DFA that starts in $q$ with final states $F_2$.

For case 4 you can combine the two.

You may be concerned that this is not a real answer, but rather just a characterization of properties using words rather than states, but this is a typical answer in this field (similarly to the Myhill-Nerode theorem).


Async Distributed Algorithm Time Complexity In theory of distributed systems, I understand message complexity and time complexity are common performance measures, with the first being the number of messages sent in the overall execution of the algorithm, and the time being the number of "steps" it takes to complete the algorithm.

My question is, with asynchronous distributed algorithms, where we assume that at least one message is received and processed per step, how can the time complexity differ from the message complexity? If I have to send m messages to complete the algorithm, it seems to me the worst case time complexity would be $m$, sending one message per time step. For example, the time complexity of an async flood algorithm is $O(n)$ while the message complexity is $O(m)$. Why is the time complexity not $O(m)$ too? Here $m$ is the number of edges and $n$ is the number of vertices. Same goes for constructing a rooted spanning tree.

Again, this is for async systems where messages don't have to be received in parallel.

In a distributed system, messages can be sent in parallel.  Vertex #1 can send a message at the same time as vertex #2 is sending a message.  So, the total amount of time to complete the algorithm might be much less than the total number of messages sent.


Why does Insertion sort take linear time in this case? Remove any 5 elements from a sorted array of n items and replace them with 5 new elements.
Why does running Insertion sort again on this array take linear O(n) time, I tried counting the number of swaps when running Insertion sort again, and noticed every element is shifted by at most 5 places(not sure why), I cannot get the intuition behind why this takes linear time?
Wouldn't the new elements affect the position of the unchanged items in the array as well?
Appreciate any explanation on this!

Count the number of times each of the 5 new element is moved in the array:
The areay is of length $n$, and thus each of the 5 elements move at most $n$ times. The place of all other elements is correct, and thus there is at most $5n$ swaps required to "correct" the array, hence $O(n)$ swaps.


Does this algorithm on a circular linked list ever terminate? Suppose we have a circular linked list that has nodes $1$ to $n$. L is a pointer that points to node 1 (with label $1$). Note i has a link to i+1 and we have a link from node n to node 1 because the list is circular.

Now we have following pesudo-code:

Int SO(LIST *L) {

  While ( L->Next != L ) {
    L->Next = L->Next->Next;
    L = L->Next;
  }

  return L->Data;
}

The question is: what is the output for $n=729$ and $n=2200$ what is the output of the above code.

My solution: I check the pesudo-code. My idea is this code has a problem and  L and L->Next never become equal so an infinite loop occurs. Is this correct?

The algorithm will always terminate. Look at the case where $n=2$. Initially we'll have 1->next = 2 and 2->next = 1. In the first iteration we'll change 1->next to 1->next->next = (1->next)->next = 2->next = 1 so 1->next will point to 1 and the loop termination condition applies, so we bail and return 1->data.

If $n>2$, every iteration of the loop will point around a node, eliminating it forever from consideration, so every iteration of the loop decreases the number of nodes in play, so we'll always get to the $n=2$ case eventually and then halt.

It might help to think of this as the nightmarish situation where a group of $n$ people have been captured by bloodthirsty pirates. The pirates arrange the group in a circle and, starting at person 1, go around the circle, shooting every other person until only one remains. Where do you want to position yourself so that you are the last surviving person?

This is a well-known problem, called the problem of Josephus, and is often assigned as an exercise in a beginning programming class. The solution is nifty: Given $n$, write it as $n=2^m+k$, where $0\le k < 2^m$, then the last survivor is the one in initial position $2k+1$ (starting at position 1). Given this, we have that with $n=729$ the survivor will be the one in position 435 and with $n=2200$ the survivor (after a heck of a lot of shooting) will be the one in initial position 305.


A task-scheduling problem as a matroid (CLRS book) I don't understand very well section 16.5 of the 3rd edition of the famous Introduction to Algorithms book, known as CLRS. It defines the problem of scheduling unit-time tasks with deadlines and penalties for a single processor with the following inputs:

a set $S = {a_{1}, a_{2}, ..., a_{n}}$ of $n$ unit-time tasks
a set of $n$ integer deadlines ${d_{1}, d_{2}, ..., d_{n}}$ such that each $d_{i}$ satisfies $1 \leq d_{i} \leq n$ and task $a_i$ is supposed to finish by time $d_i$
a set of of $n$ nonnegative weights or penalties ${w_{1}, w_{2}, ..., w_{n}}$, such that we incur a penalty of $w_i$ if task $a_i$ is not finished by time $d_i$, and we incur no penalty if a task finished by its deadline.

And the following goal:

We wish to find a schedule for S that minimizes the total penalty incurred for
missed deadlines.

NOTE: I'm aware that there are other posts here about similar problems (scheduling unit-time tasks with profit etc.), but I'm trying to understand this particular explanation, on the CLRS book.
So, I'll get now to the point. On the same page (444), where it explains the core idea, the book talks about the early-first form and the canonical form, without mentioning the penalties anymore: it talks exclusively about the deadlines (I'm not going to copy the whole text, I'm assuming that who answers the question owns the book).
My first question: because the whole reasoning does not mention penalties, it looks like to me it will work only if all the penalties are equal, which would be a different problem. I'm probably missing something here. But what? No matter how you order the tasks based on deadlines, you cannot possibly minimize the penalties without taking them into account. In other words, even if you hit 99/100 deadlines and missed the deadline for that one single task, its penalty might be bigger than the penalties of all the other tasks combined. I don't understand CRLS's logic, in this particular case.
My second question: on the next page (445), CLRS mentions the penalties in one place:

The problem of minimizing the sum of the penalties of the late tasks is the same
as the problem of maximizing the sum of the penalties of the early tasks. The
following theorem thus ensures that we can use the greedy algorithm to find an
independent set A of tasks with the maximum total penalty.

And after that it mentions theorem 16.13 claiming substantially that $(S, I)$ is a matroid.
I believe I understand that, it makes sense. But, how can we determine in the first place the subset of the early tasks without taking into account the actual values of each $w_i$ penalty? In my understanding, that's not possible. I wouldn't dare claiming there's a mistake in the CLRS book, but that's my only theory at the moment. Very likely I'm wrong, but I cannot figure out why. On page 444, it mentions twice "monotonically increasing deadlines" but never anything like "monotonically decreasing penalties".
On the other side, I've done some research and I've read about variations of this problem with profits instead of penalties. I've understood that the tasks need to be ordered by monotonically decreasing profit. After doing that, we put each task as close to its deadline as possible, and move left only (= early) when the slot is already taken. That makes completely sense, because the profit is taken into account. If we consider penalties as negative profits, shouldn't the same logic apply? But, even with a different logic, how can we ignore the $w_i$ values?

I believe you are completely correct but mixed up two things from the book, namely the order in which the tasks are selected and the order in which the tasks are scheduled.
The greedy algorithm here indeed orders the task by their weights $w_i$ (as for every max-weight greedy algorithm on matroids). Given a set $A$ of tasks that are independent, i.e. they can somehow be scheduled so that no task is late, one way to schedule those tasks, such that none of them is late is by ordering those tasks (and only those, you omit the the tasks that are not in $A$) in increasing order of their due dates $d_j$.
Regarding your example with 99/100 tasks early: The one with the biggest weight (or penalty) is definitely one of the 99 tasks, as it is the first one to be selected by the greedy algorithm (unless its due date is non-positive). However, this task does not need to be the one that appears in the schedule first.
In essence, the order in which the greedy algorithm selects the tasks is not related to the order in which the tasks are scheduled.
Towards your second question: Whether a task is early only depends on its due date. The corresponding independence check for the matroid would work as follows:

The empty set is independent (no task is late).
Given set $A$ and task $a \notin A$, order all tasks in $A+a = [a_1, \ldots, a_m]$ by $d_j$ (such that $d_1 \leq \ldots \leq d_m$) and check for all $a_j \in A+a$ whether $j \leq d_j$ (as you have unit processing times).

The reason why this works, is subject of Lemma 16.12 (in the 3rd edition at least. the equivalence of three statements).


PSPACE-completeness of DFA intersection problem Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness.

It seems to me that I understand, why this problem lies in PSPACE: if $ n_1,\dots, n_k $ are the numbers of states, then one can take the product of these DFA and get that if there is a recognisable string, then there is a recognisable string of length $ \le n_1\dots n_k$. Then we can non-deterministically guess this string and use Savitch theorem.

So, the question is, how to prove PSPACE-hardness? Should I reduce any given TM to this problem, or maybe some known problem like QBF?

Your proof that the problem is in PSPACE is not quite correct. The problem is that the product $n_1 \cdots n_k$ is not bounded by a polynomial in the input length $n_1 + \dots + n_k$. The correct way to do it is to directly apply Savitch's theorem to the NPSPACE machine that nondeterministically guesses a path through the product graph. The difference is that, while an accepting path can indeed be as long as $n_1 \dots n_k$, the machine only guesses one symbol at a time and never stores the entire input string in memory, so we stay within the polynomial space limit.

It is a well-known fact that this problem is PSPACE-hard, but the only proof that I am aware of is not particularly trivial. I believe the first proof was given in:

  Dexter Kozen. Lower Bounds for Natural Proof Systems. FOCS 1977: 254-266.

The proof involves constructing a mess of DFAs which collectively enforce all the necessary constraints to require that any string in the intersection language is a trace of the execution of a polynomial space Turing machine that leads to an accepting configuration.


Complexity of an instance of a NP-complete problem I am trying to prove the NP-Completeness of problem [A].

I know there is a well-known NP-Complete problem called problem [B].

I can model [A] into an instance of [B] ([B] is a very general problem and when I assign some edges a weight value then it becomes [A]).

Is this sufficient to say [A] is NP-Complete?

To show $A$ is NP-complete, you need to prove the following:

$A \in \mathbf{NP}$
$A$ is NP-hard: any problem $B \in \mathbf{NP}$ is poly-time (many-one) reducible to $A$

or

equivalently (because reduction relations are transitive): there is an NP-hard problem $B$ which is poly-time (many-one) reducible to $B$.

You have shown neither, so you cannot say $A$ is NP-complete.

What you did do is a many-one reduction from $A$ to $B$, but you want the other way around. In addition, you also need to show the reduction is efficient, that is, takes polynomial time; you did not explicitly state whether this is the case. And, of course, you must not forget to show $A \in \mathbf{NP}$ (which is usually the easier part).


What is the difference between a state machine and a database I didn't study computer science as a degree, so whilst having studied computer science, there are still gaps in my knowledge. Everything I read about 'state' sounds like some form of 'data' but kept in memory as opposed to a database. This keeps leading me to the question: is a state machine not just a way of storing data, like a database.
There is probably a very obvious answer to this, but I can't seem to find anything about it when searching Google, which leads me to think I'm way off in my understanding somewhere. Any pointers (not the memory type) into some good reading would be super helpful. Thanks!

State machines and databases are quite different entities, and their usage (or functionality) is very different.
In this answer, I'll just try to separate them with respect to the similarity you mention. This is by no means a comprehensive description of neither state machines nor databases.
The states of a state machine can indeed be thought of as representing data (although this is not always obvious, and sometimes state machines do not reveal what data they store in their states). However, the crucial element of a state machine is the transitions between the states, which represent the behaviour of the machine.
That is, a state machine does something. It computes. During its run (or runs, in nondeterministic models), it moves from state to state according to some predetermined set of rules, and possibly according to a given input, and this process is called a computation. At the end of the computation (if it's finite), you might receive an output, from which you can derive some information.
For example, a Turing machine receives an input and if it halts, tells you whether the input is accepted or rejected, from which you can formalize a decision problem.
Similarly, an automaton does the same, but without external memory.
In contrast, a database merely stores data. How this storage is done, which operations are allowed on the data, and what their respective complexity is, are all interesting questions, and their answers depend on the type of database you use.
However, databases do not compute anything by themselves, they just store the data, possibly efficiently.


Bit operations; Treating a number like an array Are there features in programming languages that allow you to directly access the $k^{th}$ bit of a number. Treating it like an integer.

I'm not talking of using bit shifting to retrieve a number. But directly access the bit at index $i$ of a number as if it were an array.

I'm looking at this feature to replace shifting to write an algorithm I was working on. If it isn't faster than shifting, then such a feature would be pointless.

I didn't ask this on stack overflow as this isn't about a specific programming language, but about whether programming languages in general have this feature.

Also are there language features for inverting the bits(a specific bit or as many as needed) of a number?

The answer depends on the programming language and, to some extent, on the CPU. For any practical purpose, though, extracting the $k$th bit is an $O(1)$ operation even on a "big integer" stored on several machine words, since in order to extract the $k$th bit, you can use the following algorithm:

Determine which word the $k$th bit is in, and which bit in the word.
Extract the appropriate bit from the appropriate word.

In practice it is a reasonable assumption to make that indices of bits fit into a machine word, and so all of these operations are $O(1)$.


What is the consensus algorithm that requires an odd number of nodes? Last week I stood up and gave a talk on the Raft Consensus Algorithm.

The first question I got was:

  Doesn't it need an odd number of nodes?

I answered "During leader election, the first node to become a candidate, all the other nodes have to vote for. (Provided for that node the lack of heartbeat, timeout conditions have been triggered, and for the client nodes the candidate has an update to date term log). If two candidates arise at the same time, and neither gets a majority, each will fall back to a different random timeout, and the first to become a candidate (provided all the other criterion are met) will win. So you don't need an odd number of nodes to reach a majority, you just need to be the first candidate. Split votes are handled."

Immediately after this answer - I got the same question from a different person all over again.

  So how does it reach consensus if it doesn't have an odd number of nodes?

My question is: What is the consensus algorithm that requires an odd number of nodes?

EDIT:

Here is an online publication that claims distributed systems need an odd number of nodes. (Spurious claim).

  Partition tolerant consensus algorithms use an odd number of nodes (e.g. 3, 5 or 7). With just two nodes, it is not possible to have a clear majority after a failure. For example, if the number of nodes is three, then the system is resilient to one node failure; with five nodes the system is resilient to two node failures.

To my knowledge there is no quorum-based consensus algorithm that requires an odd number of nodes (processes). That's because such algorithms don't require a majority in the sense that a higher number of processes accept a value. A majority in these algorithms means that at least $N / 2 + 1$ processes accept a value, where $N$ is the total number of processes.

The reason for this is that a quorum-based algorithm requires that every decision made is known by at least one member of each one of the possible quorums in the system. One simple way (but not the only one) to achieve this is to require that every quorum is composed by $N/2 + 1$ processes and that the vote is unanimous inside a quorum.

For example, in a system with two processes two votes are required and the system is not fault tolerant. For three processes two votes are required. For four, three votes. For five, three votes.


Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete) I need to prove that TAUT is coNP-complete. I showed that $\text{TAUT} \in \text{coNP}$ by reducing $\text{SAT}$ to $\overline{\text{TAUT}}$. However, I cannot figure out how to prove that every problem in coNP can be reduced to $\text{TAUT}$ in polynomial time. To do that, I would need one of two things:

A known coNP-complete problem for reduction or
a proof that a problem is coNP-complete if its complement is NP-complete.

Neither of these was given to us in lecture, so I cannot use anything without proving it myself. Did I miss anything which should have been obvious? Where should I start?

I take it that we call $TAUT$ the problem of given a DNF formula, decide if it is a tautology (if you do not want to restrict to DNF, this will still work as this only makes the problem more general).

The answer of your questions easily follows from the definition of $coNP$. Remember that a language $L \subseteq \{0,1\}^*$ is in $coNP$ is $\bar{L} = \{x \in \{0,1\}^* \mid x \notin L\} \in NP$. For example, $\overline{TAUT}$ is the set of DNF that are not a tautology. To prove that a DNF is not a tautology, you only have to find an assignment that does not satisfy your formula, which can be done in polynomial time with a NTM (just "bruteforce" the assignments). Hence, it is in $NP$. In other words, $\overline{TAUT} \in NP$ thus $TAUT \in coNP$.

Now take an $NP$-complete language $L$. By definition, $\bar{L} \in coNP$. We show that $\bar{L}$ is $coNP$-complete, that is, for every language $A \in coNP$, $A \leq \bar{L}$. Let $A \in coNP$. Then $\bar{A}$ is in $NP$. By $NP$-completeness of $L$, there exists a function $f$, computable in polynomial time such that $x \in \bar{A}$ iff $f(x) \in L$. This is equivalent to say that $x \notin \bar{A}$ iff $f(x) \notin L$. Which in turn, is equivalent to $x \in A$ iff $f(x) \in \bar{L}$. Thus, $f$ is also a reduction from $A$ to $\bar{L}$, meaning that $A \leq \bar{L}$. In other words, $\bar{L}$ is $coNP$-complete.

Now, if you want to show that $TAUT$ is $coNP$-complete, you only have to show that $\overline{TAUT}$ is $NP$-complete. And it is not hard to see that $SAT \leq \overline{TAUT}$. Indeed, a CNF $F$ is satisfiable iff $\neg F$, which is a DNF, is not a tautology.


Given a random number generator rand5() generate gen7() Given a pseudo random number generator rand5() that generates a random integer in the set [0,1,2,3,4], how would someone use this to generate a function rand7() that outputs [0,1,2,3,4,5,6] with equal probability.

I was thinking of approaching it this way: reduce the problem to generate number from 0 to 6 using a coin.

We can represent [0,1,2,3,4,5,6] using bit-wise from 000 to 111.
Selecting each bit from LSB to MSB can be done using tossing a coin.
However, if we continue in this fashion from LSB to MSB then we
can get all bits as 111 which is decimal 7. So, in the case of MSB
if we get 1 then discarding it and starting again should give
the result? Right?

Reducing the problem from rand5() to coin can be done in this way: if the number is 0,2 then we can consider it as head and getting 1,3 can be considered as tail.

Is my solution right?

(For some reason, this old question came up first)
rand5()+rand5()*5 would give numbers 0-24, each with a probability of 1/25.  You could use the first 21 of these to return 0-6 with equal probabililty.
Likewise, rand2()+rand2()*2+rand2*4) gives numbers 0-7, each with a probability of 1/8. You could use the first 7 of these to return 0-6 with equal probability.
In pseudocode:

function rand7a() {
  do { rand7 = rand5() + rand5()*5 } while (rand7 >= 21);
  return rand7 mod 7;
}
function rand7b() {
  do { rand7 = rand2() + rand2()*2 + rand2()*4 } while ( rand7 == 7);
  return rand7;
}

EDIT: Elaboration:
1st approach:
rand2() in binary is 000 or 001 with 50-50 probability.
rand2()*2 is         000 or 010 with 50-50 probability.
rand2()*4 is         000 or 100 with 50-50 probability.
So the sum is binary xxx where each x has a 50-50 probability of 0 or 1; so each 000 to 111 has a probablilty of 1/8.

2nd approach: going through each of the 8 possibilities of the 3 rand2()s:
0+0+0 or 1+0+0 or 0+2+0 or 1+2+0 or 0+0+4 or 1+0+4 or 0+2+4 or 1+2+4
all of these with equal probablilty 1/8.


How can I convert a for loop to a recursive function? My loop is pretty simple. The function takes in two parameters, a and b; both are integers where a<=b. The function will then create a list of numbers from a to b.

This is what I created:

 def cat(a,b):
     j = []
     for i in range (a,b):
     j.append(a+1)
     a +=1

I honestly cannot figure out how to turn this into a recursive function.. I have tried things which I realize don't make any sense and I'm not really sure where to start. Any help would really be appreciated :) Thanks

Here is a recursive version of this procedure, in python:

def cat(a,b):
  if a == b:
    return [a]
  else:
    return [a] + cat(a+1,b)

Another option is

def cat(a,b):
  if a == b:
    return [b]
  else:
    return cat(a,b-1) + [b]

These conversions are heavily geared toward this particular function. Here is a more general conversion, in the context of state machines without input (inputs can easily be added):

def run_my_algorithm(state = None):
  if state is None:
    state = initial_state
  if is_final_state(state):
    return extract_answer(state)
  else:
    state = next_state(state)
    return run_my_algorithm(state)

Hopefully the notation is self-explanatory.


Are all turing complete languages interchangeable Note, while I know how to program, I'm quite a beginner at CS theory.

According to this answer

  Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do.

And any program written in any Turing complete language can be rewritten in another.

Ok. This makes sense. I can translate (compile) C into Assembly (and I do it everyday!), and can translate Assembly into C (You can write a virtual machine in C). And the same applies to any other language - you can compile any language into Assembly, and then run it in a VM written in another other language.

But can any program written in a Turing complete language be re-written in another?

What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

Ok. So you'll say that since we're dealing with computer theory, we're not discussing physical device limitations.

But what about a device that doesn't have multiplication? division? To the best of my knowledge (though this is more of a question for math.SE), one can't emulate multiplication (and definitely not division) with addition and subtraction [1].

So how would a "turing complete language" (which can add, subtract, and jump) emulate another language which can add, subtract, multiply and jump?

EDIT

[1]. On arbitrary real numbers.

Turing-completeness says one thing and one thing only: a model of computation is Turing-complete, if any computation that can be modeled by a Turing Machine can also be modeled by that model.

So, what are the computations a Turing Machine can model? Well, first and foremost, Alan Turing and all of his colleagues were only ever interested in functions on natural numbers. So, the Turing Machine (and the λ-calculus, the SK combinator calculus, μ-recursive functions, …) only talk about the computability of functions on natural numbers. If you are not talking about a function on natural numbers, then the concept of Turing-completeness doesn't even make sense, it is simply not applicable.

Note, however, that we can encode lots of interesting things as natural numbers. We can encode strings as natural numbers, we can encode graphs as natural numbers, we can encode booleans as natural numbers. We can encode Turing Machines as natural numbers, which allows us to create Turing Machines that talk about Turing Machines!

And, of course, not all functions on natural numbers are computable. A Turing Machine can only compute some functions on natural numbers, the λ-calculus can only compute some functions on natural numbers, the SK combinator calculus can only compute some functions on natural numbers, …. Surprisingly (or not), it turns out that every model of computation (that is actually realizable in our physical universe) can compute the same functions on natural numbers (at least for all the models we have found up till now). [Note: obviously, there are weaker models of computation, but we have not yet found one that is stronger, except some that are obviously incompatible with our physical universe, such as models using real numbers or time travel.]

This fact, that after a long time of searching for lots of different models, we find, every single time, that they can compute exactly the same functions, is the basis for the Church-Turing-Thesis, which says (roughly) that all models of computation are equally powerful, and that all of them capture the "ideal" notion of what it means to be "computable". (There is also a second, more philosophical aspect of the CTT, namely that a human following an algorithm can also compute exactly the same functions a TM can compute and no more.)

However, none of this says anything about

how efficient the various models are
how convenient they are to use
what else they can do besides compute functions on the natural numbers

And that is precisely where the differences between different models of computation (and programming languages) come into play.

As an example of different performance, both a Random Access Machine and a Turing Machine can copy an array. But, a RAM needs $O(size_{array})$ operations to do that, while a TM needs $O(size_{array}^2)$ operations, since it needs to skip across $size_{array}$ elements of the array for copying each element, and there are $size_{array}$ elements to copy.

As an example for different convenience, you can just compare code written in a very high-level language, code written in assembly, and the description of a TM for solving the same problem.

And your light switch is an example of the third kind of difference, things that some models can do that are not functions on natural numbers and thus have nothing to do with Turing-completeness.

To answer your specific questions:

  But can any program written in a Turing complete language be re-written in another?

No. Only if the program computes a Turing-computable function on natural numbers. And even then, it might need a complex encoding. For example, λ-calculus doesn't even have natural numbers, they need to be encoded using functions (because functions is the only thing λ-calculus has).

This encoding of the input and output can be very complex, as can expressing the algorithm. So, while it is true that any program can be rewritten, the rewritten program may be much more complex, much larger, use much more memory, and be much slower.

  What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

A lightbulb is not a Turing-computable function on natural numbers. Really, a lightbulb is neither a function nor a computation. Switching a lightbulb on and off is an I/O side-effect. Turing Machines don't model I/O side-effects, and Turing-completess is not relevant to them.

  On arbitrary real numbers.

Turing-completeness only deals with computable functions on natural numbers, it doesn't concern itself with real numbers.

Turing-completeness is simply not very interesting when it comes to questions like yours for two reasons:

It is not a very high hurdle. All you need is IF, GOTO, WHILE, and a single integer variable (assuming the variable can hold arbitrarily large integers). Or, recursion. Lots and lots and lots of stuff is Turing-complete. The card game Magic: The Gathering is Turing-complete. CSS3 is Turing-complete. The sendmail configuration file is Turing-complete. The Intel x86 MMU is Turing-complete. The Intel x86 MOV instruction is Turing-complete. PowerPoint animations are Turing-complete. Excel (without scripting, only using formulas) is Turing-complete. The BGP routing protocol is Turing-complete. sed is Turing-complete. Apache mod_rewrite rules are Turing-complete. Google for "(accidentally OR surprisingly) turing complete" to find some other interesting examples. If almost everything is Turing-complete, being Turing-complete stops being an interesting property.
It is not actually necessary to be useful. Lots of useful stuff isn't Turing-complete. CSS before version 3 isn't Turing-complete (and the fact that CSS3 is isn't actually used by anyone). SQL before 1999 was not Turing-complete, yet, it was tremendously useful even then. The C programming language without additional libraries doesn't seem to be Turing-complete. Dependently-typed languages are, more or less by definition, not Turing-complete, yet, you can write operating systems, web servers, and games in them.

Edwin Brady, the author of Idris, uses the term "Tetris-complete" to talk about some of these aspects. Being Tetris-complete isn't rigorously defined (other than the obvious "can be used to implement Tetris"), but it encompasses stuff like being high-level enough and expressive enough that you can write a game without going insane, being able to interact with the outside world (input and output), being able to express side-effects, being able to write an event loop, being able to express reactive, asynchronous, and concurrent programming, being able to interact with the operating system, being able to interact with foreign libraries (in other words: being able to call and be called by C code) and so on. Those are much more interesting features of a general purpose programming language than Turing-completeness is.

You may find my answer to the question you linked interesting, which touches on some of the same points even though it answers a different question.


Constructing a DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$ with a kind of log-space TM Suppose that $A$ and $B$ are DFAs. We know that there is some DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$, the symmetric difference. Also, we can construct this $M$ by some Turing machine $N$. But can we ensure that $N$ has the following form?

$N$ consists of (i) a read-only input tape, (ii) a work tape that is log-space with respect to $|\langle A, B\rangle|$, and (iii) a one-way, write-only, polynomial-time output tape.

This really comes down to showing that this kind of TM can construct DFAs for $L(A) \cup L(B)$ and $L(A) \cap L(B)$. But it's not clear to me how this would work.

Any help is appreciated.

Don't construct machines for $L(A)\cap L(B)$ and $L(A)\cup L(B)$. Use a variant of the product construction for those two automata to directly construct an automaton for symmetric difference. Because of the way the product construction works, you don't need to store much intermediate data at all: essentially the algorithm is just a couple of for loops and, with at most $n$ states to loop through, you only need $\log n$ bits to hold the value of the loop counter.


Domain of a Type-2 Computable Function In Weihrauch's Type-2 computability theory, a string function $f\colon\subseteq \Sigma^{\omega}\rightarrow \Sigma^{\omega}$ (the $\colon\subseteq$ indicates that $f$ may be a partial function) is computable iff there exists a Type-2 Turing machine that exactly realizes $f$, which implies that the Turing machine must fail to produce an output on inputs that are not in the domain of $f$.

To extend this to functions between arbitrary domains $D_1$ and $D_2$, one specifies representations $\gamma_i\colon\subseteq\Sigma^{\omega}\rightarrow D_i$, and Weihrauch defines $f\colon\subseteq D_1\rightarrow D_2$ to be $(\gamma_1,\gamma_2)$-computable iff there exists a Type-2 computable string function $g$ such that $f(\gamma_1(y)) = \gamma_2(g(y))$ whenever $f(\gamma_1(y))$ is defined.

But $\gamma_2(g(y))$ is allowed to be defined even when $f(\gamma_1(y))$ is not.

Why is it defined this way? It seems to me more natural to require $f\circ\gamma_1 = \gamma_2\circ g$, i.e. the domain of the realization $g$ must match the domain of $f$. With Weihrauch's definition we have the odd condition that, for a string function $f$, the statements "$f$ is Type-2 computable" and "$f$ is $(\mathrm{id},\mathrm{id})$-computable" (where $\mathrm{id}$ is the identity function) are not equivalent.

Reference: Weihrauch, K. (2000), Computable Analysis: An Introduction, Springer.

Philosophical answer

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

Technical answer

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

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

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

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

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

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

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


Minimize function on permutations Problem:

Consider $[k] = \{ 1, 2, \dots, k \}$ and function (of two arguments) $f: [k]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in [k]^{2}$ (all ordered pairs of numbers from $[k]$). Also, we know that for all $n, m \in [k]$ $$f(n, m) = f(m, n) .$$

Also, consider the set $S_{k}$ of all permutations on $[k]$ and function $g: S_{k} \rightarrow \mathbb{N}$ defined as follows $$ \sigma = \sigma_{1} \sigma_{2} \dots \sigma_{k} \quad \Rightarrow \quad g(\sigma) = \sum_{i = 1}^{k - 1} f(\sigma_{i}, \sigma_{i + 1}) .$$

The problem is to find at least one permutation $\sigma \in S_{k}$ such that $g(\sigma)$ is minimal.

Question:

How can we find the desired permutation faster than brute force?

Hamiltonian path is a special case of your problem. Given a graph $G$, let $f(n,m) = 1$ if the edge $(n,m)$ exists, and $f(n,m) = 2$ otherwise. The minimum value of $g(\sigma)$ equals 1 iff $G$ contains a Hamiltonian path.


Min-Max number of shifts and reductions in bottom-up parser Given the Grammar has no unit or ɛ-productions,
What is minimum & maximum number of shifts and reduce needed by bottom-up parser?

The number of shifts is always precisely the number of symbols in the input stream, since every symbol is shifted exactly once. The number of reductions depends on the grammar; it is impossible to answer that question without knowing something about the grammar.

For example, if the grammar were in Chomsky Normal Form, you could easily count the number of reductions because for CNF grammars, the concrete syntax tree must be a complete binary tree and each node in the tree corresponds to a single reduction.


Range intersection with bounding box? I have a lexicographical order on integer $n$-tuples, where $(x,y,\dots) > (a,b,\dots)$ if $x>a$ or if $x=a$ and $y>b$, and so on to the end of the tuple (I called it lexicographic because of its similarity to the natural order on strings of $n$ characters). In this order I have a range, defined inclusively by a pair of tuples.

I also have a rectangular box in $n$ dimensions defined by a pair of integer $n$-tuple corners. A tuple is in the box if every one of its elements is greater than the corresponding element in the first corner, and also less than the corresponding element in the second corner.

Given two tuples to serve as the ends of the range (under the lexicographic ordering), and another two tuples defining the corners of the box, I would like to determine if there is any overlap between the tuples in the range and the tuples in the box. What is the most elegant way to do this?

I think you can answer this in $O(n)$ time with a recursive algorithm, as follows.  It basically boils down to an ugly case analysis.

Over the real numbers

Let me start by assuming you are working over the real numbers, to make it easier to present the ideas.

Suppose the range is $(r_1,r_2,\dots,r_n) \ldots (s_1,s_2,\dots,s_n)$ and the bounding box has corners $(b_1,\dots,b_n)$ and $(c_1,\dots,c_n)$ with $b_i \le c_i$ for all $i$.  There are four cases:

If the intervals $[r_1,s_1]$ and $[b_1,c_1]$ don't overlap, then there is no overlap between your range and your bounding box.
If $r_1=s_1$ or $r_1=c_1$, then check whether $b_1 \le r_1 \le c_1$ and then recurse on the $n-1$-dimensional problem obtained by forcing the first dimension to be $r_1$ (i.e., the range is $(r_2,\dots,r_n) \ldots (\infty,\dots,\infty)$ and the box has corners $(b_2,\dots,b_n)$ and $(c_2,\dots,c_n)$).
If $r_1<s_1$ and $s_1=b_1$, then recurse on the $n-1$-dimensional problem obtained by forcing the first dimension to be $s_1$  (i.e., the range is $(-\infty,\dots,-\infty) \ldots (s_2,\dots,s_n)$ and the box has corners $(b_2,\dots,b_n)$ and $(c_2,\dots,c_n)$).
Otherwise, the intervals $[r_1,s_1]$ and $[b_1,c_1]$ overlap at more than two points.  In this case, there is guaranteed to be an overlap between your range and your bounding box.  In particular, pick a value $x_1$ that is in the overlap and such that $r_1<x_1<s_1$; then $(x_1,b_2,\dots,b_n)$ is in the range and in the bounding box.

It is easy to see that this runs in $O(n)$ time, because the running time satisfies the recurrence $T(n) = T(n-1) + O(1)$.

Over the integers

If you are dealing with integers, then it suffices to add the following cases just before the "Otherwise":

If $s_1=r_1+1$, recurse twice: recurse on the range $(r_1,r_n,\dots,r_n)\ldots (r_1,\infty,\dots,\infty)$ and recurse again on the range $(s,-\infty,\dots,-\infty) \ldots (s_1,s_2,\dots,s_n)$ (leaving the bounding box alone).  If either of them finds a point of overlap, then you have found an overlap between your range and your bounding box.  (*)
If $c_1=b_1+1$, then there is a point of overlap.  (If $r_1<b_1<c_1\le s_1$, use $(b_1,\dots,b_n)$); if $r_1 \le b_1<c_1 < s_1$, use $(c_1,\dots,c_n)$); those are the only two possibilities.)

The running time with this modification remains $O(n)$.  It takes a little more work to see why, though.  Naively, we obtain the recurrence $T(n)=2 T(n-1) + O(1)$, due to need to recurse twice in the case marked (*); and this recurrence satisfies $T(n)=O(2^n)$, which is very bad.  Fortunately, this is an overly loose upper bound.  Note that when $(r_1,\dots,r_n) = (-\infty,\dots,-\infty)$ or $(s_1,\dots,s_n)=(\infty,\dots,\infty)$, then we never invoke the case (*) in any subsequent recursion.  So, when running on one of those inputs, the running time is $O(n)$.  Moreover, the case (*) recurses on inputs of this form.  Thus, we will never invoke case (*) more than once in the entire recursion tree.  Thus, the entire recursion tree can involve at most $2n$ recursive calls.  Thus, the total running time remains $O(n)$.

This algorithm looks a pretty messy, with at least 6 different cases.  Perhaps there is a cleaner way to do it.


To find median of k sorted arrays of n elements each in less than O(n*k*log(k)) How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient solution..Like for 2 arrays it can be done in O(log(n)) time..I am trying to use the same logic here but couldn't apply..

Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$.
Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define
$$
N = \sum_{i=1}^k \lceil |A_i|/2 \rceil.
$$
There are at least $N$ many elements in $\mathbf{A}$ whose value is at least $m_r$, and at least $N$ many elements in $\mathbf{A}$ whose value is at most $m_s$.
If $N \geq t$ then elements larger than $m_s$ cannot be the $t$'th smallest element. In particular, we can throw out the upper half of $A_s$. Similarly, if $N \geq n+1-t$ then elements smaller than $m_r$ cannot be the $t$'th smallest element, and so we can throw out the lower half of $A_r$ (and update $t$ accordingly, by subtracting $\lfloor |A_r|/2 \rfloor$). Note that $\min(t,n+1-t) \leq \lceil n/2 \rceil \leq N$, and so at least one of these cases must happen.
How many rounds does it take this algorithm to complete? Each round results in reducing the size of one of the $k$ arrays roughly by half (the reduction is $\ell \mapsto \lceil \ell/2 \rceil$). One can check that it takes $\lceil \log \ell \rceil$ steps to reduce each array to a singleton. Therefore the number of rounds it takes the algorithm to narrow down all arrays to a single element is
$$
\sum_{i=1}^k \lceil \log |A_i| \rceil \leq k + \sum_{i=1}^k \log |A_i| \leq k + k \log \sqrt[k]{|A_1| \cdots |A_k|} \leq k + k \log \frac{|\mathbf{A}|}{k}.
$$
After an initial round which takes $O(k\log k)$ time, each subsequent round can be implemented in $O(\log k)$, if we store the medians in an appropriate data structure such as a heap. Following this phase, we are left with $k$ elements, and we can run a linear time selection algorithm to find the $t$'th smallest element in $O(k)$. In total, this algorithm runs in time
$$
O\bigl(k\log k + k \log \tfrac{|\mathbf{A}|}{k}\bigr) = O(k\log |\mathbf{A}|).
$$
When $|A_i|=n$ for all $i$, this is $O(k\log (kn))$.


Bin-packing satisfiability rather than minimization Here's a problem I need to solve that's clearly related to the standard bin-packing problem, but I'm not sure how to approach it.

Suppose you have some finite set of bins $B$, and each $b_i \in B$ has some integer capacity $\mathit{cap}(b_i)$. You also have some set of items $L$ where each item $l_j \in L$ has some integer volume $vol(l_j)$. The question is, is there some way of assigning each item in $L$ to some bin in $B$ where no bin is overful, i.e. to find any total mapping $M : L \rightarrow B$ such that $\forall b_i \in B$, the sum of all $vol(l_j)$ with $M(l_j) = b_i$ is less than $cap(b_i)$.

The notable differences from the classic bin-packing problem are: first, we have only a finite set of bins, not an infinite number of bins to draw from. Second, we have no notion of cost; we only want to find some total mapping or determine that no such mapping exists. Third, bins are not homogeneous; we might have one bin with capacity 5 and another with capacity 10.

I'm not sure how to approach this problem or whether standard bin-packing approaches can be adapted to work with it. What is a good algorithm for answering the question?

For extra credit, there are a few extra bells and whistles that I would like to add, though these are optional:

Add a constraint that some bins can only contain a maximum number of items as well as having a volume limit
Some bins may have a minimum per item volume as well as a maximum volume; i.e. you don't have to put an item in the bin, but if you that item must have at least a given volume

Having a fixed number of bins makes little difference. If you use sorted-first-fit for example, the only difference is that the algorithm can fail. On the other hand, if you use a better algorithm for bin-packing (one that considers all bins before it is proven that they are all needed), you would find a trivial lower bound l for the number of bins, try to fit them all, and if it fails increase l by 1 and start all over again.

The different sizes make the problem likely harder to solve. For example, if you only wanted to decide which bin contains the largest item, that would in normal bin packing be no problem: Just put it into the first bin; it doesn't matter which one. With different bin sizes, pick all the bins that are big enough, remove duplicates with the same size, and try putting it into each of these bins. So you have more possible combinations. (If you had 100 bins of size 10 and 100 bins of size 5, then items of size 6 would be no problem, but a largest item of size 5 or smaller would be put into one of two bins).

I say "likely harder" because in the extreme you might have items that fit into one bin only.

Once you try to find an optimal solution using brute force, any additional restrictions make it easier because they remove possibilities from the search tree.


Calculating the end-to-end delay of a message sent over a network This is a problem from a MOOC on computer networking:

  We wish to send a message of size $150,000$ bytes over the network. There are four hops, each of length $20$ km and running at $100$ Mb/s. However, before sending we split the message into $1500$ byte packets. What is the end-to-end delay of the message? Use speed of light in copper $c = 2 * 10^8$ m/s, and round your answer to the nearest integer millisecond.
  HINT: Break the problem into two parts: the end-to-end delay of one packet and the delay of the rest of the message across the slowest link.

After struggling for a bit, I obtained the answer by following the hint as follows:

$$
4\left(\frac{1500 \ B * 8 \ (b/B)}{100 \ Mb/s} + \frac{20 \ km}{2 * 10^8 \ m/s}\right) +
\left(\frac{150000}{1500} - 1\right)\left(\frac{1500 \ B * 8 \ (b/B)}{100 \ Mb/s}\right) = 12.76 \ ms
$$
The answer is correct but I don't understand why the packetization delay only was considered for the rest of the message. Why wasn't the propagation delay also considered for the remaining packets?

In this case the propagation delay is more than the transmission delay, the propagation delay acts as a bottleneck for the whole network therefore the total time depend on it.

Consider a pizza shop, it takes 10 min to prepare pizza but 5 min to transport it, having infinite labour to transport, calculate how much time will it take to finsh job for 100 pizza.

Your ans might be correct but equation is wrong, you should draw the transmission diagram for better understanding.


A variant of the busy beaver function Reading this question "Natural RE undecidable problems but not Turing-complete" the following language came to my mind:

If $\Sigma(\cdot)$ is the busy beaver function (maximum attainable score among all halting 2-symbol n-state Turing machines of the above-described type, when started on a blank tape), define the function:

$$BB(\langle M \rangle) =
\begin{cases}
1 & \text{$\langle M \rangle$ computes $\Sigma(\cdot)$}\\
0 & \text{ otherwise}
\end{cases}$$

Now define the language:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

  Is $L$ recursively enumerable? (it should be r.e.: just simulate in parallel M with all TMs of the same length, and if $M$ halts and another $M'$ halts with a higher score add M to the enumeration).

  Can we reduce the halting problem to $L$ ? (it seems that it cannot "capture" the halting of the busy beavers)

I can't believe I didn't see this before — but yes, with an oracle for $L$ you can solve the halting problem.  Obviously an oracle for $L$ gives us 'recursively' all non-Busy Beaver halting machines, so the question is 'can we figure out recursively in $L$ what the busy beavers are?'.  Define $\Sigma_2(n)$ as the count function of the 'second busiest beaver'; that is, the second-highest attainable score among all halting two-symbol $n$-state TMs.  The trick here is that there's a recursive function $f()$ such that $\Sigma(n)\leq\Sigma_2(f(n))$ (it's almost certain that $f(n)=n+1$ will do the trick, in fact, but that requires knowing that the BB function is strictly increasing) : given a machine $M$ of size $n$ that prints $\Sigma(M)$ 1s on its tape and then halts, there's some $c\gt 1$ and two machines each of size $\leq cn$ that print exactly $\Sigma(M)$ 1s and exactly $\Sigma(M)+1$ 1s, respectively, on their tapes — and this holds true for a 'busy beaver' machine $M$ even though we don't know $M$ explicitly.  This means that having a bound on the 'second busy beaver' function for $f(n)$ gives a bound for the busy beaver function on $n$; but then having this, it's easy to solve the halting problem for a TM $M$ of size $n$ - if $\langle M\rangle\in L$ then say that $M$ halts; otherwise, find the longest-running machine of size $f(n)$ in $L$ (which can be done recursively since there are only finitely many machines of size $\leq f(n)$) and simulate $M$ for as many steps as that machine takes to halt.  If $M$ doesn't halt within that time then $M$ can't possibly halt.


Can there be a language not Context free but still PDA acceptable? Let the input alphabet be $Σ = \{1,x,=\}$
Let the stack alphabet be $\tau = \{1,\$\}$ where $\$$ is the initial stack symbol.

Let,$q_0$ be the initial state of the PDA,$q_f$ be the final state of PDA,
I can define a transition function for PDA like this.

$(q_0,1,\$)\rightarrow(\$1,q_1)$
$(q_1,1,1)\rightarrow(1,q_1)$
$(q_1,x,1)\rightarrow(1,q_2)$
$(q_2,1,1)\rightarrow(1,q_2)$
$(q_2,=,1)\rightarrow(1,q_3)$
$(q_3,1,1)\rightarrow(\epsilon,q_3)$
$(q_3,\epsilon,\$)\rightarrow(\$,q_f)$

Now the PDA can recognize language $L = \{1^m x 1^n = 1^{mn}\}$
But According to https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/18/Small18.pdf Slide 24 this language is not Context Free.

Assume that I am quite beginner in TOC.

It is proven in your nearby language theory textbook (like Hopcroft, Motwani, Ullman "Introduction to automata theory, languages, and computation" (3rd edition, Pearson) that the languages accepted by (nondeterministic) PDAs are exactly the context free languages (generated by context free grammars).


What is the time complexity of this nested loop code? In this loop $j$ is dependent on $i$, and $j$ is executing like $n/2$, $n/2-1$, $n/2-2$, ... So does this sum up to $O(n\log n)$?

We just have one comparison when  $n$ is odd. So, the total complexity is (if we suppose $n$ is even, w.l.o.g.):

$$T(n) = \frac{n}{2} + (n + (n-2) + (n-4) + ... + 2) $$
$$= \frac{n}{2} + 2 \sum_{i=1}^{\frac{n}{2}}i = \frac{n}{2} + 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \Theta(n^2)$$


Do we know if there is an oracle $B$ so that $P^B \neq NP^B$ but $coNP^B=NP^B$? We know there is $B$ with $P^B \neq NP^B$, and we know there is $C$ with $coNP^C=NP^C$, what happens if we want to mix?

Any oracle relative to which $\mathsf{NP=EXP}$ would do the trick. You can find a construction of such an oracle in Heller's paper. Clearly if $\mathsf{NP=EXP}$ then $\mathsf{NP=coNP=EXP}$ but $\mathsf{P\neq NP}$ by the time hierarchy theorem.

I don't know whether there are known oracle constructions who collapse the hierarchy to $\Sigma_i$ and not to $\Sigma_{i-1}$, but it's an interesting question (I would guess the answer is in the affirmative).


Basic Question in networking - why max data size of ip datagram 65535 BYTES and not 65535 bits? I recently started computer networks with some understanding of algorithms and discrete mathematics. I am completely new. Kindly elaborate following -

data size of ip datagram = 16bits. So with this $2^{16} -1 = 65536$ 16 bit patterns can be generated.
My doubt:

Do we say each 16 bit pattern is 1 IP datagram or all those 65536 patterns as 1 IP Datagram?
If i consider all 65536 patterns as max data size, then max ip datagram size $= 65536$ patterns size$ = 65536*16 $ bits $= 65536*16/8$  bytes $= 65536*2$ bytes

16 bits is not the size of the IP datagram; it is the amount of bits required to encode its length. Hence, you can have datagrams of length up to 65536 octets (i.e., bytes), as described in RFC 760:

  Total Length:  16 bits

  Total Length is the length of the datagram, measured in octets,
      including internet header and data.  This field allows the length of
      a datagram to be up to 65,535 octets.

Notice 65536 is not a prescribed length, that is, the length of the datagram is (or can be) variable.

Now, to answer your two questions:

  Do we say each 16 bit pattern is 1 IP datagram or all those 65536 patterns as 1 IP Datagram?

Each octet pattern of up to 16-bit length is a datagram. In informal parlance, a datagram is simply a packet which IP adds its header to. You could call the set of all possible patterns a "datagram space", though I doubt that's standard terminology. (You might care to ask that in a separate question.)

  If i consider all 65536 patterns as max data size, then max ip datagram size =65536 patterns size=65536∗16 bits =65536∗16/8 bytes =65536∗2 bytes

I'm not sure I see a question here. Though I suppose any one you had is answered by my remark about the datagram length above.


How to prove that for a full binary tree $T$ there's a series of frequencies such that Huffman alg. will produce $T$? How to prove that for a full (each node that's not a leaf has 2 nodes) binary tree $T$ of $n$ leaves there's a series of frequencies $f_1,f_2,...,f_n$ such that if we use Huffman algorithm on the series we'll get $T$?

First in order to get frequencies from $T$ we can assign the probability of $\frac{1}{2^d}$ to each node where $d$ is the depth of a given node. The root node will have the probability of $1$ which means $100$%. After one traversal of $T$ we could fill the array with the frequencies of the leaves of $T$ (only leaves correspond to the the actual values to be encoded).

I'm not sure how to prove that if we apply Huffman algorithm to the frequencies one of the trees will happen to be $T$. It seems like if we build a tree from the frequencies each time such that the new tree is different (if possible) from the previous tree we'll eventually build $T$. Also we know that Huffman tree is always a full tree.

The Huffman algorithm is as follows (as described in Algorithm Design by Jon Kleinberg, Eva Tardos):

Huffman(S) {
  if |S|=2 {
    return tree with root and 2 leaves
  } else {
    let y and z be lowest-frequency letters in S
    S’ = S
    remove y and z from S’
    insert new letter ω in S’ with f_ω=f_y+f_z
    T’ = Huffman(S’)
    T=add two children y and z to leaf ω from T’
    return T
  }
}

The proof is by induction. The case $n = 1$ is clear. For $n > 1$, choose two leaves at maximal depths, and merge them. Huffman's algorithm could have chosen these two leaves at the first step and merged them. Now apply the inductive hypothesis to complete the proof.

Note that Huffman's algorithm, as described in your textbook, is non-deterministic in the sense that at any step there could be many valid choices. Any actual implementation of the algorithm will use a tie-breaking rule to arbitrarily choose which two leaves of minimal probability to merge at any given step.


Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points? So in this math exchange question I asked, it was proven that for $n>2$ dimensions, you can always find a curve that separates $k$ points in $n$-dimensional space into $2$ arbitrary sets that you pre-defined. What I wanted to know is if there is a polytime algorithm (polynomial in $k$) for determining this curve.

If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?

What I wanted to know is if there is a polytime algorithm (on the order of k) for determining this curve. If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?

Yes, this is possible. The equation for the curve will be nonlinear. (It is not possible to have a linear equation which describes the curve, because there exists sets of $k$ points (as long as $k \ge 4$) where no linear separator exists.)

Let the $k$ points in $n \ge 3$ dimensions be $\vec{x}_1, \vec{x}_2, \ldots, \vec{x}_k \in \mathbb{R}^n$.
For each point $\vec{x}_i$, suppose the set it is in is given by a label $\ell_i$, which is either $+1$ or $-1$. So the points are divided into those labeled $+1$ and those labeled $-1$.

Then we define the following function:
\begin{align*}
f: \mathbb{R}^n &\to \mathbb{R} \\
f(\vec{x}) &:= \sum_{i=1}^k \ell_i \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_i\| \right),
\end{align*}
where $d_{min}$ is the minimum distance between a pair of points, over all pairs of $2$ out of the $k$ points. That is, we take the minimum over $\|\vec{x}_1 - \vec{x}_2\|$, $\|\vec{x}_1 - \vec{x}_3\|$, etc. I am using $\| \cdot \|$ to denote the norm, that is, the length of vectors in $\mathbb{R}^n$.

Now I claim that your desired curve is given by the set
$$
\big\{ x \;\mid\; f(\vec{x}) = 0 \big\}.
$$

To justify this, we should show that $f$ separates the points labeled $+1$ from those labeled $-1$. So we first calculate $f(\vec{x}_i)$. We get
\begin{align*}
f(\vec{x}_i) =
\underbrace{\ell_i \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_i\| \right)}_{= \ell_i \cdot e^0 = \ell_i}
+
\underbrace{\sum_{j \ne i} \ell_j \cdot \exp \left(- \frac{\log k}{d_{min}} \|\vec{x} - \vec{x}_j\| \right)}_{\text{small}}
\end{align*}
Now the first term is just $\ell_i$, which is $1$ or $-1$, and the second term is small enough that it doesn't change the sign. Specifically,
we can bound the second term (in absolute value) by
$$
(k-1) \exp \left( -\frac{\log k}{d_{min}} \cdot d_{min}\right)
= (k-1) \cdot \frac{1}{k} < 1.
$$

So $f$ is positive on points labeled $+1$ and negative on points labeled $-1$. Also, $f$ is continuous on the entire $\mathbb{R}^n$. So, the points $\vec{x}$ where $f(\vec{x}) = 0$ must be a separating boundary curve between the positively and the negatively labeled points. $\square$

Finally, some notes:

Definition of a curve: In the question, it is not defined what a curve is, here; I took it to be the zero set of a continuous function, but you might want something more specific. This curve is actually a $(k-1)$-dimensional surface, but it might not be smooth at the points $\vec{x}_i$. A modification could be made that would smooth out these points by replacing $\|\vec{x} - \vec{x}_i\|$ with $\|\vec{x} - \vec{x}_i\|^2$ and $d_{min}$ with $d_{min}^2$.
Polynomial time: Returning the function $f$ is polynomial time: the only hard part is to compute the quantity $d_{min}$, which requires computing the distance between every pair of points in the set. So this is $O(k^2)$ time. The rest is just $O(k)$ time. Note that this requires that we have a model of computation in mind where arithmetic can be done on real-number values (it won't be a traditional Turing machine).


Why does Kadane's algorithm solve the maximum sub-array problem? I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms".

it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], A[i+1] , ... , A[j] in given array A[1] , ... , A[n].

The exercise is about developing linear-time algorithm to solve this using a following idea, (f.y.i. A[1 ,... , j] means A[1] , A[2] , ... , A[j] )

  Knowing a maximum sub-array of A[1, ... , j], extend the answer to find a maximum sub-array ending at index j+1 by using the following observation: a maximum sub-array of A[1, ... , j+1] is either a maximum sub-array of A[1,...,j]        or a sub-array A[i,...,j+1], for some 1 <= i <= j+1. Determine a maximum sub-    array of the form A[i,...,j+1] in constant time based on knowing a maximum sub-           array ending at index j." .

People said that this solution is actually Kadane's algorithm, which is relatively a simple algorithm stated on Wikipedia
(I'm really sorry that you have to move to another site. but it explains better than I do.)

However, Kadane's Algorithm deals with only a sub-array that ends at exactly j.
but above idea says I should use maximum sub-array of A[1, ... , j] and we can't guaranteed that this sub-array should end with j. Because I think this two algorithm is quite different.

Suppose $A[1..N]$ is your array for which you want to find maximum sum sub-array. Construct $B[1..N]$ such that $B[j]=max (\sum A[k] \mid k \le j,k \ge i)$ ($i$ is some starting index for which B[j] is maximum). So it boils down to $B[j]=max(B[j-1]+A[j],A[j])$ (here I am assuming that empty sub-array isn't allowed in answer). And then find the maximum $B[j]$ for all $j \in [1..N]$. Now this can be done in constant space since we only need result of the previous iteration( for $j$ we need only $B[j-1]$) and the maximum sub-array sum which has occurred till now. Now compare these two ideas and you will get you answer.


Help wrapping my head around a combinatorial optimization problem Here's the problem I'm trying to solve:

I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight requirement, while maximizing the total number of groups I can form.

Knowing a specific name for this class of problem would be a good start. Help formalizing it would be even better. I did this stuff so long ago in school, I need my memory jogged good and hard. Thanks!

Here is a complete MIP (Mixed Integer Programming) model that should do the trick. I just use some random data (weights) with 100 widgets and 50 possible bins. When solved the variable NumUsedBins gives the maximum number of bins and the variable x gives the assignment. The equation 'order' is to make sure we use lower numbered bins first. The strange statement about optcr is to tell the solver to solve to optimality (for very difficult problems you may want to stop at 5% or so).

With 1000 widgets this becomes somewhat difficult to solve to optimality.


NP hard relation with NP complete If any problem P is NP complete then if there is a polynomial time reduction of P to another problem R then what can we say about R.Is it NP-hard or NP complete ?
From Theory of computation of Hopcroft,Ullman theorem 10.4 it says it would be NP complete but there some times when i see that it is NP-Hard in some other reference . is there any condition when it is NP Hard or NP Complete .Or i misunderstood the theorem .

NP-hard means that all the problems in NP reduces to this.  NP-complete means that it is in NP as well.

Sometimes we say a problem is NP-hard when it is obviously NP-complete.  But this is because we want to stress the hardness of the problem, and also that it should be trivial that the problem is in NP.


Print (not count) all possible path classic climbing stair problem) I came across this classic question and found may many solution to it. for loop and DP/ reclusive + memorization.

Also found a twisted version of the questions asking to print all possible path instead of counting.  Wondering for the twisted version, if we have DP solution ?
Q: If there are n stairs, you can either take 1 or 2 steps at a time,  how may way can you finish the stairs. we can just using fib to calculate it.
What if you are ask print out all possible ways(not revision please). For example, if n = 5. we have  as solution.  pseudo code is welcome.

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 1, 1]
[1, 2, 2]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]

Here is pseudocode for solving this, using a recursive procedure:
All-Solutions($n$):
If $n=0$, return the solution (empty sequence).
If $n=1$, return the solution $1$.
Otherwise:

Run All-Solutions($n-1$), and prefix $1$ to all results.

Run All-Solutions($n-2$), and prefix $2$ to all results.

There is also a simple iterative solution. Start with the solution composed of $n$ many $1$s, and iteratively try to increase it, until getting stuck. How to increase a solution?

If a solution ends with $1,1$, replace this with $2$.
If a solution ends with $2,1$, consider the suffix of the form $1,2,\ldots,2,1$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell$ many $1$s.
If a solution ends with $2$, consider the suffix of the form $1,2,\ldots,2$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell-1$ many $1$s.

Here is an example, $n=5$:
\begin{align}
&1,1,1,1,1 \\
&1,1,1,2 \\
&1,1,2,1 \\
&1,2,1,1 \\
&1,2,2 \\
&2,1,1,1 \\
&2,1,2 \\
&2,2,1
\end{align}
Both solutions output the list in lexicographic order. The iterative one has $O(1)$ amortized update time. Indeed, the length of the list is $F_{n+1}$, and the total length of suffixes is $F_{n+3}-2$, and so the average length of a suffix is roughly $\phi^2 = \phi + 1 \approx 2.618$.