Omission of smaller variables in Big-O Complexity I have an algorithm that:

1. takes in a book's text as a string.

2. splits that string into words and stores it in a list.

3. creates a hash table from this list by iterating over the elements of the list

4. It then iterates over a separate list of words to see if each of these words (in this separate list) is contained in the hashmap.

Three linear traversals occur here. One to split the input string into a word list, one linear traversal of the word list to create the hash table and one final traversal over the separate list to check each word is in the newly created hash table.

Time complexity is O(n + k + m), where n is the number of characters in the input string, k is the number of words and m is the number of words in the other list.

My question is, since k is derived from n and we can guarantee that k will always <= n can we omit n and write the complexity as O(n+m)?

Yes, you can.  Since $k \le n$, you have $n+k+m \le 2n+m = O(n+m)$.


What does it mean " The outer level page table need not be page aligned? The question is in context to multilevel page table. I was trying to solve numerical on multi-level paging and noticed that page size might not be same at all levels. I came across the point "Outer level page tables need not be page aligned to inner page tables".

Question 1: Does this mean that outer level page tables need not have same page size as inner page tables?

Question 2: If the sizes at different levels of paging are different, then will an outer page table's entry have to contain the exact frame address, i.e., frame number + offset, because page sizes are different across all levels?

Having different subtable sizes for different levels of a multilevel page table just means that a different number of bits from the virtual address will be used. The size of each level's subtable is independent of the sizes of subtables in other levels. (Yes, "outer level page tables need not have same page size as inner page table".)

Each subtable would be aligned to its size and pointers to that table in earlier levels could exploit this to elide zero bits in the address. The index would still be provided by the selection of virtual address bits. (No, outer page tables entry will not have to contain frame number + offset.)

For example, with a 47-bit virtual address space with a 50-bit physical address space (8-byte PTEs), an 8 KiB subtable with entries pointing to a 16 KiB subtable whose entries point to a 64 KiB subtable that points to 8 KiB pages:

root 8KiB subtable entry physical address
   PA[49:13] = root_pointer[39:0]
   PA[12:03] = VA[46:37] // 8 KiB subtable index
   PA[02:00] = 000       // PTE is 8-byte aligned
16 KiB subtable entry physical address
   PA[49:14] = pointer_to_16KiB_subtable[38:0]
   PA[13:03] = VA[36:26] // 16 KiB subtable index
   PA[02:00] = 000
64 KiB subtable entry physical address
   PA[49:16] = pointer_to_64KiB_subtable[36:0]
   PA[15:03] = VA[25:13] // 64 KiB subtable index
   PA[02:00] = 000
page address
   PA[49:13] = PTE_in_64KiB_subtable[36:0]
   PA[12:00] = 0_0000_0000_0000  // 8 KiB aligned page

The above example assumes a fixed size associated with each level. With variable sizes, the size of the targeted subtable would have to be included with its pointer.

The subtable size could be determined by a subtable size number such that three bits would support eight different subtable sizes or using a single extra bit with the size boundary marked by the first set bit starting from the least significant bit (e.g., aa...aa_1000 would indicate a subtable eight times larger (three bits before the set bit) than the smallest size supported). The former allows additional alignment bits of larger subtables to be used to extend the physical address space or provide more metadata; the latter saves bits (two in the example) that can be used for metadata or larger physical addresses even for the smallest subtables. Supported subtable sizes could also be dependent on the level of the subtable or even the sizes (or other metadata provided) in previous levels, though that seems inappropriately complex.


How is a program executed at the CPU level? I know this is a very common question. But I have a different angle in my mind. I will just try to articulate it here.

From what I know, every instruction that a CPU executes, is in machine language and all CPU can do is do some arithmetic operations thanks to ALU and to its transistors (if we go at hardware level).

However this is easier to type than to comprehend it. So if all CPU does is adding, subtracting, etc., then how is a program, say a JAVA program saying print Hello World, executed with these arithmetic operations?

I mean how is this program converted into something that is just an addition for the CPU?

P.S. If this question is not applicable for this website then I apologise.

-----Part TWO-----

Okay. Thanks to all for answering this fast and with this enthusiasm. I thought its better to modify my question a bit than to go and comment to all answers and ask them again.

So here it is.

First, all have answered specifically w.r.t example of Hello World. This is my fault. I should have kept this generic. Hello world example brings in question of output devices and how its processing is not just limited to the CPU, which is rightfully brought up in your answers.

Also  many of you brought to my notice that CPU does more than just addition. I agree with that. I just didn't write that and assumed it all the way.
From what I understand, this is the process:

read the instruction from memory (using data and address buses and program counter stuff)

store data in register inside CPU
Now ALU does arithmetic operations, of course after decoding the instruction, or take a jump if its an if like instruction
And then communicating with other resources if needed like with output device and so on. Processes beyond this are trivial for now.

So in step3 where CPU decodes an instruction and decides to do an arithmetic operation(here we are assuming that there is no other operation to be done like jump the current instruction..since arithmetic operations are mostly done..so we will stick to that)  This is where my visualization ends. How an instruction from my program is just an arithmetic operation for CPU. It does that arithmetic operation and that instruction serves its purpose.

I hope I made myself clear this time.

P.S. I am taking a big assumption here that ALU is just not restricted to actual arithmetic operation we do in our programs, rather it executes all instructions ,which are now in binary form, by adding or subtracting e.t.c them to yield result that they are meant to yield.
If I am wrong here than answers below correctly answer my question.

You can try taking a simple program and compiling it to native machine code.  (Java normally compiles to JVM code, but Andrew Tennenbaum has a book where he describes how to design a CPU that runs that natively, so it will do.)  On GCC, for example, you give the compiler the -S switch.

This will tell you that anything tricky, like I/O, is implemented by calling the operating system.  While you could download the source to the Linux kernel and do the same to it, what's going on under the hood is: everything is manipulating the state of the computer's memory, for example the list of running processes, or else talking to hardware by using special memory addresses that control it or using special CPU instructions like in and out on the x86.  Generally, though, only special programs called device drivers will talk to particular hardware, and the OS will send requests to use hardware to the right driver.

Specifically, if you print, "hello, world!" your compiler will turn that into a set of instructions that loads the string into a particular location (for example, loading the address of the string in memory to the %rdi register) and calling a library function with the call instruction.  This library function might find the length of the string with a loop, then call the system call write() to write that number of bytes from the string to file descriptor number 1, which is standard output.  At that point, the OS looks up what that process' file number 1 is and decide what writing to it means.  If writes to standard output get printed on your screen, there will be some process like copying the bytes to a buffer, which is then read by your terminal program, which tells the windowing system which letters to put where in what font.  The windowing system decides exactly what that should look like, and tells a device driver to put the pixels on the screen, which it does by changing video memory.


Does Second chance Page replacement algorithm suffer with Belady's anomaly? In Second chance Page replacement algorithm(clock algorithm), if all the Reference bits are set to one, then the algorithm behaves just as FIFO.

Considering this case, can we conclude that Second chance algorithm also suffers from Belady's anomaly?

This is not true.  This is only a special case in once instance of 2nd chance algorithm.  All reference bits set to one does not persist for each page that tested for a page replacement.  Since LRU does not suffer from Belady's anomaly, and since 2nd chance is an approximation to LRU, then it follows that 2nd chance does not suffer from Belady's anomaly.


Identifying and describing the language accepted by a Turing machine Given a Turing machine, how can I identify the language it accepts and write a set notation for L(M)?

A Turing machine implements an algorithm.
The algorithm can be implicit by an explicit definition of the language such as:
$M$ is a TM such that $L(M)=\left \{ x\in \Sigma^* \ | \ |x|\in \mathbb{N}_{even}\right \}$. Which is usually the case.
In other cases, you might have to understand a turing machine based on a state diagram, this will be a simple reverse engineering problem where based on some inputs you understand the algorithm (and then you can prove your assumption).
Generally, there is no fixed approach towards understanding the language a machine accepts.


Are there NP COMPLETE problems that are "easy" in practice? NP COMPLETE problems are hard in the worst case (assuming $P \neq NP$). What that means is that for every polynomial $p$, sufficiently large integer $n$, and algorithm $A$, there is an instance $x$ of size $n$ for which the algorithm takes more than $p(n)$ time. But this is one instance for every (sufficiently large) $n$. In principle, this could be the only hard instance for that value of $n$, and all other instances for that $n$ could be easy. So how hard are NP COMPLETE problems in practice?

I'll refine that question to: Are there NP COMPLETE problems that are somehow easy in practice?

The definition of "easy" is left open. One definition may be given by average-case complexity, another one could be given "smooth complexity", another could be given by Fixed Parameter Tractability, efficient approximability, polynomial-time solvability with an advice oracle, efficiency in practice without a mathematical definition etc. I'm hoping that by leaving the definition of "easy" open, I can get a wider range of answers. Any definition of "easy" should imply that the problem is easy "in real life" or "in practice". Also, don't assume I know any of that stuff I just listed in any detail.

Honestly, SAT seems pretty easy in practice. SAT solvers are routinely used on instances with millions of variables that arise in model checking against formal specifications.


How many unique counting functions there are for strings of N bits? Let a counting function inc for inputs of N bits be defined as:

inc(b0 | b1 ... | bN) = F0(b0) | F1(b0,b1) ... | FN(b0,b1,...bN)

Where FN is a function from N bits to a bit, and such that the period of inc is 2^N. Notice that, here, we have a special restriction: the nth bit of the output of inc must only depend on bits that come before the n+1th bit of the input. This is obviously the case for the traditional counting function. How many unique inc functions there are for a given N?

Example

For n = 3, there are at least two unique functions:

# Example 0

F(b0 | b1 | b2)
   = not(b0)
   | xor(b0, b1)
   | if b2 then and(b0,b1) else or(b0,b1)

Produces the usual counting: 000, 100, 010, 110, 001, 101, 011, 111, 000...

# Example 1

F(b0 | b1 | b2)
    = not b0
    | xnor(b0,b1)
    | if b2 then and(b0,b1) else or(b0,b1)

Produces the sequence: 000, 110, 011, 101, 001, 111, 010, 100, 000...

Suppose that a set of functions $F_0,\ldots,F_{N-1}$ satisfies the constraints, generating the sequence $x_0 = 0^N, x_1, \ldots, x_{2^{N-1}-1}$. When does a function $F_N$ satisfy the constraints?

If $F_N$ works, then it generates a sequence of the form
$$ x_0\alpha_0, \ldots, x_{2^N-1}\alpha_{2^N-1}, \\x_0\alpha_{2^N}, \ldots, x_{2^N-1} \alpha_{2^{N+1}-1}. $$
The $\alpha_i$'s are given by the following rules: $\alpha_0 = 0$, and for $0 \leq i \leq 2^N-1$,
$$
\alpha_{i+1} = F_N(x_i\alpha_i), \\
\alpha_{2^N+i+1} = F_N(x_i\alpha_{2^N+i}).
$$
In order for the period to be $2^{N+1}$, we must have $\alpha_{i+1} \neq \alpha_{2^N+i+1}$. This means that there is a function $G_N\colon \{0,1\}^{N-1} \to \{0,1\}$ such that
$$ F_N(x\alpha) = G_N(x) \oplus \alpha. $$
It follows that for $0 \leq i \leq 2^N-1$, we have
$$
\alpha_{i+1} = F_N(x_i \alpha_i) = G_N(x_i) \oplus \alpha_i, \\
\alpha_{2^N+i+1} = F_N(x_i \alpha_{2^N+i}) = G_N(x_i) \oplus \alpha_{2^N+i}.
$$
In particular, this implies that
$$
\alpha_{2^N} = G_N(x_0) \oplus \cdots \oplus G_N(x_{2^N-1}).
$$
We must have $\alpha_{2^N} = 1$ in order to have a period of $2^{N+1}$, and this gives one constraint on $G_N$.
One can check that there are no other constraints, and so the number of possibilities for $F_N$ is $2^{2^N-1}$. In total, the number of possibilities is
$$
2^{2^0-1 + \cdots + 2^N-1} = 2^{2^{N+1}-N-2}.
$$
When $N=0,1,2$, this works out to be $2^0,2^1,2^4$. The corresponding sequences are:

For $N=0$, we have one sequence, $0, 1$.

For $N=1$, we have two sequences, $00, 10, 01, 11$ and $00, 11, 01, 10$.

For $N=2$, we have 16 sequences:
$$
000, 100, 010, 110, 001, 101, 011, 111 \\
000, 100, 010, 111, 001, 101, 011, 110 \\
000, 100, 011, 110, 001, 101, 010, 111 \\
000, 100, 011, 111, 001, 101, 010, 110 \\
000, 101, 010, 110, 001, 100, 011, 111 \\
000, 101, 010, 111, 001, 100, 011, 110 \\
000, 101, 011, 110, 001, 100, 010, 111 \\
000, 101, 011, 111, 001, 100, 010, 110 \\
000, 110, 010, 100, 001, 111, 011, 101 \\
000, 110, 010, 101, 001, 111, 011, 100 \\
000, 110, 011, 100, 001, 111, 010, 101 \\
000, 110, 011, 101, 001, 111, 010, 100 \\
000, 111, 010, 100, 001, 110, 011, 101 \\
000, 111, 010, 101, 001, 110, 011, 100 \\
000, 111, 011, 100, 001, 110, 010, 101 \\
000, 111, 011, 101, 001, 110, 010, 100
$$


Turing machine loop and reject example I'm getting confused on these both. Reject the string does a stop while loop the machine goes on and on.

My textbook has one example on a reject state and no physical one for loop:

Assume that no reject state was given. And I input a string

$1^{q_{1}}011$

After all the transitions the turing machine is now on the empty string $1011 \epsilon^{q_{8}}$ with no where else to go and its not on a accept state, so it rejects.

Now consider if its on q2 at string $0$ so $$10^{q2}11$$

And it cant go anywhere. Would that also reject? Or only if its on the empty string?

Now what is a loop? My idea is

$$1^{q_{1}}011$$

$$1^{q_{2}}011$$

$$1^{q_{1}}011$$

$\dots$

forever

Here's a different way to think about it. Every step, the Turing machine looks at the current cell of the tape, then does the following:

Optionally, move the head left or right
Select a new state, or accept, or reject

If it accepts or rejects, it halts and doesn't do anything further. But this won't necessarily happen: it's also possible for it to get stuck in a loop it can never get out of. Imagine the following machine:

  State 0: if you see a 0, don't move, go to state 0
  State 0: if you see a 1, don't move, go to state 0

It's never going to get out of state zero, it'll just stay in it forever.

It's possible for a single machine to do all three, depending on its input:

  State 0: if you see a 0, don't move, go to state 0
  State 0: if you see a 1, move right, go to state 1
  State 1: if you see a 0, don't move, reject
  State 1: if you see a 1, don't move, accept

Given the input 0 it'll loop, given the input 10 it'll reject, given the input 11 it'll accept.


There are functions with f (n) = f (2n) which can't be calculated I have to proofe that there are functions defined by $f:\mathbb{N} \rightarrow \mathbb{N}, f(n)=f(2n), \forall n\in \mathbb{N}$, which are not-computable. However I'm not really sure about the correct method.

I thought about a proof by contradiction. Assume each of those functions are computable. Then, by the Church-turing-thesis, there has to exist a TM which can compute every of those functions. Therefore $L(M)=\{code(M) | \text{M calculates this type of function}\}$ would be decidable. However I profed earlier, that this language is undecidable. This would lead to a contradiction, but I'm not sure about the correctness of my profe...

Thank you for your help :)

Cook up some encoding of Turing machines so that if $n$ codes a machine, $2 n$ codes "the same" (perhaps use binary numbers ending in 1 as starting points, and 0s at the end are disregarded, thus making that odd $n$ and $n \cdot 2^k$ represent the same machine). Then use that e.g. $\operatorname{HALT}(M)$ (does $M$ halt if started on an empty tape?) isn't computable.


Diameter of a disconnected graph Given G(V,E) a graph that has 2 connected components, what is the diamter of this graph?

The distance $d_G(u,v)$ between two disconnected vertices $u,v$ of a graph is usually defined as $+\infty$.
As a consequence the diameter of a disconnected graph $G=(V,E)$ is
$$
\textrm{diam}(G) = \max_{u,v \in V} d_G(u,v) = + \infty.
$$


Grover algorithm when element not present in the array/database I've been reading about the Grover algorithm for finding elements in an unstructured database by the means of quantum computing, and even done some exercises.

What I don't understand (and can't find anywhere) is what is supposed to happen if the element is NOT present in the database. The oracle would never flip any qubit, and then I don't know what would happen with the inversion about the mean operator. Would the algorithm keep iterating forever?

The most basic version of Grover's algorithm has a fixed number of iterations and assumes there is one marked item. If there is no marked item instead of one marked item, you will do those iterations but then get a random answer.

As mentioned in the wikipedia article on Grover's algorithm, the algorithm can be extended to work when there are an unknown number of marked items while still running in $O(\sqrt{N})$ time. There's just more details to work out.


What's the runtime complexity of this algorithm for breaking up string into words? I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to divide the input string $s$ into a series of words in the dictionary. In this case, the two allowed outputs would be ["bed", "bath", "and", "beyond"] and ["bed", "bat", "hand", "beyond"]. Both outputs are allowed and none is better than the other.
Here is my recursive solution. On input $s$, it either outputs a decomposition of $s$ into a sequence of words in the dictionary, or Fail.

If the input $s$ is empty, output the empty decomposition.
Otherwise, go over all prefixes of $s$. For each prefix that belongs to the dictionary, recursively try to decompose the corresponding suffix, and if successful, output the corresponding decomposition.
If no decomposition was found, output Fail.

In order to speed up the procedure, I envision using memoization. That is, I maintain a hashtable with answers to previous queries, and on input $s$, I first check whether I already know the answer for $s$. If not, after computing the answer, I put it in the hashtable.
If no memoization is used, the runtime is clearly exponential: we have $O(n)$ branching factor, and $O(n)$ as the depth: $O(n^n)$. With memoization; however, the algorithm seems to be polynomial: the procedure can be called with at most $n$ different inputs, and it then performs a polynomial amount of work on it.
I've been told by a very knowledgeable person that it's still exponential. Could someone explain why? I've been thinking very hard about it and I'm not sure why that's the case. If it matters, I'm implementing this algorithm in python.

The running time is polynomial with memoization.  If the original input string has $n$ characters, then there are only $O(n)$ possible suffixes of the original string, the function is only called on a suffix of the original string, and (ignoring recursive calls) the time to execute the function is polynomial; so the total running time with memoization is polynomial.


LTL properties in bounded model checking via assertions Is there a way to check LTL properties in a bounded model checker?

As an example, consider a liveness property ($G F p$ - always eventually $p$)? Suppose we have the following trivial program

#include <pthread.h>
int a = 0;
void * f(void * x)
{
  a = 1;
  return x;
}
int main()
{
  pthread_t t;
  pthread_create(&t, 0, f, 0);
  while (a == 0);
  return 1;
}

Is "always eventually main terminates" expressible in a bounded model checker using only assertions?

In principle, you can construct a Büchi automaton from an LTL formula, express it in the modeling language (e.g. as C code) and run it in parallel to the model/program. However, unbounded loops pose a problem to the bounded model checker. Hence, I wonder how such properties can be expressed using assertions, e.g. in CBMC.

The property "always eventually main terminates" should be expressible and verifiable in a bounded model checker. For such properties, the model checker would either verify the property or find a "acceptance cycle" that shows that there exists a loop in an execution trace that does not satisfy the property (by considering execution traces of bounded lengths).

For example, the given property can be expressed in the SPIN model checker with:

int a;
bool end;

proctype thread1() {
  a = 1;
}

init {
  a = 0;
  end = false;
  run thread1();
  do
  :: (a == 0) -> skip;
  od;
  end = true;
}

ltl prop { always (eventually end) }

The code follows the given C code, where do simulates checking the condition with while loop. When checking if prop holds, SPIN will find an "acceptance cycle" that shows that main might get constantly scheduled for execution and starve thread1, thus refuting the formula. If a "fair" scheduler is assumed (e.g. with enforcing "weak fairness" SPIN reference), the property will be proven correct.

Note that although such (liveness) properties should be supported, by expressing them in LTL (or other logics like CTL), it is not clear how could they be expressible only with assertions (since assertions state something about the state at particular program point).


What edge-set is required to make a non-cyclic directed disconnected graph initial? Is there an algorithm to find the minimum set of edges required from a new node in order to make a disconnected directed graph initial?

Example -

input:

a -> b;
b -> c;
b -> d;
e -> f;
f -> g;

output:

n -> a;
n -> e;

Result:

Thanks!

Assuming that "initial" means connected and having a single source, you can do no better than adding an edge to each source.


Proving that a language is a CFL Assume that $L_1 \subseteq \Sigma^*$ is a CFL and that $y \in \Sigma^∗$ is a string.
I need to prove that the language $L_2 = \{x \in L_1 \mid x \text{ does not contain $y$ as substring}\}$ is a CFL.
I tried pumping lemma for CFLs, but it seems that is for disproving that languages are CFLs. I also tried to create a CFG for this language, but I'm having a hard time. I even took a look at the membership problem for CFGs.
Any ideas on how I would go about proving this?

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


Attempt to write a function with cubed log runtime complexity $O(\log^3 n)$ I'm learning Data Structures and Algorithms now, I have a practical question that asked to write a function with O(log3n), which means log(n)*log(n)*log(n).

public void run(int n) {
    for (int i = 1; i < n; i *= 2) {
        for (int j = 1; j < n; j *= 2) {
            for (int k = 1; k < n; k *= 2) {
                System.out.println("hi");
            }
        }
    }
}

I have come with this solution, but it seems not correct. Please help me out.

Your program is correct. Your could also iterate Math.Log(n)*Math.Log(n)*Math.Log(n) times. Not sure if that is considered cheating.


Prove that $NP^{NP\cap co-NP} = NP$ Let $A\in NP\cap co-NP$. Then, $NP^A = NP$.

At first, I thought: Easy, let $L\in NP^A$ s.t. $A\in NP\cap co-NP$. Let $M_L$, an $NDTM$ to decide $L$ and $M_A$, an $NDTM$ to decide $A$. Then, we could create a new $NDTM$, $M$ which acts the same as $M_L$, but instead of calling the oracle, it simulates $M_A$ on the oracle's input.

That is wrong as far as I understand; We can't simulate an $NDTM$ that way since $M_A$ may have some computation paths which rejects and some which accepts and we wouldn't know how to act.

What should I do instead?

Since $A \in \mathsf{NP} \cap \mathsf{coNP}$, there is a witness both for $x \in A$ and for $x \notin A$. An NP machine which wishes to (non-deterministically) find out whether $x \in A$ or not can guess the answer ($x \in A$ or $x \notin A$) and then verify it using a witness.


What are the gap functions in the $AC$ hierarchy? Hastad had in 1985 shown that PARITY(n) if it has to be evaluated by a depth$-d$ $AC^0$ circuit needs a size $\Theta(2^{n^{\frac{1}{d-1}}})$. But PARITY is in $NC^1$ and PARITY is also the negation of the MOD2 and hence this shows that the following inclusions are strict, $AC^0 \subset AC^0[2] \subset NC^1$.

If I understand right then Razborov's 1987 result of exponential size lower bound for MAJORITY for $AC^0[2]$ or Smolensky's similar result in 1986 for MOD3 for $AC^0[2]$ do not in anyway strengthen the inclusion consequence of Hastad's result. Am I right?
But do we know whether $AC^i$ vs $AC^{i+1}$ separation is strict or not? Like do we know of functions which are exponentially sized for $AC^i$ but can be computed by polynomial sized circuits for $AC^{i+1}$?

Razborov-Smolensky prove that the classes $\mathrm{AC}^0[p]$ and $\mathrm{AC}^0[q]$ are incomparable when $p$ and $q$ are distinct primes, which also implies
$$\mathrm{AC}^0\subsetneq\mathrm{AC}^0[p]\subsetneq\mathrm{ACC}$$
for prime $p$. That's about it: it is consistent with the present knowledge that uniform $\mathrm{AC}^0[6]$ coincides with all of the polynomial hierarchy PH, so no classes in between have been unconditionally separated (uniformly or nonuniformly).


Time complexity of quicksort for arrays in increasing or descreasing order Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order.

Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using quicksort.

I think $c_1 = c_2$ and $c_1=O(n^2)$? Is this correct ?

I am using the last element as a pivot for each partition.

Quicksort is just an idea. There are algorithms and implementations.

Only stupid implementations will run in O(n^2) for sorted or reversed sorted arrays. Good sorting implementations actually check for elements in ascending or descending order at the beginning and end of the array and will handle either case in O(n), because wanting an array sorted without checking that it is sorted before is such a common case. Such implementations will fall back on Quicksort for handling the more difficult parts.

(It’s not just sorted arrays. You can have a general algorithm that sorts the concatenation of two sorted arrays in O(n), or a sorted array with fewer than O(n / log n) random elements added, or a sorted element with one random element changed).


2 approximation algorithm for the single machine scheduling problem We are given one machine and $n$ jobs that we want to process.

For the $n$ jobs we have the following data:

$r_{1}, ... , r_{n}$ are the release times

$p_{1}, ... , p_{n}$ are the processing times

$d_{1}, ... , d_{n}$ are the deadlines/due dates

$c_{1}, ... , c_{n}$ are the completion times(when the jobs are finished executing)

$l_{1}, ... , l_{n}$ are the latenesses achieved where $l_{j} = c_{j} - d_{j}$

Our goal is to find a schedule that minimizes the maximum lateness achieved ($L^{*}_{max}$)

Since even deciding whether there is a schedule such that $L^{*}_{max} \leq 0$ is np hard, this implies that we can not come up with an approximation algorithm of any ratio $\rho > 0$ that runs in polynomial time and produces a schedule with maximum lateness at most $\rho L^{*}_{max}$. So this is why we make the assumption that the due dates are negative, ie $d_{i} < 0$

Before trying to come up with an algorithm, we can prove that for any subset $S$ of jobs, $L^{*}_{max} \geq r(S) + p(S) - d(S)$ where $r(S) = min_{j\in S}r_{j}$, $p(S) = \sum_{j\in S}p_{j}$ and $d(S) = max_{j \in S} d_{j}$.

To prove this what we have to do is look at the last job of the optimal schedule and try to find its lateness, which will also be a lower bound for the maximum lateness achieved.

Now, having this as a fact for any schedule, assume our algorithm produces a schedule as follows. At each moment the machine is idle, start processing next the available job with the earliest due date.

The analysis I have in my book (the design and analysis of algorithms by Williamson and Shmoys) is as follows:

We consider the schedule produced by our algorithm and let $j$ be the job of maximum lateness in the schedule. That is $L_{max} = c_{j} - d_{j}$. We focus on the time $c_{j}$ in this schedule and try to find the earliest point in time $t \leq c_{j}$ such that the machine was processing without any idle time for the entire period $[t, c_{j})$. By our choice of $t$, we have $r(S)=t$. Let $S$ be the set of jobs that are processed in that interval. From the bound about the maximum lateness we found before, we have that $L^{*}_{max} \geq r(S) + p(S) -d(S) \geq r(S) + p(S) = t+p(S) = c_{j}$

Then we only focus at the last job $j$, so we get $L^{*}_{max} \geq r_{j} + p_{j} - d_{j} \geq -d_{j}$

combining both the equations we get $c_{j} - d_{j} \leq 2L^{*}_{max}$

what I don't understand is, where do we actually need the earliest due time rule?  Where do we use it in the analysis? What would happen if we used the longest due time rule? Could we then apply the same analysis to come up with the same approximation ratio?

This is an error in the book. The earliest deadline condition is not used any where in the analysis. This means that we can achieve the 2-approximation algorithm even if we drop this condition.


A query about serial data transmission I was studying computer science and I learnt that Serial Data transmission is when one bit is transmitted at a time over one wire/channel. Then what does '8 bit serial' data transmission mean?
I was studying about MIDI where it said it uses 8 bit serial data transmission and is asynchronous.

Also, I cannot seem to find an appropriate tag to set to this question.

It was probably a rather unfortunate abbreviation of 8-N-1 serial transmission which is what MIDI uses. The 8 bits are sent serially, one at time, still.


Finding shortest path between two nodes with a set of forbidden nodes I have undirected and unweighted graph, in which I would like to find the shortest path between two entered nodes. There is also a set of forbidden nodes. How to find the shortest path, if I am allowed to visit at most one node from the set of forbidden nodes?

Create two directed copies of the graph, one without the forbidden nodes. Connect the outgoing edges of the "forbidden" nodes to the second graph.


Can a Turing machine or Push Down Automaton construct languages of type 3? I am not quite sure, whether automata can construct languages over their types. For example, a Push down automaton can construct a language of type 2 - does that mean that a PDA also can construct a language of type 3? The same for turing machine?

The set of languages of type $3$ is a proper subset of the of languages of type $2$. In other words, a language of type $3$ is also a language of type $2$.
If some automaton can recognize languages of type $2$, then it can also recognize languages of type $3$.


Sample compression scheme and bounding the VC dimension There is a compression function takes any sample $S$, for which there exists a function $h ∈ H$ with $L_S(h)$, and compresses it to a subset of $k$ sample points. Similarly, there is a decompression function $\rho$ which maps this compressed set back to a classifier $h'$ (not necessarily in $H$), such that $h'$ makes no mistakes on the original sample $S$.
Let $C(H)$ denote the smallest natural number $k$ such that $H$ admits a compression scheme of size $k$. $\mathrm{VC}$ stands for VC dimension.
I want to prove that $$\mathrm{VC}(H) ≤ C(H).$$

Suppose that $H$ shatters a set $S$ of size $\ell$, and has a compression scheme of size $k$. For each of the $2^\ell$ labelings of $S$, the compression scheme associates a labeled subset of size $k$, in an injective way. There are $2^k \binom{\ell}{k}$ such labeled subsets, and so $2^\ell \leq 2^k \binom{\ell}{k}$. Using $\binom{\ell}{k} \leq (e\ell/k)^k$, this shows that $2^{\ell-k} \leq (e\ell/k)^k$, and so $2^{\ell/k} \leq 2e\ell/k$, implying $\ell < 5k$.
Here is an example showing that we cannot improve this to $\ell \leq k$. Consider the set of all functions from $[k+1]$ to $\{0,1\}$. We give a compression scheme of size $k$. Given a labelling $(\ell_1,\ldots,\ell_{k+1})$, we remove either $(1,\ell_1)$ or $(2,\ell_2)$ according to the parity of labels. This is injective, since we can reconstruct the missing label from the index of the missing point.


How to prove polynomial time equivalence? Define the problem $W$:

  Input: A multi-set of numbers $S$, and a number $t$.

  Question: What is the smallest subset $s \subseteq S$ so that $\sum_{k \in s} k = t$, if there is one? (If not, return none.)

I am trying to find some polytime equivalent decision problem $D$ and provide a polytime algorithm for the non-decision problem $W$ assuming the existence of a polytime algorithm for $D$.

Here is my attempt at a related decision problem:

  $\mathrm{MIN\text{-}W}$:

  Input: A multi-set of numbers $S$, two numbers $t$ and $k$.

  Question: Is there a subset $s \subseteq S$ so that $\sum_{k \in s} k = t$ and $|s| \leq k$?

Proof of polytime equivalence:

Assume $W \in \mathsf{P}$.

solveMIN-W(S, t, k):
1. S = sort(S)
2. Q = {}
3. for i=1 to k:
4.     Q.add(S_i)
5.     res = solveW(Q, t)
6.     if res != none and res = t: return Yes
7. return No

I'm not sure about this algorithm though. Can anyone help please?

The problems you mention here are variations of a problem called SUBSET-SUM, FYI if you want to read some literature on it.

What is $S_i$ in your algorithm? If it's the $i$-th element, then you assume that the minimal set will use the smaller elements, which is not necessarily true - there could be a large element that is equal to $t$, in which case there is a subset of size $1$. So the algorithm doesn't seem correct.

However, as with many optimization problems that correspond to NP-complete problems, you can solve the optimization problem given an oracle to the decision problem.

First, observe that by iterating over $k$ and calling the decision oracle, you can find what is the minimal size $k_0$ of a subset whose sum equals $k$ (but not the actual subset).

After finding the size, you can remove the first element in $S$, and check whether there is still a subset of size $k_0$ - if not, then $s_1$ is surely in a minimal subset, so compute $t-s_1$, and repeat the process with the rest of $S$.

If $s_1$ does not effect the size $k_0$, then repeat the process with $S\setminus \{s_1\}$.

It is not hard to verify that this process takes polynomial time.


construct a TM from a PDA Given a PDA $P=(Q,\sum,\delta,q_0,F)$ construct formally a TM that accepts $L(P)$.

My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add $q_a$ for accept and $q_r$ for reject and to send to $q_a$ if the TM stops on states in $F$ and send to $q_r$ otherwise.

But I am having a trouble to define new the transition function for the TM: $\delta_M$.

Your idea is correct (or at least one way of doing it), though it may be "easier" to add a third tape, where you just write the current PDA state. Your transition function just needs to simulate the PDA. The alphabet for the input tape is just the PDA's input alphabet plus the blank, the alphabet for the stack tape is the stack alphabet plus the blank symbol. You read a symbol on the input tape, the PDA state and the current symbol on the stack, move the input head right and maybe write a symbol on the stack tape and stay put, write a symbol and move right, or erase a symbol and move left. The state tape head just stays put and writes the new state on the tape. If you read a blank on the input tape, and the current PDA state is accepting, move to the TM's accept state, if you otherwise read a blank on the input tape, then move to the TM's reject state.

Given a PDA transition $\delta_{PDA}(q_{i}, \sigma, \tau) = (q_{j}, \rho) $ (so moving from state $q_{i}$ to $q_{j}$, with $\sigma$ in the input, popping $\tau$ and pushing $\rho$), the TM transition looks something like $\delta_{TM}(q_{p}, \sigma, \tau, q_{i}) = (q_{p}, (\sigma, R), (\rho, S), (q_{j},S))$ - the notation here is somewhat abused, mostly to group each tapes actions together in order. Transitions that have one or more $\varepsilon$/$\lambda$ in them complicate things a little, the input tape head would not move on an $\varepsilon$, the stack tape head might move left or right, depending on whether it was a pop or push that had the $\varepsilon$.

This gives you a TM with a single state that does all the real work, and the accept and reject states.


Can a context-senstive gramma contains production rule $cB\rightarrow Bc$? Some textbook show that the grammar $G=(N,T,P,S)$ below belongs to context-senstive grammars:

S->aSBC
S->abc
cB->Bc
bG->bb

where N={S,B}, T={a,b,c}.

I am confused by the fact that the production rule cB->Bc cannot satisfy the definition of a CSG. So, why is the above grammar belongs to CSG?

Your confusion is not unexpected. That grammar is not a context-sensitive grammar in its usual strict sense.

However, that grammar can be considered as a context-sensitive grammar in some situations. The Wikipedia entry on context-sensitive grmmar reads the following.

  Some definitions of a context-sensitive grammar only require that for any production rule of the form $u \to v$, the length of $u$ shall be less than or equal to the length of $v$. This seemingly weaker requirement is in fact weakly equivalent, see Noncontracting grammar#Transforming into context-sensitive grammar.

You may want to double check the definition of CFG and exposition thereafter in the textbook you mentioned.


Find an invariant in the minimum algorithm I have the following simple algorithm to find the smallest element of an array $A$ of numbers:

m = A[0];
For i = 0 to A.length() do
    if m < A[i] then
        m = A[i];
    end
end
return m;

The complexity of this algorithm is $O(n)$ where $n$ is the length of $A$.

I would like to prove the correctness of this algorithm using an invariant. Yet I don't know which invariant is nice here.
Maybe something like: $m$ is the minimum of the subarray $A[1..k]$.

The invariant is good (once you fix lots of imprecise things, like the 1..k which is obvious nonsense, and wouldn’t proof correctness. Precision is important. ) The code is broken, so your proof should fail - because it would be an invariant of a correct algorithm, but not your code posted here.


What is the name of this function of a tree? I've written a recursive function of a tree, and I would like to know what it's called!  It's not quite the same as the height or the width of a tree, but it seems kind of like a width.

Assuming the tree $T$ is binary, we can define the function $f(T)$ as follows.  If $T$ has a only a single node, let $f(T) = 1$.  Otherwise, let $T_0$ and $T_1$ be the two trees rooted at the child nodes $T$'s root.  If $f(T_0) = f(T_1)$, then let $F(T) = F(T_0) + 1$; otherwise, let $f(T) = \max(f(T_0), f(T_1))$.

The function $f$ is generalized as follows to trees that are not necessarily binary.  As before, let $f(T) = 1$ when $T$ has no edges.  Otherwise, let $T_0, \dots, T_k$ be the $k+1$ subtrees rooted at the child nodes of $T$'s root, sorted by descending values of $f$.  Then let $f(T) = \max_i(f(T_i) + i)$.

This is basically the Strahler number, which is great because now I can call my function ComputeStrahlerNumber instead of keeping the profane function name I was using as a placeholder.


How/why is switch made from equation to inequality for certificate of optimality for dual problem in linear programming? I am reading Chapter 7 Linear Programming in Algorithms by Dasgupta et al.
I don't get how they switch from an equation to an inequality specifically the part highlighted in red/pink regarding the multiplier $y_1 + y_3 ≥ 1$ instead of $y_1 + y_3 = 1$

If the required conditions are met then you have
$$ x_1 + 6x_2 \leq (y_1+y_3)x_1 + (y_2+y_3)x_2 = y_1 x_1 + y_2 x_2 + y_3(x_1 + x_2) \leq 200y_1 + 300y_2 + 400y_3$$
By looking at the leftmost and rightmost expressions you get the inequality you want.


Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle The following is an excerpt from a material on NP-Theory:

"Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a
path from s to t using edges of G, on which each vertex of G appears once and only once. By
HAM-PATH we denote the problem of determining, given G, s and t, whether G contains a
Hamiltonian path from s to t. I now explain a reduction
HAM-PATH < HAM-CYCLE.
Let G, s, t constitute an input for HAM-PATH. We want to convert it to an input G′ (an
undirected graph) for HAM-CYCLE. We add a new vertex u to the vertex set of G in order
to obtain the vertex set for G′. The edges of G′ are all the edges of G plus two extra edges
(u, s) and (t, u). I leave it to the reader to visualize that G′ contains a Hamiltonian cycle if
and only if G contains a Hamiltonian path from s to t."
I am confused as to why do we need to add a vertex u to create G′. Why can't we simply connect s and t and then check for a Hamiltonian Cycle. If it exists, then a path would also exist(as path is a sub-graph of cycle in an undirected graph) and we would be done. What am I missing? I am specially asking this for undirected graphs. I am clear about directed graphs that existence of cycle having s and t does not guarantee Hamiltonian path.

Illustrations or counter examples are welcome!

If the vertex $u$ is not added to to $G'$, then a Hamiltonian cycle in $G'$ does not necessarily correspond to a Hamiltonian path from $s$ to $t$. This is because the cycle may not have $s, t$ adjacent to each other.
For example, one could have

Since there is no Hamiltonian path from $s$ to $t$ in the first graph, there is no Hamiltonian cycle in the second graph. However, if you didn't include $u$,

then there is a Hamiltonian cycle so the reduction fails.


Decremental reachability in a grid graph Consider an $n$ by $n$ grid graph. For example, the following.

You can of course reach the top left corner from the bottom right.  Now consider the graph dynamically with an arbitrary number of edges deleted at each step.

  What is the time complexity of determining whether you can still reach
  the top left corner from the bottom right after edge deletions?

Further clarification.

Queries. There is exactly one type of query which gives a Boolean output.  That is whether there is a path from the top left corner to the bottom right.

Updates. An update can delete an arbitrary number of edges greater than $0$.

Complexity.  Each update is followed by a query. The complexity I am interested in is the amortized time over all updates and queries.  The best this could possibly be would be proportional to the number of deleted edges I assume.

I found these lecture notes which say you can get $O(\log{n})$ time for planar graphs per individual edge deletion (the Eppstein et al. reference). However this paper supports many more operations than I need, my graph is a special case of a planar graph and my updates are in batches in a sense.  The most important difference may just be that I am only interested in the decremental version. I haven't found anything specialized for batched, decremental connectivity in a grid graph.

Is there anything simpler than the Eppstein et al. paper for my special case or alternatively faster than $O(\log{n})$ time per edge deletion?

By improving on @emab's idea, you can achieve $\Theta(\alpha(n^2))$ amortized time per deletion and query, where $\alpha$ is the inverse Ackermann function, i.e. almost constant.

Initialize a union-find data structure with an enry for each square of the grid graph and two entries each for the two pairs of outside faces top+right and bottom+left.
For an example of $n=3$, the faces $1,2,3,\ldots,9,A,B$ in the diagram below are initialized. Where $A,B$ are the outside faces split by the dashed lines.

When removing an edge call union() on the two squares (or the sqare and $A$ or $B$) separated by that edge.
To check connectivity, call find() on the faces $A$ and $B$. If the results differ, return true, else return false.


Maximum flow with Edmonds–Karp algorithm I am learning Edmonds–Karp algorithm , I formed following flow network, (capacity is described above arrow, where s is source and t is sink.)

If we first follow path S - A - C - T , we will get max flow equals to 1 as we cannot take path S - B - C - T (residual flow from C -- T became 0). I am also assuming that while doing BFS when we reach to t from c, we are stopping our BFS search and returning path. There is D left in the queue but we will ignore it as we have got one augmenting path. On next iteration we will move to B as S -- A edge residual capacity is 0.

If we first follow path as S - A - D - T and then S - B - C - T , we get max flow as 2.

I think, I am missing some basics, I belive algorithm does not dependend on which path I take first.

Thanks in advance.

I'm sure you have a misunderstanding.  Try simulating the Edmonds-Karp algorithm by hand on the first example, then edit the question to show the residual graph you've got after it finishes.  I'm sure you'll find there remains an augmenting path from $s$ to $t$ in the residual graph.  If you don't draw the residual graph explicitly, you might fail to notice the path -- you can't do this in your head without drawing the graph on paper.

Many students get tripped up by the fact that there might be an augmenting path in the residual graph that looks like it goes "backwards" in the original graph; that's OK, and it still counts as an augmenting graph.


How can I develop a pseudo-polynomial time algorithm for a non-integer problem? I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5,  \exists j \in J$.

Since the problem will be trivial if $\beta_j > 0.5, \forall j \in J$, I can not assume that we may transform an instance to an integer one. By the way, I am looking for the computational complexity of the problem.

So my question is: How can I develop a pseudo-polynomial time algorithm for the problem (to indicate that it is at most NP-hard in the ordinary sense), although the problem is not integer-value?

Classifying algorithms as pseudo-polynomial time is not really a meaningful concept if there are no numbers (integers) in the instances. Of course, it is up to you to define what parts of the input should be considered "numbers".

Using real numbers in the inputs is a bad idea in the first place if you want to be able to analyze complexity or computability of the problem, as there is no way to encode all real numbers as finite strings from a finite alphabet.

For your problem, you may be able to turn it into an equivalent integer problem using some scaling, but it is impossible to say from the description given. Otherwise I would suggest you redefine the problem with rational parameters instead. This allows you to analyze it as a normal computational problem, and you could also meaningfully talk about pseudo-polynomial time if you, for example, consider numerators and denominators as separate integers.


Efficiently representing a set of sets (The question is an extension of this unanswered question on stackoverflow)

If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in a DAG instead of a tree that is even more compact.

However, if we have a set of sets (i.e. the order does not matter), there are a lot of possible tries that represent the same set of elements.
An example can be found in the stackoverflow question I linked above.

Edit: For example, assume that we are given the following sets of integers.

{1,2,3,4,5}
{1,2,6,7}
{1,2,4,7}
{1,3,5,7}

Two possible representations are shown below (trie on the left, DAG on the right)

My questions are:

  How hard is the problem of finding an optimal (i.e minimal) such trie?
  Are there any fast algorithms for solving this problem?
  If not, are there any fast algorithms that find "good" tries?
  What about the DAG case?

In the scenario I have in mind there is an additional constraint that no set is a subset of another set.

Any link/paper that is even slightly relevant to any of the questions is helpful.

I suggest you start by looking at BDDs and ZDDs.

Your problem is similar to the problem of finding an optimal BDD.

I'll explain.  Suppose we have sets $S_1,\dots,S_k$ over a universe $U$ containing $n$ items (so $S_i \subseteq U$).  A BDD is a finite-state automaton (a DAG) for recognizing the language of all of the allowed sets, where each set is presented to the finite-state automaton as the $n$-bit string that is the characteristic function of that set.  In other words, given a total order on $U$, each set $S \subseteq U$ corresponds to a binary string $[S] \in \{0,1\}^n$: $[S]_i=1$ if $S$ includes the $i$ element of $U$, otherwise not.  (This order is known in the BDD literature as a "variable ordering".)  Then define the language $L$ by $L=\{[S_1],[S_2],\dots,[S_k]\}$.  A BDD is a finite-state automaton that recognizes the language $L$.

Notice that you have the freedom of what "variable ordering" to choose.  The choice of the variable ordering determines how each set is represented as a binary function, which can affect the size of the BDD.  It is well-known that the problem of choosing the optimal variable ordering (the one that leads to the smallest BDD) is NP-hard.  Nonetheless, there are various heuristics for trying to find a good variable ordering, and in real-world problems, they often work reasonably well.

So, your problem can be framed as the problem of choosing the optimal variable ordering to represent your sets as a BDD.

ZDDs are a variant of BDDs that are better in some circumstances.  ZDDs are especially oriented at representing a set of sets, so they might be particularly helpful for your needs.  ZDDs are especially handy if you need to represent a bunch of sets that are related to each other in some way; ZDDs provide a compact and efficient encoding for that situation.


What is the point of the "check" array in a triple-array trie? I am currently reading the definition of a triple-array trie as described here.

More precisely, I am trying to understand the nature of the three arrays:

  base. Each element in base corresponds to a node of the trie. For a trie node s, base[s] is the starting index within the next and
  check pool (to be explained later) for the row of the node s in the
  transition table.
  next. This array, in coordination with check, provides a pool for the allocation of the sparse vectors for the rows in the trie
  transition table. The vector data, that is, the vector of transitions
  from every node, would be stored in this array.
  check. This array works in parallel to next. It marks the owner of every cell in next. This allows the cells next to one another
  to be allocated to different trie nodes. That means the sparse vectors
  of transitions from more than one node are allowed to be overlapped.

I understand how those three arrays are linked together, but I fail to see the point of the "check" array. It seems to me like you could walk the trie without using the "check" array at all.

What am I missing?

It is a bit confusing. Suppose the alphabet has size $\Sigma$.

Basically the idea is that instead of allocating each state an entire block of $\Sigma$ elements in next[] to hold the target states for each possible input character, most of which would just hold a special "this transition is invalid" sentinel value since there are typically only a few valid transitions from each state, check[] lets us "overlap" these blocks of $\Sigma$ elements, and thereby save space, provided there are no "collisions" -- that is, elements in next[] that correspond to valid transitions from more than one state.

A crucial piece of information that seems to be missing from the article (I only read down to the beginning of the next section, "Double-array Tree") is that initially all check[] values must have some special "no current owner" sentinel value (which in practice would be something like -1).

Think of each element in next[] as a resource slot, which can be either unallocated (as it is initially), or allocated to exactly one source state: check[i] tells you which source state the i-th element is allocated to (or if it is unallocated). The rule is: If a source state s does not own the slot in next[] that corresponds to the transition on some character c, then there is no valid transition from state s on character c. Specifically, check[base[s] + c] != s, which literally means "State s does not own slot base[s] + c in next[]", also implies "State s has no transition on character c".

In this way, all the elements of next[] that would have been set to a "this transition is invalid" sentinel value in the original every-state-gets-its-own-block-of-$\Sigma$-elements-in-next[]-to-itself scheme become available to be used by some other source state. If some such element, say at position i, is later needed by some other state s, then check[i] will be set to s at that time.

Example

First let's initialise the triple-array trie data structure.

Suppose the alphabet is the digits 0-9, the states range from 0-49, and we have the following transitions for state 17, to which we allocate the block of 10 elements starting at position 20 in next[]:

Transitions from state 17
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     3     |     40     |      23     |
|     5     |      6     |      25     |
|     8     |     13     |      28     |

After adding this information to the triple-array trie, base[17] = 20, next[23] = 40, next[25] = 6 and next[28] = 13, and check[23], check[25] and check[28] are all set to 17, with every other element in check[] remaining at its initial value of -1.

Now suppose we that we have the following transitions for state 35, to which we try to allocate the overlapping block of 10 elements starting at position 22 in next[]:

Transitions from state 35
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     2     |     10     |      24     |
|     3     |     33     |      25     | <-- COLLISION

There is a problem, since next[25] is needed by both source states. We detect this by noticing that check[25] != -1. In this case, either state 17's or state 35's range of slots in next[] has to be reallocated somehow. Let's reallocate state 35's range. First, undo the allocation already done (set check[24] back to -1; it is not necessary or helpful to change next[24] to anything, since there is no meaning attached to the value of next[i] when check[i] == -1). Now we will try to reallocate state 25's slot range to start at position 24 in next[]. (Why 24? It's just a value that I know will work. In practice, you would probably need to just keep trying different starting points until one worked, and there is no guarantee that any will work.) Now it looks like this:

Transitions from state 35
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     2     |     10     |      26     |
|     3     |     33     |      27     |

And there will be no collisions. So after adding the information for states 17 and 25 to the data structure, we will have base[17] = 20, base[35] = 24, and next[] and check[] look like this:

|  i  | next[i] | check[i] |
|-----+---------+----------|
|  .  |    .    |     .    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |
| 20  |don'tcare|    -1    |
| 21  |don'tcare|    -1    |
| 22  |don'tcare|    -1    |
| 23  |   40    |    17    |
| 24  |don'tcare|    -1    |
| 25  |    6    |    17    |
| 26  |   10    |    25    |
| 27  |   33    |    25    |
| 28  |   13    |    17    |
| 29  |don'tcare|    -1    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |

Now let's try some queries.

Is there a transition from state 17 on character 5? First see if state 17 owns the relevant entry in next[]: check[base[17] + 5] = check[25] = 17, so it does (and the destination state is then given by next[25] = 6).
Is there a transition from state 35 on character 1? check[base[35] + 1] = check[25] = 17 != 35, so state 35 does not own this entry in next[] => there is no transition from state 35 on character 1.


Sampling of subsets with repeat Given a string S of length n and a positive integer k <= n, we want to randomly, and with equal probability, choose a string from the set of all strings of length k that may be formed with a subset of the letters of S. For example, if S = daddy and k = 2, we want to choose each of the strings da, dd, dy, ad, ay, yd and ya with equal probability 1/7.

Obviously, one could do this by calculating all possible permutations. However, is there a more efficient way?

Let $l$ be the number of distinct characters in the input string. So our input size is summarized by $n, k, l$, with $k \le n$ and $l \le n$.

Here is one efficient way to do it. In the first step, since the order of characters in the string doesn't matter, let's turn it into a map:
$$
M = \{a \mapsto 1, d \mapsto 3, y \mapsto 1\}.
$$
The idea of our algorithm is to first calculate the number of possible permutations of $k$ elements from $M$, and then to use this to generate one randomly.

Step 1: calculating the number of possible permutations

We use dynamic programming. We actually calculate, more generally, the quantity
$$
p[i,j] \qquad \text{ for } 0 \le i \le k \text{ and } 0 \le j \le l,
$$
which represent the *number of permutations of length $i$, which use only the first $j$ elements of the map. For example, in the example problem (input "daddy", $k = 2$), we have
\begin{align*}
p[0, 0] &= p[0, 1] = p[0, 2] = p[0, 3] = 1 \quad \text{(empty string)} \\
p[1, 1] &= 1 \quad \text{(strings of length 1 using only a -- so just "a")} \\
p[1, 2] &= 2 \quad \text{(strings of length 1 using a and d -- so "a" and "d")} \\
p[1, 3] &= 3 \quad \text{("a", "d", and "y")} \\
p[2, 1] &= 0 \quad \text{(no strings of length two using only a since only one a is allowed)} \\
p[2, 2] &= 3 \quad \text{("ad", "da", and "dd")} \\
p[2, 3] &= 7 \quad \text{("ad", "da", "dd", "ay", "ya", "dy", "yd")}
\end{align*}

Now how do we calculate $p$? We can use a recursive algorithm. Let $M[j]$ denote the value of $M$ on the $j$th character (so in our example, $M[1] = 1, M[2] = 3, M[3] = 1$). Then
$$
p[i, j] = \sum_{i' = 0}^{M[j]} \binom{i}{i'} p[i - i', j-1].
$$

What this formula says is: pick $i'$ places to put character $j$. For example, in our running example for $p[2, 3]$, it says pick $i'$ places to put the character $y$ in a string of length $2$. Then for the remaining $i- i'$ places, we fill them in with a string only using the first $j-1$ characters (which can be done in $p[i-i', j-1]$ ways). The variable $i'$ ranges from $0$ to $M[j]$ because we can only use character $j$ at most $M[j]$ times.

This recurrence allows us to calculate the entire table of $p[i,j]$ in approximately $O(nk)$ time.

Step 2: Picking a permutation at random

The total number of permutations is $p[k, l]$. So pick a random number $r$ from $1$ to $p[k, l]$.

Now recall the recurrence relation
$$
p[i, j] = \sum_{i' = 0}^{M[j]} \binom{i}{i'} p[i - i', j-1].
$$

Very roughly, we can use this recurrence relation to enumerate the $r$th permutation.
To evaluate the $r$th permutation of $p[i,j]$ total, evaluate the above sum and locate the term where the $r$th permutation would fall. For example if $r = 4$ and there are $7$ total permutations, and the sum gives you $3 + 4$, then $4$ falls fourth out of $7$, so it falls in the second group. Then, we are looking for the first out of $4$ permutations in the second group, which we can recursively find by picking a random permutation from $p[i - i', j-1]$.


How to calculate run time of insertion sort and Merge sort? I am currently studying computer science and we were given assignment to implement two algorithm(Insertion sort and Merge sort) and run them in order to track their running times across different input arrays. And ask us to do: "Your task is to run each algorithm 3 times on 5 input arrays with 5, 50, 500, 5000, and 50000 random integers each, and report their running times both as a table and "n vs. time" plots"

I have already implemented algorithm but I am not sure how to calculate runtime of both algorithm. Any help would be appreciated. Thank you.

In sorting algorithms you can count the number of comparsions and consider it as run time of worst case. Just add one static counter in your code it will reflect the time complexity in a better form. Otherwise the general approach of calculating run time works fine always. Most language has a function that gives system time.


Non planarity of K3,3 I am reading about planar graphs from this site.

It says:

  The complete bipartite graph K3,3 is not planar, since every drawing of K3,3contains at least one crossing. why? because K3,3 has a cycle which must appear in any plane drawing.

I am not able to get what cycle which must appear in any plane drawing has to do with edge crossing. Can't a cycle appear in plane drawing without crossing edges and thus letting the graph be planar? I must be missing something stupid.

This explanation is wrong. In principle you could prove that $K_{3,3}$ is not planar by enumerating all types of planar embeddings, and show that some paths must cross. If I remember correctly this is the path chosen in some lecture notes, so if you look around you might be able to find this argument. Another route, taken by your lecture notes, is to use Euler's formula.

When your notes say that $K_{3,3}$ isn't planar since it "has a cycle", they were trying to provide you some intuition, not too successfully I reckon. The claim requires a proof which is indeed given later in the notes.


Is a very long plain text password harder to crack than a short complicated password? Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters?

Usually when we talk about "hard to find" we are talking about brute force guessing. This is where the attacker just keeps trying different passwords till they find the right one. I'm going to assume we're talking about this model here and not talk about the real world with hashing and rainbow tables and so forth.

Now, there is nothing inherently different about trying a 5-character random string versus trying a 4-word password. They are both equally easy for a computer to plug in and see if they work. Instead, the question is how many guesses you need to find the password, i.e. how hard is it for an attacker to guess your password.

Now, an important question is what the attacker knows about your strategy of picking passwords.
We usually want to make the worst-case assumption that the attacker knows our method for picking passwords. Under this key assumption, we can compare the two methods.

If we pick a 5-character password uniformly at random from all strings containing a-z,A-Z,0-9,!@#\$%^&*()-_+={}[];:'"|\,<.>/? then we have something like $92^5 \approx 6.6$ billion possibilities. So the attacker has a one in $6.6$ billion chance of guessing it on the first try, and so on.

If we pick 4 random words uniformly from a set of say 500 words, then we have $500^4 = 62.5$ billion possibilities. So in this example, the attacker is worse off trying to guess a 4-word random passphrase than a 5-character random string. Notice that the example is really assuming that we do this random process for picking passwords, i.e. we run a computer program that takes a list of 500 words and (using good randomness!) spits out a sequence of 4 random words.

Also notice that both of these examples assumed that the attacker knows your strategy. If the attacker is first going to try all 4-word passphrases, and then all 5-character strings, then you would rather have a short random string because it will take longer for that attacker to guess. But since you don't know what the attacker knows, you're best off assuming they know what type of passwords you use, but they don't know which one you picked. And by "type" of password, I really mean a method of generating that password, like uniformly random 5-character strings. Thinking about this method, as we did above, tells you how random or hard-to-guess it is.


If NP $\neq$ Co-NP then is P $\neq$ NP Does the proof of the widely believed result P $\neq$ NP depend on the proof of NP $\neq$ Co-NP ?

Only in one direction. As $\mathsf{P}=\text{co-}\mathsf{P}$, if $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ then we would know that $\mathsf{P}\neq\mathsf{NP}$. However the reverse implication doesn't hold. If $\mathsf{P}\neq\mathsf{NP}$ then it's possible that either $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ or $\mathsf{NP}=\text{co-}\mathsf{NP}$.


How can I prove that a cryptography algorithm is a pseudo-random number generator? I have read about cryptography prgs.
If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not?

Is there some principles I have to be based on while proving prgs?

We don't know how to prove that a cryptographic PRNG exists. There are some candidate constructions, but they have not been proved to work. There are some results of the form "if X exists then so does a cryptographic PRNG", where X is some other cryptographic primitive, and the PRNG can be constructed explicitly from X. However, none of these other cryptographic primitives are known to exist. A particularly intriguing open question is to construct such a primitive which works merely under the assumption that P differs from NP.

On the other hand, proving that a generator is not a PRNG is much easier.  You just need to give a distinguisher which has a non-negligible advantage in comparing the output of the generator to truly random output (as in the definition of a cryptographic PRNG).


Modified paths Counting in a Rectangle I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is:

  We are given K Rectangles. The dimensions of $x$-th Rectangle is ($N_x \times M_x$), where $1\leq x \leq K$.
  From each rectangle $x$ , Alice Cuts  a rect. of dimension ($P_x \times Q_x$), where $1 \leq x \leq K$ ,
  from the Top-Right Corner and trashes the cut portion.

  Initially Alice placed a robot, at the top left corner of each rectangle. He is very interested to find the number of ways, each robot can reach the bottom-right corner (target) using the following rules:

  The robot can only move 1 unit right* or the robot can only move 1 unit downward.
  The robot cannot move upward, can't move even left and can't move even diagonally.
  The robot can move on rectangle boundary.

  The number of ways can be very large. Thus, Answer = (Number of ways) mod 10^9+7.

Constraints is very large:

1<=K<=10
2<=(Nx,Mx)<=5*10^5
1<=Px<Nx
1<=Qx<Mx

The Time Limit is just 1 second.

Example:

K=1

N1=2 M1=2

P1=1 Q1=1

Answer: 5 ways

I had solved the easier version of this problem (Using Pascal triangle + Combinatorics), when no portion of rectangle is cut/removed. But I don't know how to solve the above modified problem, where a small rectangle is cut from top-right Corner of the original rectangle.

As mentioned in the comments, DP is a perfectly valid solution to the problem. If the numbers are too large to calculate directly the number of solutions, then you can take things mod 10^9 + 7 during intermediate steps, too. This will work out because $(a \% b + c \% b) \% b = (a + c) \% b$ (for positive numbers or programming languages that implement negative mod correctly such as Python.

For a more elegant approach, you can calculate directly using more combinatorics. You know the total number of paths in the rectangle before part of it was removed, so it suffices to count the number of paths that went through the removed portion. To do this, take a diagonal from the bottom left of each removed rectangle up and to the right until you reach the border, Any path that goes in the removed portion must hit this diagonal, so if you sum the number of paths there are through each spot on the diagonal, you know how many paths to remove from your total. To count the number of paths that go through a square, count the number of paths to that square and multiply by the number of paths from there to the finish.

A fancier version of this approach is to count directly the paths that avoid the removed portion. To do this, take a diagonal from the corner of the removed rectangle (but not including it) down and to the left until you reach the border. A path avoids the removed rectangle if and only if it goes through this diagonal, so you can sum the number of paths through each location on this diagonal. Again, multiply the number of paths to a point by the number of paths from that point.


Is the language $a^nwa^n$ regular? The given description of language is:

  $\Sigma=\{a,b\}$ and $L=\{a^nwa^n:n\geq 1,w\in\Sigma^*\}$

I felt its regular as we can always interpret $aabaa$ in string $aaabaaa$ as $w$. That is we can always interpret $a^n(a+b)^*a^n$ as $a(a+b)^*a$. So isnt it correct to call this language regular. The book calls it not regular without any explanation. So I was just confused, what is correct.

Your language is regular, since it is identical to $a\Sigma^*a$.

Indeed, by definition of $L$, every word of the form $a\Sigma^*a$ is in $L$ (take $n = 1$). Conversely, every word in $L$ starts and ends with $a$ (and is of length at least 2), and so is of the form $a\Sigma^*a$.


Finding the mistake(s) within this "proof" of NP being closed for complement For my classes in theoretical computer science the following proof must be shown to be wrong. However, this is the first time I am attempting myself at this topic, so I would be thankful for some help:

Lemma:
If $L \in NP $, then $ \bar{L} \in NP $
Proof:

Let N be a non-deterministic Turing machine, which accepts L in polynomial time.

Swap all final states of $N$ with non-final states and vice-versa.

This new Turing machine $N'$ does now accept $\bar{L}$ in polynomial time.

Therefore $\bar{L} \in NP$

I have doubts that simply swapping non-final and final states within $N$ will produce a $N'$ with the proposed properties, but how can I show this?

You just need to show that swapping final and non-final states doesn't complement the language accepted by an NTM, e.g., by showing that, for at least one NTM $N$ (which you can construct to have whatever properties you need), there is a  string that is accepted by both $N$ and $N'$, or rejected by both.


Is the Tomasi-Kanade factorization still commonly used as a modern computer vision technique? My understanding is that, in very rough terms, the Tomasi-Kanade algorithm published in 1992 describes a way to reconstruct the 3D structure of an object from multiple images of that object, given that you have a reliable method of identifying important structural features from the 2D images.

A lack of general information on the topic has prompted me to ask this question: is this method deployed in any recent computer vision systems? Has it been followed up by other methods? Finally, if anyone would like to suggest any resources containing background information that are helpful in digesting the paper, please do. Despite being familiar with the mathematics, I had a hard time making any sense of it.

The Tomasi-Kanade algorithm is probably not used too much these days, though it is an important algorithm that provides a lot of insights and opens interesting avenues of research.  I would say that the main drawback of the algorithm is not that it assumes an orthographic camera, but that it requires a full data-matrix, in which all points are visible in every view.  This is usually not realistic in practice.
The most significant step to address the first issue was the Sturm-Triggs extension of the algorithm to true perspective camerad (i.e. the pinhole camera model).  There were several follow-ups to this, trying to improve on the original method, including papers by Shyjan Mahmood, John Oliensis and others, to a point where the algorithm works well for the perspective model, as long as points are visible in all views.
The situation where there are gaps in the data is addressed by the research topic of low-rank matrix factorization with missing or noisy data.  Unlike the low-rank factorization of a full data matrix, where a least-squares solution is available using SVD (as in the original Tomasi-Kanade algorithm) low-rank factorization of a matrix with holes, or per-entry weights, is NP hard.  Nevertheless, various methods of trying to do this have been proposed, and a good place to look at this is the paper "Damped Newton Factorization for matrix factorization ..." by Buchanan and Fitzgibbon.  This discusses and compares various methods.
Essentially the same sort of algorithm is used for dynamic structure and motion, or multi-object structure and motion.  A good place to start looking into that is the work of Rene Vidal, who has looked at these problems in great depth.


Maintaining data structure with two operations I was trying to implement data structure over set of rectangles that can perform two types of operations.

Update operation, add new rectangle with sides parallel to x and y axis and positive coordinates to the set.
Query operation, for some rectangle check if there is some rectangle intersecting with this rectangle.

I don't have big knowledge of data structures so I was thinking if you could give me some hints how to start approach this problem.

Thanks in advance.

You might want to look into R-trees (described in detail here) or a similar tree data structure for spatial indexing.


Why do we proof the halting problem with turing machines? It can be shown that Turing machines, μ-recursive functions and reasonable programming languages can compute/decide the same problems. I wonder why we then still proof the halting problem with Turing machines.
Isn't it much easier to argue that the function halts below cannot exist in e.g. python since then I would be able to write the following program which is a contradiction.
def halts(source):
  ...

if __name__ == "__main__":
  this_file = open(__file__)
  if halts(this_file.read()):
    while True:
      pass
  else:
    return 1

Why is this proof not as good as the TM diagonal argument?
Edit: I read https://cs.stackexchange.com/a/94235/119946

OK, fine. This proves that the halting problem can't be solved for
code written in any programming language that has a
get_source_code_of_current_function() API. However, my favorite
programming language doesn't have such an API. So, this proof doesn't
prove anything about my favorite programming language -- perhaps the
halting problem is solvable for my language, who knows? Similarly,
Turing machines don't have such an API, so this doesn't prove that the
halting problem for Turing machines is undecidable.

I mean by that argument I can say the TM proofs only shows that the halting problem cannot be decided by Turing machines, but does not show anything about python. Isn't the crucial part, that (as I wrote) TM and modern programming languages can compute/decide the same problems? If one can decide the halting problem, then all other can do so as well and vice versa.

You could totally do that, but there are some consequences it's worth being aware of.

TM proofs only show difficulty of the halting problem for TMs, but here's a crucial thing that you might be overlooking: it is easy to implement a simulator of a TM in any language of one's choice.  That can probably be done in a few dozen lines of code and it is conceptually straightforward.  This lets us very easily see that the halting problem is also hard in those other languages, too.
The same is not true for Python.  You can't write a Python interpreter in a few dozen lines of code.

Let me try it another way.
Some languages don't have a __file__ global variable or anything with similar semantics.  That makes it unclear whether your result applies to other languages.
Sure, we could try to write down a reduction.  In some other language, we could build a Python interpreter that supports __file__.  But that's not a trivial exercise!  We might need to implement a filesystem, library functions that interact with the filesystem, a parser for Python code, an interpreter for Python code, and so on.  Nothing you can code up in a few hours, and it's not trivial to construct such a reduction.

Now, sure, your argument does work, so it's just a matter of taste which you prefer.  I am showing you some reasons why someone might prefer the TM proof.  If you prefer the Python proof, that's fine.  That's your choice. I just want you to be aware of the implications of your choice, and for you to understand all of the steps of reasoning that you have to go through, if you want to use it to draw conclusions about other programming languages.  Arguably your choice makes some parts of the reasoning easier, and some parts (the application to other programming languages) harder.


How does random number probabilities work in distributed systems? Let's say I have a code which does coin toss at 25% win probability.

If I run this code n number of times in the same system it will yield ~25% win.
If I run this code on n devices (once each) will the result be ~25%.

n = very large number.
Are my assertions right?
Edit:My key doubt was, since computers use pseudo random numbers (which are based on a seed), will this affect this assertion (especially #2)

Yes - this is a consequence of the Law of Large Numbers.  https://en.wikipedia.org/wiki/Law_of_large_numbers
Yes - it still holds for pseudorandom number generators if they are any good.
Seed each PRNG independently.


Difference between bit times and milli seconds The propagation delay between two links is 200 bit time .....i want to know what is the difference between 200 bit time and 200 mill seconds

The propagation delay is time it takes to transfer one bit from sender to receiver.
200 ms would be such time, for Bit Times it is the duration of given bits in the medium, the first bit of a header reaches the receiver before the last bit was transmitted by the source (here also given 200).


Priority queue for partially ordered priorities with infima I have a some objects with priority that is compound type and is only partially ordered. I need to select the objects in order of this priority (i.e. yield minimal item each time). But rather than arbitrarily completing the order, I would prefer if the queue was stable in a sense that if there is more than one minimal element, it should return the oldest first.

Is there any heap data structure that would work with partial ordering? Or a modification of regular priority queue to work with it? Common choice for the algorithm I need is simple binary or 4-ary heap, but that does not work with partial ordering.

The priority values support:

Partial ordering using operation $\preccurlyeq$. It's partial ordering, so it's possible that $a \preccurlyeq b$ is false and $b \preccurlyeq a$ is also false. I write $a \not\lesseqgtr b$ in that case.
Finding infima (glb) and suprema (lub). $\inf(x_i)$ is the maximal $y$ such that $y \preccurlyeq x_i$. Calculating the infimum of $n$ values takes $O(n)$ time. Infimum (and supremum) of every set exists.
A linear extension for the partial ordering could be defined. Using it for the priority queue is the easy way out as the algorithm does work that way. But the order affects performance and the order of insertion looks like it should be best in avoiding worst cases.

Additionally the algorithm that I want to use this in needs to know infimum of all priorities in the queue.

The priorities have some real-world meaning, but are subject to change, so it does not seem viable to rely on other properties they could have.

Note: Binary heaps don't work with partial ordering. Assume a binary heap with $a$, $b$ and $c$, where $a \preccurlyeq c$ and $a \not\lesseqgtr b$ and $a \not\lesseqgtr c$. They are positioned in that order, so

     a (0)
   /   \
 b (1)   c (2)

now d is inserted. Next free position is 3, the left child of $b$, so we get

        a (0)
      /   \
    b (1)   c (2)
  /
d (3)

If $d \preccurlyeq a$ (which implies $d \preccurlyeq c$ from transitivity, but does not say anything about $d$ and $b$) and $d \not\lesseqgtr b$, then $d$ does not get swapped with $b$, because it's not less. But it actually is less than $a$, but it's not compared with it, so now the main heap invariant does not hold; top is not minimal.

I suspect a forest of heaps somewhat in style of binomial heap could be made to work.  Basically it's important to always compare new values with root and only link together comparable elements. It would make the trees in the forest randomly sized and thus make the complexity dependent on number of mutually incomparable sets in the heap. I somewhat suspect the complexity can't be fixed (we have to keep comparing until we hit a comparable element) I might have missed something, so I am leaving this open.

Note: The ordering is partial and while there are ways to define a linear extensions for it, adding a timestamp and using it as secondary criterion is not one of them. Suppose we assigned the timestamp $t(a)$ for each $a$ and defined the ordering $\preccurlyeq'$ as $a \preccurlyeq' b$ iff $a \preccurlyeq b$ or
($b \not\preccurlyeq a$ and $t(a) \le t(b)$.
Then suppose we have distinct $a$, $b$, $c$, such that $t(a) \le t(b) \le t(c)$ and $c \le a$. Then $a \preccurlyeq' b$ and $b \preccurlyeq' c$, but $c \preccurlyeq' a$, so the relation is not transitive and therefore is not an ordering at all. This kind of extending only works for weak orderings, but not partial ones.

Edit: I realized that not only is infimum of any set defined, but I actually need to be able to get infimum of elements currently in the queue efficiently. So I am now contemplating whether adding special nodes containing infima of subtrees to some common heap structure would help.

Although the exact problem posed in the original question does seem to be difficult (and I would be interested in a solution to that problem, especially the infima finding part). I just wanted to note that if the partially ordered set indeed consists of vectors using a product order, and if it is sufficient to just have the guarantee that the priority queue returns the values in an order that is "compatible" with the partial order (that is, smaller elements are always returned before larger elements), then there is a fairly easy way to do it.

The idea is essentially to find a topological ordering of the partially ordered set. That is, a total order '$\le_T$' such that $\mathbf{a}\le\mathbf{b}\implies \mathbf{a}\le_T\mathbf{b}$. For vectors using a product order, this is fairly easy: just use a lexicographical order '$\le_S$', where the first "component" is the sum of all the components used for the product order (the rest of the components are essentially arbitrary, so you could also stick to a weak order). We can then see that
$$\mathbf{a}<\mathbf{b}\implies \forall_i(a_i\le b_i)\text{ and }\exists_i(a_i<b_i)\implies(\sum_i a_i)<(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b}$$
and
$$\mathbf{a}=\mathbf{b}\implies \forall_i(a_i=b_i)\implies(\sum_i a_i)=(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b},$$
and thus that $\mathbf{a}\le\mathbf{b}\implies\mathbf{a}\le_S\mathbf{b}$. We can thus use this order with a priority queue and be sure that smaller elements (in the product order) will always be extracted before larger elements.


Computational complexity theory books I recently attended a lecture on an introduction to computation complexity and I am looking to find out more, I haven't studied computer science or discrete mathmateics at university and I was wondering if anyone could recommend any relatively simple books or reading material that could help me understand the topic more

Classic texts on computational complexity include Hopcroft & Ullman's text {1} and Sipser's text {2}.  With patience, they should both be accessible.

{1} Hopcroft, John E., R. Motwani, and J. D. Ullman. "Introduction to Automata Thoery, Language, and Computation (2nd edition)". Addison-Wesley, Reading (2001).

{2} Sipser, Michael. Introduction to the Theory of Computation. Cengage Learning, 2012.


Is regular expression syntax regular? Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular?

My guess is that the original syntax (concat, | and *) is, but the Perl-style syntax is not (backtracking). As the newer syntax recognises non regular languages they must also generate non regular languages. If a DFA could recognise a non regular language then there would be a problem...

Both "original syntax" and PCRE's syntax is not regular. You need parenthesis to override operator precedence, which puts your syntax language into the territory of context free languages.


CLRS Rod Cutting Inductive proof I'd like to preface this question by saying that it is not a homework question. However, it is a question regarding the course material. In the rod-cutting example an equation is presented to determine the maximum possible revenue attainable for give rod length:

$r_{n} = max(p_{i} + r_{n-i})$ (15.2)

I'm trying to prove by induction that this equation does in-fact output the optimal revenue.

It's stated that, "A simple
induction on n proves that this answer is equal to the desired answer $r_{ n}$, using
equation. 15.2"

While not required, I'm attempting to perform this induction and I'm stuck on the inductive step. Here is what I have so far:

Base Case n = 3, where $r_{n}$ represents the maximum revenue attainable from a rod of length $n$ (note the following references a price list p, which corresponds to the price of a rod for a given length, and a list r which corresponds to the maximum revenue given a rod length).

$i = 1, p_{1} + r_{3-1} = 6 $

$i = 2, p_{2} + r_{3-2} = 6 $

$i = 3, p_{3} + r_{3-3} = 8 $

Assume,
$r_{k} = max(p_{i} + r_{k-i})$

Inductive Step,
$r_{k+1} = max(p_{i} + r_{(k+1)-i})$

I'm am unclear on how to proceed from here. I realize that the optimal revenue for a give rod length is defined in terms the optimal revenue for smaller rod lengths, which I believe means this problem displays optimal sub-structure. But i'm unclear on how to proceed. I'm prefer to not be given an answer but rather some direction.

First, be more precise in your writing. What does $\max$ range over? What is $k$ in the inductive hypothesis and step? What is the actual statement in the induction hypothesis?

In the step, you want to establish that $r_n = \dots$ is optimal assuming all $r_k$ as computed by the proposed formula for $k \leq n$ are optimal, for some fixed $n \geq 3$.

One way you typically do this is by contradiction. Assume (in addition to IH) that $\max \dots$ were not optimal. Derive that the chosen $r_k$ is not optimal either, then, which is in contradiction with the IH.


Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$ I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^*$ and a regular grammar generating $\Sigma^*$.. I got the examples here from Sipser. Let $ALL_{CFG}$ refer to the language that a given CFG generates $\Sigma^*$, and let $ALL_{REX}$ refer to the language that a given regular expression generates $\Sigma^*$ (and since for each regular expression there is a regular grammar, we can also say that the equivalent regular grammar generates $\Sigma^*$).
From what I got, we have:

$ALL_{CFG}$ is not decidable, it is also not Turing-recognizable. Let $\overline{A_{TM}}$ refer to the language that a TM $M$ does not accept input word $w$. We can reduce $\overline{A_{TM}}$ to $ALL_{CFG}$ in polynomial time using computation histories. The reduction constructs a CFG which generates all possible words where: 1) the first characters do not match $w$,  2) the last characters do not match accepting configurations, and 3) characters do not match valid transitions of $M$'s configurations. Thus, $A_{TM}$ does not accept $w$ iff the CFG generates $\Sigma^*$ (i.e. there are no accepting computation histories). Since the reduction maps $\overline{A_{TM}}$ to $ALL_{CFG}$, and $\overline{A_{TM}}$ is not Turing-recognizable, $ALL_{CFG}$ is not Turing-recognizable.

$ALL_{REX}$ is decidable since it is decidable if a finite automaton accepts $\Sigma^*$. However, the acceptance problem for any regular language $R$ can be polynomially reduced to the language $ALL_{REX} - f(R_M)$, where $R_M$ is a TM that decides $R$, and $f(R_M)$ is a similar reduction of computation histories as outlined above.  In more detail, $f(R_M)$ is the regular grammar that generates all possible words where  1) the first characters do not match $w$,  2) the last characters do not match rejecting configurations, and 3) characters do not match valid transitions of $R_M$'s configurations. The decider for $ALL_{REX} - f(R_M)$ checks if it is empty (which means that $f(R_M)$ is equal to $\Sigma^*$). If empty, then there are no rejecting computation histories and $w \in R$. (In Sipser, he used something like this to show EXPSPACE-completeness for $ALL_{REX} - f(R_M)$)

I would like to ask:

From above, both regular grammars and CFG could generate computation histories of a TM, and both could generate $\Sigma^*$. But what is it with the fundamental power of the CFG's grammar that makes it valid to reduce $\overline{A_{TM}}$ to $ALL_{CFG}$, but it is not possible for $\overline{A_{TM}}$ to be reduced to $ALL_{REX} - f(A_{TM})$ ? I know that we cannot reduce $\overline{A_{TM}}$ to $ALL_{REX} - f(A_{TM})$ since $ALL_{REX} - f(A_{TM})$ is decidable, while $\overline{A_{TM}}$ is not Turing-recognizable... But I would like to understand this in terms of the difference in generating power between CFG's and regular grammars via their rules.

For instance, from what I read, CFG's permit the rules $A \rightarrow BC$, where $B$ and $C$ are strings of variables and terminals. On the other hand, regular grammars only permit rules in the form of $A \rightarrow aB$, where $a$ is a terminal. I would like to ask: why does incorporating rules of the form $A \rightarrow BC$ to a grammar, give it enough generating power such that it is already valid to reduce $\overline{A_{TM}}$ to the grammar (i.e. to the CFG).

Your summary of the proof of undecidability is not accurate.  Your specification of $\overline{A_{TM}}$ is not correct.

For a reasonable exposition of the proof, see https://liacs.leidenuniv.nl/~hoogeboomhj/second/codingcomputations.pdf particularly the beginning of Section 1 and Section 3.

The intuition is not easy to convey, as the proof is not entirely trivial.  But here is the core fact.  Let $v,w$ be two configurations of a Turing machine.  Write $n(v)$ to be the next configuration of the Turing machine after a single step of computation, if you start at configuration $v$.  Define the language

$$L = \{v \# w^R \mid n(v) \ne w\}.$$

Then the key fact is that $L$ is context-free.  This takes some proof; proving that is a key step in the proof.  However, that's the answer to your question: $L$ is context-free but not regular.  As a result, we can reduce the halting problem to $ALL_{CFG}$ but not to $ALL_{REX}$.

I have skipped many steps to give you an overview of the main idea.  You will need to read the full proof to fill in the details.  I suggest that you next read and understand the proof, with this perspective in mind, and then revisit what I've written here.  Hopefully that will help you understand why the proof holds for context-free languages but would fail for regular languages.


How to solve the following left recursion? A common left recursion:

A -> Aa | B

can be solve by transforming it into:

A  -> BA'
A' -> aA' | E

However, I face another similar yet different left recursion when I'm writing my compiler:

A -> (A|B) a

So, my question is, how to solve such left recursion?

Rewriting (A|B) a as Aa | Ba allows you to apply the solution you already have (with Ba instead of B).


What is the difference between AM and IP Intro

I am trying to understand how those two models of interactive proof are different. I understand that

$\text{AM}$ relies on public coins (the prover knows the random bits used by the verifier)
$\text{IP}$ relies on private coins (the prover does not)

And here are some common results in those classes

Goldwasser and Sipser showed that if we allow a polynomial number of rounds $Q$, we have that $\text{IP}[Q] \subseteq \text{AM}[Q+2]$.
It has also been shown that if we allow a constant number of rounds $k$ in $\text{AM}$, we have that $\text{AM}[k] \subseteq \text{AM}[2]$

This seems to imply that if we limit $\text{IP}$ to a constant number of round $k$, we also have that $\text{IP}[k] \subseteq \text{AM}[k+2] \subseteq \text{AM}[2]$, and that these classes are very similar.

The thing that bugs me

But then, why do we have the huge difference that
$\text{IP} = \text{PSPACE}$, while $\text{AM} \subseteq \prod_2^{\text{P}}$?

(see the Complexity Zoo on AM and IP)

Question(s)

Why the difference? My assumption is that there is a convention to use $\text{AM}$ to speak about $\text{AM}[k]$, private coin, constant $k$ rounds protocols, and $\text{IP}$ to speak about $\text{IP}[\text{poly}]$ public coin, polynomial rounds protocols. Is it correct?
Do the results holds if we swap the classes? $\text{IP}[k] \subseteq \prod_2^{\text{P}}$ does, but what about $\text{AM}[\text{poly}] = \text{PSPACE}$?
As an additional question, we do know that a constant number of messages $k$ can be condensed into only two messages. Is there a similar result for a polynomial number of messages?

$AM$ is defined to be $AM[2]$, i.e. languages with 2-rounds Arthur-Merlin protocol, which is equal to $AM[k]$ for any constant $k$.

Two extra rounds are required to overcome the fact that the coins are public, i.e.

$IP[k]\subseteq AM[k+2]$ for any $k$ , constant or not, as stated in complexity zoo.

This means that $IP[poly]=AM[poly]=PSPACE$ (which answers your second question).

If $IP$ can be limited to a constant number of rounds (rather than polynomial), then we would have $PSPACE\subseteq IP[k]\subseteq \Pi^p_2$, and the hierarchy collapses to the second level, since $PH\subseteq PSPACE$.


Tool/app for learning category theory? Being a programmer I appreciate the errors given by a compiler for a programming language and come to rely on the compiler's error as a safety net.

In learning category theory I would like to have some tool that also acted as a safety net letting me experiment with diagrams and pointing out my mistakes when I make one. Does such a tool/app exist?

I know this is more of a math question, but I am asking here because I am looking for an answer from those with and understanding for computer science.

There are at least three encodings of (aspects of) Category Theory in Coq. Approaches using a proof assistant guarantee correctness by design, though I don't know whether they will enhance understand. You'll then have both the proof assistant and Category Theory to learn.

If you want a reasonably introductory, computer science-oriented book, it's hard to beat Categories and Computer Science by R. F. C. Walters. His examples are mostly about data types and automata, rather than programming languages and lambdas. Conceptual Mathematics by Lawvere and Schanuel is also quite digestable.

One approach combining these two is to use this Coq formalisation with Steve Awodey’s Book. The formalisation covers closely what is in the book. There's also a blog post about it.

That said, Category Theory is tough and its relationship with  programming quickly becomes quite distant, and so one needs to rely on one's mathematical background (which is now getting on to be 20 years old).