Has the graph isomorphism problem been solved? Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not sophisticated enough to follow the reasoning in the paper.

I do have my own very rough attempt at a polynomial time algorithm without anything like proof, but I'd like to know whether or not this problem has been successfully tackled before proceeding.

So, is the graph isomorphism problem solved?

No.  That paper appears to be flawed.  The flaw was explained in a comment by Tracy Hall on MathOverflow.  A follow-up comment claims that the author later realized there is a flaw in his algorithm.

As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed.  When it comes to results on famous open problems (e.g., P vs NP, graph isomorphism, etc.), I recommend looking to published literature in reputable peer-reviewed conferences and journals -- peer review is not perfect, but peer-reviewed papers have a much higher likelihood of being correct.


No nonfinal states in NFA I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$.

What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can there be an NFA with no non-final states whose minimal NFA has some non-final state?

Oh , no nonfinal states means all are final states. So DFA - all final states means every string gets accepted. So language is $\sum^*$. For NFA, it need not be $\sum^*$. Please correct me if i am wrong here. Other case --> If there are no final states(all non-final states) means in DFA, language accepted is empty language. In case of NFA with no final state means empty language right?

Imagine an NFA with a single state, which is final/accepting. It has no edges.

This NFA accepts the language $\{\varepsilon\}$—that is, only the empty string. If it is given a non-empty string, it looks for appropriate edges leading away from the starting state, finds none, and fails.


Construct a deterministic finite automation The question asks to:

  construct a DFA which accepts exactly $\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}+1$ many members of $\{0, 1\}^n$ for every n.

I have no idea where to start to constructing the DFA, could you give some directions?
By the way, how many states should this DFA have?

Hint: Here is a regular language which "accepts" exactly $n$ members of $\{0,1\}^n$ for every $n$: $0^* 1 0^*$. For example, for $n=4$ we have the strings $0001,0010,0100,1000$. The minimal DFA for this language contains three states.


Time complexity of a triple nested for loop for ThreeSum problem I am new to Algorithms and am currently confused about the running time of the ThreeSum program. If we look at ThreeSum's count function:

public static int count(int[] a) {
  int N     = a.length;
  int count = 0;

  for (int i = 0; i < N; i++) <-- A
    for (int j = i + 1; j < N; j++) <-- B
      for (int k = j + 1; k < N; k++) <-- C
        // check each triple
        if (a[i] + a[j] + a[k] == 0)
          count++;
  // loop i = 0; j = i+1; k = j+1 so that we get each triple just once

  return count;
  }

I understand that int N = a.length means that its frequency is 1 as the statement only runs once and that count++'s frequency is x as it depends on input however with nested for loops. I understand that say A's frequency is $N$ (as it is repeated N times) but then I get a bit confused.

It seems to be that for each nested loop, the other loop has to run which makes sense so B's frequency is $N^2$ but then in the book it says that B's frequency is $N^2/2$ and C is $N^3/6$ (where I would have assumed $N^2$ and $N^3$) where is the "$/2$" and "$/6$" coming from?

Any help is appreciated, thanks. Sorry for the lengthy question!

The second loop runs only on $j > i$. Only (roughly) half of the pairs $(i,j)$ between $0$ and $N-1$ satisfy $j > i$. Similarly, the third loop runs only on $k > j > i$, and only (roughly) $1/3!$ of the triples $(i,j,k)$ satisfy that condition.

If you want to be more accurate, $B$ runs this many times
$$ \sum_{i=0}^{N-1} (N-i-1) = \sum_{i=0}^{N-1} i = \frac{i(i-1)}{2}. $$
I'll leave you the calculation for $C$.


What is complement of Context-free languages? I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I can say that complement of CFL is included in P(right?). There is still a question whether complement of CFL is proper subset of P or the whole P. I would appreciate any ideas on how to show that complement of CFL is the whole P(if that's the case of course).

One can understand your question in two ways, according to the definition of "the complement of CFL".

case A: Complement of CFL is the class of all the languages that are not in CFL.  Formally, $$\overline{CFL} = \{ L \mid L\notin CFL\}.$$
In that case, $\overline{CFL}$ is way bigger than $P$, it even has languages that are not in $R$, etc.
But maybe that's not what you meant.

case B: Define the complement-CFL class as $$co{CFL} = \{ \bar{L} \mid L \in CFL\},$$
in words, the set of all languages $L$, such that $L$'s complement is context free.

In that case, what you wrote makes sense:
$CFL \subsetneq P$  (by the CYK algorithm), and also $co{CFL} \subseteq P$ (run the same algorithm, output the opposite answer), and since $CFL \neq co{CFL}$,
then it should be immediate that $co{CFL}\subsetneq P$, right?


How can a quadratic algorithm be faster than a linearithmic one? I have to solve the following problem:

  Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if $n<100$, the $O(n^2)$ time algorithm runs faster, and only when $n \geq 100$ is the $O(n\log n)$ time one better. Explain how this is possible.

Watching the Big O definition I can see that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $|f(x)|\leq C|g(x)|$ whenever $x>k$.
Also, I know that $O(n^2)$ comes from a polynomial of degree 2 that might have a coefficient and other terms of lower degree.

I do not find how to relate this facts in order to make a conclusion although I suspect that constants $C$ and $k$ could play an important role in such a conclusion.

I will very much appreciate any clue so I can get a better idea about how to formulate an answer.

All you know is that an $O(n\log n)$ algorithm is eventually (a lot) faster than an $O(n^2)$ algorithm, but for any specific value of $n$, you can't say anything. Indeed, the asymptotic growth of the function doesn't depend on its value on $n < 100$. This means that if $f(n) = O(n^2)$ then for all $c_1,\ldots,c_{99}$, the following function is also $O(n^2)$:
$$
f'(n) = \begin{cases} c_n & \text{if } n < 100, \\ f(n) & \text{if } n \geq 100. \end{cases}
$$
So asymptotic notation is completely uninformative regarding the performance of algorithms on specific values of $n$.

You could say that functions such as $f'(n)$ are artificial and never really occur in practice. This is not quite true (you can hard-code some auxiliary information for small $n$, for example), but even if you consider "natural" functions, asymptotic notation doesn't help you to determine anything other than asymptotics: consider for example $n^2$ against $10^{100} n\log n$ (such examples definitely happen in practice, for example in fast matrix multiplication).


Recurrence relation for the number of "references" to two mutually recursive function I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line scheduling
(Note: Assembly line scheduling or dynamic programming is not required to answer to the question though, it is just for information so that it shall help relating the context).

$(1),(2),(3)$ are three relations as shown.
$$f_{1}[j] = \begin{cases}
       e_1+a_{1,1} &\quad\text{if } j=1\\
       \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad\text{if }  j\geq2\\
\end{cases}\tag 1$$
Symmetrically,
$$f_{2}[j] = \begin{cases}
       e_2+a_{2,1} &\quad\text{if } j=1\\
       \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad\text{if } j\geq2\\
\end{cases}\tag 2$$
(where $e_i,a_{i,j},t_{2,j-1}$ are constants for $i=1,2$ and $j=1,2,3,...,n$)
$$f^\star=\min(f_1[n]+x_1,f_2[n]+x_2)\tag 3$$

The text tries to find the recurrence relation of the number of times $f_i[j]$ ($i=1,2$ and $j=1,2,3,...,n$) is referenced if we write a mutual recursive code for $f_1[j]$ and $f_2[j]$. Let $r_i(j)$ denote the number of times $f_i[j]$ is referenced.
They say that,
From $(3)$,
$$r_1(n)=r_2(n)=1.\tag4$$
From $(1)$ and $(2)$,
$$r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1)\tag 5$$

I could not quite understand how the relations of $(4)$ and $(5)$ are obtained from the three corresponding relations. (directly without any proof, is it so trivial?)
Thought I could make out intuitively that as there is only one place where $f_1[n]$ and $f_2[n]$ are called, which is in $f^\star$, so probably in $(4)$ we get the required relation.
But as I had not encountered such concept before I do not quite know how to proceed. I would be grateful if someone guides me with the mathematical prove of the derivation as well as the intuition.
[Note: However an alternative to mathematical induction shall be more helpful as it is a mechanical cookbook method without giving much insight into the problem though (but if in case there is no other way out, then even mathematical induction is appreciated if I can get the intuition behind the proof)].

It looks like that you are exhausted after a long and tiring journey that you have taken to comprehend the setup of assembly-line scheduling, the step 1 on the structure of the fastest way through the factory and the step 2 on a recursive solution.
It is straightforward to understand formula (4) and (5).
When we program a recursion solution using formula (1), (2) and (3), the left-hand side of each formula is transformed to the signature of its implementing method while the right-hand side is transformed to the body of the method.
For example, (3) is transformed to pseudo-Python code
def f_star(n):
    return min(f_1(n) + x_1, f_2(n) + x_2)

So, when $f^\star$ is referenced, i.e., when f_star is called, $f_1[n]$ and $f_2[n]$ will be referenced, i.e., f_1(n) and f_2(n) will be called, where f_1(.) and f_2(.) will be explained below. Since we will call f_star(n) once, which is enough to get the value of $f^\star$, we get formula (4).
Formula (1) is transformed to pseudo-Python code
def f_1(j):
    if j == 1:
        return e[1] + a[1][1]
    else:
        return min(f_1(j - 1) + a[1][j], f_2(j - 1) + t[2][j - 1] + a[1][j])

So whenever $f_1[j]$ is referenced, i.e., when $f_1(j)$ is called, $f_1[j-1]$ will be referenced exactly one, i.e., f_1(j-1) will be called exactly once.
Similarly, whenever $f_2[j]$ is referenced, $f_1[j-1]$ will be referenced exactly once. (You can write the function f_2(j) explicitly yourself to check it out.)
Note that any reference to $f_1[j-1]$ must be brought by either a reference to $f_1[j]$ or a reference to $f_2[j]$. So we have
$$r_1(j-1) = r_1(j) + r_2(j).$$
Similarly or by symmetry, we also have
$$r_2(j-1) = r_1(j) + r_2(j).$$
Replacing $j$ by $j+1$, we get formula (5).


Why neural nets are split into layers? Why is every artificial neural network layered? Why isn't each node just a separate process?

A neural net will work with any arbitrary topology, as long as it has no cycles. We often use layers because it is easy to implement and because it allows a human to set parameters for how large the net should be, such as "four layers with 5, 6, 7 and 10 nodes, respectively".

I cannot find anything on the web about neural networks that are not organised into layers, but there is nothing principally impossible about them. Here's an idea for a rainy sunday afternoon: implement a neural net as a directed acyclic graph and use an evolutionary algorithm to find a good topology. Compare it to a layered neural net with similar numbers of nodes and edges.


Saving information from reaching definition I am learning about compilers at the moment and in my textbook it is briefly mentioned that UD/DU (Use-Def, Def-Use Chains) a way of saving information from the reaching definition is. It is just said that, when a variable is used, it has a list of the reaching definitions.

The problem that I am having is, that I am not clearly understanding the way this information is being used. How can this help the compiler optimize the code? Are there any other ways of saving (using) this information?

Here are just a few examples:

dead-code elimination,
instruction reordering, and
(implementation of) scoping/shadowing.


Transitive Closure vs Reachability in Graphs I am facing the most curious situation with [my current information of] transitive closure algorithms. Specifically, is what follows not an algorithm for finding the transitive closure of a graph G(V, E) and is the time complexity not O(|V|+|E|):

Use Kosaraju's to compute SCCs (strongly connected components) -- O(|V| + |E|)
Create a DAG from the SCCs as (super)nodes -- O(|V| + |E|)
In a single supernode, reachability of all nodes is the same and equal to the union of the nodes in the containing supernode plus the reachable supernodes in the DAG -- O(|V| + |E|) to compute reachability in the DAG and O(|V| * |V|) total to compute reachability sets for all nodes

These reachability sets do constitute the transitive closure of the graph wholly, right?
But there aren't any O(|V| + |E|) transitive closure algorithms around.
What am I missing?

Your algorithm is known as Purdom's algorithm. There are two versions of transitive closure:

Calculate the transitive closure as a relation. This cannot run in time $O(|V|+|E|)$, since the output could be bigger than that (consider a directed path, for example).
Calculate enough information to be able to answer oracle queries to the transitive closure in $O(1)$. Even in this case, the algorithm doesn't seem to run in time $O(|V|+|E|)$. Hopefully the link would make it clear why.


How page table base register (PTBR) is used to locate the correct frame using Page Number? I was reading about paging in OS , and one of the things I saw was the page table base register (PTBR).
If the CPU generates a logical address (Consists of Page number + Offset) it needs to be mapped to Physical address (Consists of Frame number + Offset).
In the mapping process there must be first a lookup in the Page table of the process to get the Frame corresponding to that page.
Now to get to the page table we need to get the location of the page table of that process in the main memory.
The starting location of the page table is stored in a register called page table base register (PTBR).
Now the page number part of the logical address is added with the value in the PTBR and the corresponding frame is found in the table as the following:

Since the PTBR stores the base physical address of the page table in memory (e.g. 14000), and the logical address contains the page number that the CPU wants to read data from. Now here is my question:

Is the page number part of the logical address is the starting address of the page?

For example: the virtual address is 16 bit and the size of each page is 1KB
page 0 --->starts at virtual address 0
page 1 --->starts at virtual address 1024
page 2 --->Starts at virtual address 2048
and so on ...
So if the CPU wants to read data from page 1, then the page number is "1024" and then this value is added to the value in the PTBR?
OR
The page number itself is added for example:  if the CPU wants to read data from "page 1", then the number "1" represents the Page number value and when it is added to PTBR value? in other way does the CPU deal with page Number or Starting address?
I know this is silly for a lot of you, but it really got me confused because I couldn't find any real example about it.

I'll take x86 32 bits PCs as an example. On 32 bits x86 PCs, the CR3 register is used as the PTBR. The CR3 register contains the 4KB aligned address of the page directory. The page directory contains addresses of the different page tables. The x86 processors have virtual addresses which are separated in 3 parts. The 10 most significant bits are the offset in the page directory, the 10 bits in the middle are the offset in the page table and the 12 last bits (to the right) is the offset in the physical page in RAM. Let's look at an example. Let's take address 0x12345678. This is a 32 bits address which translates in binary to 0001 0010 0011 0100 0101 0110 0111 1000. Now let's look at the different parts of this address.
Page directory offset        Page table offset        Physical page offset
   00 0100 1000                11 0100 0101             0110 0111 1000

So in the end this virtual address will translate to page directory entry 0b0001001000 = 0x72 = 114 decimal, page table entry 0b1101000101 = 0x345 = 837 decimal and the offset in the physical page will be 0b011001111000 = 0x678 = 1656 decimal
Depending on what is the content of each selected entries by this virtual address, the actual physical address can be anywhere in RAM. In this example we have entry 114 in the page directory. If at entry 114 is written 0x1234, the MMU of the CPU will look there for the page table. It will use address 0x1234 as the bottom of the page table and then find entry 837 which could contain 0x12345. So the final physical address translated will be 0x12345 + offset_in_physical_page = 0x12345 + 0x678 = 0x129BD. This will be the final physical address once translated using the example that we have here.
On more modern processors you will have 4 levels of page tables so the virtual address will be split in 5 parts. 4 parts of 9 bits to the left and 1 part of 12 bits. Only 48 bits are used for now with the leftover bits to be used later (once there are more page table levels).


What does "prompt collection" mean in the context of memory management? I often see people assert that reference counting techniques such as shared_ptr in C++ provide prompt collection (e.g. here and here) but I am not sure what exactly is meant by this. Some people tell me that they mean "collects at the earliest possible point" but I think that is not true of scope-based reference counting because it defers collection to the end of scope even if a variable is dead. Therefore, I'm wondering if other people have a different interpretation that may be correct.

Do computer scientists use the term "prompt" in this context and, if so, what do they mean by it?

More concretely, I once studied the behaviour of various OCaml and F# programs and found that they often collect values before they fall out of scope and, therefore, more "promptly" than scope-based reference counting. For example, the following function runs in bounded memory:

let rec loop tmp i =
  if i<=0 then tmp else
    loop (Array.copy (loop (Array.copy tmp) (i-1))) (i-100)

Even though the argument tmp is in scope for the entire body of the function it is collected before even the first recursive call to loop.

EDIT Here is a simpler F# example with a single recursive call and some post-processing to ensure that the call is not in tail position so it cannot be eliminated:

let rec loop tmp i =
  if i<=0 then tmp else
    let tmp = loop (Array.copy tmp) (i-1)
    tmp.[0] <- tmp.[0] + 1
    tmp

Between the copying of the array and the call to loop the argument tmp dies and, indeed, I find that it is garbage collected so this program requires only O(1) space.

Here is the equivalent reference counted C++:

shared_ptr<vector<double> > loop(shared_ptr<vector<double> > tmp, int i) {
    if (i<=0) {
        return tmp;
    } else {
        shared_ptr<vector<double> > tmp1(new vector<double>(*tmp));
        shared_ptr<vector<double> > tmp2 = loop(tmp1, i-1);
        ++(*tmp2)[0];
        return tmp2;
    }
}

Although tmp dies between the creation of tmp1 and the call to loop, scope-based reference counting keeps it allocated until the end of scope. So n recursive calls require O(n) space.

Do computer scientists use the term "prompt" in this context and, if so, what do they mean by it?

What is meant by prompt, is that it is guaranteed to be deleted and more importantly, destructed, when it goes out of scope. The main point of this, is to take advantage of the mainly-C++-ish paradigm of Resource Acquisition Is Initialization.

Look at the following program in pythonish:

def procedure():
  f = open('path')

  ... #use f

def main():
  procedure()
  #f *might* still be alive here, which means it is hogging a file resource

So, languages like python therefore must supply some manual cleanup methods. One is supposed to call f.close() before leaving procedure(). However, this can be error prone, because of early-return (you must remember to close at every return, and remember this when changing code later; it is very cumbersome) and exception safety (what if somewhere before returning, something throws an exception?, then your f.close();return isn't called at all).

The C++ solution to this is very elegant; when things go out of scope, they are guaranteed to call a destructor. The destructor of a resource object will/should clean up the resource. So you have the following code in C++:

void procedure(){
  std::ofstream f("path");
  ... //do stuff with f
  // we *can* call f.close(), but we don't have to, because f::~() (the destructor) will clean it up, and it is guaranteed to be called when going out of scope.
}

The python solution to this is to use the finally exception block like so:

def procedure():
  f = open('path')
  try:
    ... #use f
  finally:
    f.close()
def main():
  procedure()

Alternatively, there is some syntax sugar for some special resource classes (you can add this to any custom class as well) that accomplishes the same thing:

def procedure():
  with open('path') as f:
    ... #use f
  #f.close() is called once out of "scope" of the with; it is essentially the same as the finally block.
def main():
  procedure()

So it is simply two different paradigms; C++'s concept of the "on-the-stack" objects allows self-cleanup, python and most other languages require manual cleanup, but enjoy garbage collection.

Now, the issue is, pointers don't have destructors; they are essentially POD (plain old data). Therefore, if you want to keep an object around longer, you would allocate it on the heap, and save a pointer to it, but you must manually call the destructor (via delete ptr;), but only when you "know" you are done with it. In many situations, it is hard to know when you are done with a pointer, for example, if it is used in many places ("shared ownership"); therefore a reference counter such as shared_ptr can be used, and the underlying objected that is pointed to will be destructed (the destructor will be called) "promptly" when it goes out of scope, ie. when the last user gets rid of the pointer.

  More concretely, I once studied the behaviour of various OCaml and F# programs and found that they often collect values before they fall out of scope and, therefore, more "promptly" than scope-based reference counting.

This is probably not guaranteed though. A garbage collector can decide to clean things up whenever it wants to, they usually don't take resources other than memory into consideration, and AFAIK, never provide any such guarantees. C++, and the finally blocks provide guarantees of resource cleanup.


Bakery algorithm: what is the choosing[] boolean array for? I'm studying the bakery algorithm.

do {
     choosing[i] = true;
     number[i] = max(number[0], number[1], …, number [n – 1])+1;
     choosing[i] = false;
     for (j = 0; j < n; j++) {
         while (choosing[j]); //
         while ((number[j]!= 0) && (number[j],j)<(number[i],i)));
     }
     critical section
     number[i] = 0;
     remainder section
} while (1);

Please help me know what exactly this choosing doing here. I checked this for all conditions that I could generate to understand its use. But it doesn't  seem to be making any difference. Please help me with a case.

choosing[i] is true while number[i] is being updated to be larger than all the other values in the number array — the new ticket value that the thread is taking. In the body of the for loop, the code first waits for choosing[j] to be false, which indicates that thread number j has chosen its ticket for this round. If thread j goes on executing while thread i hasn't entered the critical section yet, then number[i] won't change, so:

If thread j is still in the same round and hasn't finished the critical section yet, then number[j] is the result of a max computation which may or may not have taken the current value of number[i] into account, depending on the interleaving of the execution of threads i and j.
If thread j is in the remainder section then number[j] is 0.
If thread j has begun a new round then its number[j] is the result of a max computation that took the current value of number[i] into account, thus number[j] > number[i].

In the first case, threads i and j are running their for loop concurrently; only one of them will win the (number[j],j)<(number[i],i) comparison and proceed into the critical section, and the other will wait for the winner's number value to become acceptable again. In the second case, thread j is not competing for the critical section. In the third case, thread j has a higher number and will wait in its own for loop while thread i hasn't reset its number[i] value.

The choosing array works around the lack of atomicity in the computation of number[] values. If it was removed, then you could have two threads computing the same value concurrently and each finding that it had the smaller value at the point of testing. This could happen with as little as two threads (I use the notation k.tmpX to designate local storage of the thread k):

initially: number[1] = number[2] = 0

thread 1                                   thread 2
//choosing[1]=true
1.tmp1 = number[1]
1.tmp2 = number[2]
                                           //choosing[2]=true
                                           2.tmp1 = number[1]
                                           2.tmp2 = number[2]
                                           number[2] = max(2.tmp1,2.tmp2)+1 = 1
                                           //choosing[2]=false
                                           //while (choosing[1]) {}
                                           while (number[1]≠0 &&
                                                  (number[1],1)<(number[2],2)) {}
                                           critical section ...
number[1] = max(1.tmp1,1.tmp2)+1 = 1
//choosing[1]=false
//while (choosing[2]) {}
while (number[2]≠0 &&
       (number[2],2)<(number[1],1)) {}
critical section ...
                                           critical section ...

The two threads computed the same ticket number. The bakery algorithm uses the thread number to determine the priority in this case. However, thread 2 decided to  the critical thread while thread 1 was still preparing, whereas thread 1 saw the new ticket number of thread 2 when deciding whether to enter the critical section but had computed its own ticket number based on thread 2's old ticket number. So thread 1 incorrectly entered the critical section.

The choosing array solves this problem by preventing thread 2 from entering the critical section. Since thread 1 is computing its ticket number at the time thread 2 is preparing to enter the critical section, thread 2 will block on while (choosing[1]) {}, after which it will see the updated value of number[1] and allow thread 1 to enter the critical section first, while thread 2 waits on while (number[1]≠0 && (number[1],1)<(number[2],2)) {}.


Solution of CLRS question 4.6-2 I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^j)\right) $

when I searched online, I saw people have solved this as below:

$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^j)\right) $
$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
$T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $
$T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $

I did not understand the following points:

$ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs?
In equation 4, after calculating the summation, how did the subtraction between logs turn to sum?
There is a small o in equation 4, then how can we write theta in equation 5.

The first point seems like a mistake. Find a different solution.

For the second point, $o(f(n))$ often refers to a function whose absolute value is $o(f(n))$. So $-o(f(n))$ and $o(f(n))$ are really the same thing. For example, you can write $n - 1 = n + o(n)$.

For the third point, here is a simpler example: $n + o(n) = \Theta(n)$. You can check that if $|f(n)|/n \to 0$ then $(n + f(n))/n \to 1$, and in particular $n + f(n) = \Theta(n)$.


Difficulty in understanding few steps in the proof: "The class $\mathscr{H}_{p,m}$ of hash functions is universal" I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following excerpt regarding the said proof and the steps where I felt difficulty are marked with $\dagger$ and $\dagger\dagger$ respectively.
Designing a universal class of hash functions
$p$ is a prime number large enough so that every possible key $k$ is in the range $0$ to $p — 1$, inclusive. Let $Z_p$ denote the set $\{0, 1,..., p — 1\}$, and let $Z_p^*$ denote the set $\{1, 2,..., p — 1\}$.Because of the assumption that the size of the universe of keys is greater than the number of slots $m$ in the hash table, we have $p > m$.
We now define the hash function $h_{a,b}$ for any $a \in Z_p^*$ and any $b \in Z_p$ :
$h_{a,b} = ((a.k + b) \mod p) \mod m $.
The family of all such hash functions:
$$\mathscr{H}_{p,m}=\{h_{a,b}: a \in Z_p^* , b \in Z_p\}$$

Theorem: The class $\mathscr{H}_{p,m}$ of hash functions is universal.

Proof:
Consider two distinct keys $k$ and $l$ from $Z_p$, so that $k \neq l$. For a given hash function $h_{a,b}$ we let
$$r = (ak + b) \mod p$$ ,
$$s = (al + b) \mod p $$.
We first note that $r\neq s$. Why? Observe that
$$r — s = a(k — l) (\mod p)$$ .
It follows that $г \neq s$ because $p$ is prime and both $a$ and $(k — l)$ are nonzero modulo $p$, and so their product must also be nonzero modulo $p$
Therefore, during the computation of any $h_{a,b}$ in $\mathscr{H}_{p,m}$, distinct inputs $k$ and $l$ map to distinct values $r$ and $s$ modulo $p$; there are no collisions yet at the "mod p level." Moreover, each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $r \neq s$, since we can solve for $a$ and $b$ given $r$ and $s$$^\dagger$:
$$a = ((r — s)((k — l)^{-1}\mod p)) \mod p $$,
$$b = (r — ak) \mod p$$ ,
where $((k — l)^{-1} \mod p)$ denotes the unique multiplicative inverse, modulo p, of $k — l$. Since there are only $p(p — 1)$ possible pairs $(r, s)$ with $г \neq s$, there is a one-to-one correspondence between pairs $(a, b)$ with $a \neq 0$ and pairs $(r, s)$ with $r \neq s$. Thus, for any given pair of inputs $k$ and $l$, if we pick $(a, b)$ uniformly at random from $Z_p^* \times Z_p$, the resulting pair $(r, s)$ is equally likely to be any pair of distinct values modulo p.
It then follows that the probability that distinct keys $k$ and $l$ collide is equal to the probability that $r \equiv s (\mod m)$ when $r$ and $s$ are randomly chosen as distinct values modulo $p$. For a given value of $r$, of the $p — 1$ possible remaining values for $s$, the number of values $s$ such that $s \neq r$ and $s \equiv r (\mod m)$ is at most$^{\dagger\dagger}$
$$\lceil p/m \rceil - 1 < ((p + m - 1)/m) - 1$$
$$ =(p-1)/m$$.
The probability that $s$ collides with $r$ when reduced modulo $m$ is at most $((p - l)/m)/(p - 1) = 1/m$.
Therefore, for any pair of distinct values $k,l \in Z_p$,
$$Pr\{h_{a,b}(k)=h_{a,b}(l)\}\leq 1/m$$
so that $\mathscr{H}_{p,m}$ is indeed universal.

Doubts:
I could not understand the following statements in the proof:
$\dagger$ :Each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $r \neq s$, since we can solve for $a$ and $b$ given $r$ and $s$
why , "we can solve for $a$ and $b$ given $r$ and $s$" $\implies$ "Each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $г \neq s$"

$\dagger\dagger$ : For a given value of $r$, of the $p — 1$ possible remaining values for $s$, the number of values $s$ such that $s \neq r$ and $s \equiv r (\mod m)$ is at most $\lceil p/m \rceil - 1 $ .
How do we get the term $\lceil p/m \rceil - 1 $ ?

We want to show that if $k_1\neq k_2\in\mathbb{Z}_p$ then
$\Pr\limits_{(a,b)\in\mathbb{Z}_p^*\times\mathbb{Z}_p}[ak_1+b\equiv ak_2+b \pmod m]\le\frac{1}{m}$.
Where both addition and multiplication are preformed in $\mathbb{Z}_p$.
We start by showing that if $a\sim U(Z_p^*)$ and $b\sim U(Z_p)$ then for all $k_1\neq k_2\in \mathbb{Z}_p$, $(ak_1+b,ak_2+b)$ is uniformly distributed over $\{(x,y)\in\mathbb{Z}_p^2| x\neq y\}$ (i.e. $h(k_1)$ and $h(k_2)$ are jointly uniform over pairs with different entries, where the randomness is over the choice of $h$). This is immediate from the fact that for all $(c_1,c_2)\in\mathbb{Z}_p^2$ with $c_1\neq c_2$, the following system of linear equations:
$
\begin{align*}
& ak_1+b=c_1 \\
& ak_2+b=c_2
\end{align*}
$
has a unique solution over the variables $(a,b)\in Z_p^*\times\mathbb{Z}_p$. Subtracting the second equation from the first yields $a(k_1-k_2)=c_1-c_2$, since $k_1-k_2$ is nonzero we can multiply both sides by its inverse and obtain $a=(k_1-k_2)^{-1}(c_1-c_2)$. If $c_1\neq c_2$, then this is a nonzero solution for $a$, and we can extract $b$ from any of the two equations. Thus, for each pair $(c_1,c_2)$ with $c_1\neq c_2$ there are unique $(a,b)\in Z_p^*\times\mathbb{Z}_p$ such that $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)=(c_1,c_2)$. This settles your first question.
Now, divide $\mathbb{Z}_p$ into $\lceil p/m\rceil$ buckets, $b_1,...,b_{l=\lceil p/m\rceil}$ as follows: $b_1=\{0,1,...,m-1\}, b_2=\{m,m+1,...,2m-1\}$,...,$b_l=\{m\lfloor p/m\rfloor, m\lceil p/m\rceil+1,...,p-1\}$. Note that each bucket except the last is of size $m$, and no two elements in the same bucket are equivalent modulo $m$. We conclude that the number of different pairs in $\{(x,y)\in\mathbb{Z}_p^2| x\neq y\}$ that are equivalent modulo $m$ is at most $p(\lceil p/m\rceil-1)$, since after choosing the first element, you are left with $\lceil p/m\rceil-1$ elements to choose from (you must pick a different bucket and each bucket provides at most one candidate). Recall that $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)\sim U(\{(x,y)\in\mathbb{Z}_p^2| x\neq y\})$, so we can finally conclude:
$\Pr\limits_{(a,b)\in\mathbb{Z}_p^*\times\mathbb{Z}_p}\left[h_{a,b}(k_1)=h_{a,b}(k_2)\pmod m\right]=\frac{p(\lceil p/m\rceil-1)}{p(p-1)}\le \frac{1}{m}$
Note that allowing $a$ to take the value $0$ only makes our analysis easier, since now $\big(h(k_1),h(k_2)\big)$ is jointly uniform over $\mathbb{Z}_p^2$, but there is an additionaly probability of $\frac{1}{p}$ that $a=0$ and our hashes will be equivalent modulo $m$, so in this case we will have to settle for an $O(\frac{1}{m})$ bound on the collision probability.


Proof that shortest path with negative cycles is NP hard I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)

How would I reduce the SAT problem into the shortest path problem in polynomial time?

Copied from my answer on cstheory.stackexchange.com:

Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.

This can be reduced from the longest-path problem.  If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.

Thus your problem is NP-Hard.


Regular expressions with backreferences over unary alphabet Setting:

regular expressions with backreferences
unary language (1-symbol alphabet)

Is the following problem decidable in this setting:

Given a regular expression with backreferences, does it define a regular language?

For example, (aa+)\1 defines a regular language, while (aa+)\1+ doesn't. Can we decide which one is the case?

For concreteness, "regular expressions with backreferences" here refer to e.g. the following subset of the usual Perl-compatible regular expressions:

a matches character a (the only character in the alphabet)
X* matches 0 or more occurrences of X
X|Y matches X or Y
parentheses can be used for grouping and capturing
\1. \2, etc. match the same string as the 1st, 2nd, etc. pair of parentheses

We can also use the normal shorthands e.g. X+ = XX*.

Evidence against the effective decidability of the problem is provided by the construction in the proof of Theorem 9 in my paper On Practical Regular Expressions: You could determine if there are finitely many Fermat primes.


Famous hacker koan: who was it about, though? Read this many years ago and can't remember who it was about. Nor can I remember the exact quote. The story goes:

  Famous computer scientist/professor is teaching a class. Student is having some problem w/ a machine and wants to reboot it, hoping to fix the issue. Professor chides him, saying something to the effect of "you can't expect rebooting to fix the problem unless you 'Truly Understand What Is Going On'". Professor then proceeds to reboot the computer and the issue resolves. ;)

Who was it?

Tom Knight

https://simple.m.wikipedia.org/wiki/Hacker_koan

The item titled "Enlightenment"

Thanks to reinierpost.


Efficient search with removal I want to search from a given set of elements. Along with that I also want to remove that searched element. The problem is that the number of these queries is $q=O(n)$, where $n$ is the number of total elements. Which data structure should I use. Also, I want to avoid hashing.

Without any additional information about your setting or requirements, an obvious first choice is some self-balancing binary search tree, such as a red-black tree. It allows you to insert and remove elements in $O(\log n)$ time, where $n$ is the number of elements.

Following a standard engineering approach, try it out first. If it doesn't meet your requirements, analyze your situation more carefully, and try something else.


Can the test set of attributes be a subset of the training set's attributes? I'm currently writing an application for a trick-based card game, where agents are assigned points based on the accuracy of their predictions of how many hands they're going to win. The number of tricks predicted will display a level of confidence to the other agents as well as also potentially allowing the agent to choose the Trump suit.

I've compiled a set of attributes (such as cards in hand, score sum total in hand) that will be useful in the prediction, but it would be ideal if I could include previous predictions in the training set.

My question is can my test data [attributes] be a subset of the training data [attributes ∩ predictions] both of which are predicting the number of hands that the agent will win?

Well, if the test data would be the same from training data, your machine learning algorithm may overfit. Because you test your model with your training data it may perform very well, as it may see the pattern even in noise. And then it won't generalize on new data.

You should separate the test data (with which you see the accuracy) to the training data.


What's the difference between a "dead" and "empty" state? In computational theory, I came across both deterministic and non-deterministic finite state machines but I heard someone said there are no dead states in deterministic machines. I thought dead and empty states were the same. What I noticed is that empty states are represented by a special symbol called an empty set ∅. What's exactly the difference?

That ∅ in the figure is just the name of that particular state in that machine.You could name it "cpx" if you want.

The figure is an example showing conversion from NFA to DFA. The conversion algorithm builds the DFA states from subsets of NFA states.The state named ∅ indicates that this state represents a particular subset of the states of the NFA, namely the empty set.

So, the symbol is just for the viewer to understand the significance of that particular state in the machine.


How reducing languages work? I am reading Automata Theory book by Hopcroft, Motwani and Ullman 2nd ed.
In this book, there are these sentences:

  In general, if we have an algorithm to convert instances of a problem $P_1$ to instances of a problem $P_2$ that have the same answer, then we say that $P_1$ * reduces to *$P_2$. We can use this proof to show that $P_2$ is at least as hard as $P_1$. Thus, if $P_1$ is not recursive, then $P_2$ cannot be recursive. If $P_2$ is non-RE, then $P_1$ cannot be RE.

I am quite confused due to last statement above because the book further states the following theorem:

  If there is a reduction from $P_1$ to $P_2$, then:

  If $P_1$  is undecidable then so is $P_2$.
  If $P_1$ is non-RE, then so is $P_2$.

I dont know whether I should feel that the last statement above contradicts with the last statement in the first paragraph. So whats true?

  If $P_2$ is non-RE, then $P_1$ cannot be RE.

Or

  If $P_1$ is non-RE, then so is $P_2$.

Or both mean the same and I am unnecessarily thinking that they are contradicting each other unnecessarily? Or the book is wrong?

You will reduce $P_1$ to $P_2$ if you know something "bad" about $P_1$, and you want to see if this extends to $P_2$.

It should read "If $P_1$ is non-RE, $P_2$ cannot be RE". If it is in the book, it's a typo.


All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete? My book states this

  If a decision problem B is in P and
  A reduces to B,
  then decision problem A is in P.
  A decision problem B is NP-complete if
  B is in NP and
  for every problem in A in NP, A reduces to B.
  A decision problem C is NP-complete if
  C is in NP and
  for some NP-complete problem B, B reduces to C.

So my questions are

  If B or C is in NP-complete, and all problems in NP reduce to an NP-complete problem, using the first rule, how can any NP problem not be NP complete?
  If A reduces to B, does B reduce to A?

If A reduces to B, does B reduce to A?

No. For a really contrived example, any possible computable problem A is reducible to the Halting Problem: just pass as input the algorithm that solves the problem A but with a while(true) tacked at the end after either the true or false case. However, we know that the Halting problem isn't computable so it can't be reduced to any such algorithm A.

The basic idea is that if there is a reduction from A to B you can learn that B is at least as hard to solve then A and requires an algorithm that is at least as powerful.

So if a problem A reduces to an easy problem B, then we can deduce A is easy (since the reduction gives us the efficient algorithm) and if a hard problem A reduced to a problem B, we can deduce that B is also hard (since if B were easy then A would have to be easy too). However there is still the possibility of making a silly reduction from an easy problem to a hard problem but in this case we can't deduce any conclusions.


Perfect matching problem Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*m_i$.
I want to find some perfect matching with some given cost. I suspect that this is hard (i.e. NP-complete). Can you solve it quickly? (find an efficient algorithm).
Here is an example: we have three courses, credit hours are 4, 5, 8. Grade points are 4, 3, 2.  A solution is a perfect matching between the lists that result in some given GPA.
For this to be computationally meaningful, the largest grade point and largest credit hour are unbounded.
P.S. Yuval hinted the reduction from Subset sum problem. I am interested in hardness proof of strong NP-completeness.

This problem is indeed $NP-complete$ as you have suspected. To see this, we will show a reduction from $SubsetSum$.
The reduction
Let $A,s$ be an instance of $SubsetSum$, where $|A|=n$. We will define $L$ as all the numbers in $A$, in addition to another $n$ zeros. For example, if $A= 4, 5, 8$ then $L=4,5,8,0,0,0$.
Now, we define $M$ to be with $2n$ values, such that we have $n$ ones and $n$ zeros.
The target value will be $s$
Proof
Such a perfect matching defines us a subset $A'\in A$, that $a\in A'$ iff $1$ is matched with $a$. Since we have $n$ values in $A$, and we have $n$ ones and $n$ zeros in $M$, then each pair of $(0,1)$ in $M$ can be assigned to every pair $(a, 0)$ where $a\in A$, and thus any $a\in A$ can be matched with either $0$ or $1$, contributing to the total sum either $a$ or $0$. Therefore, there is a perfect match if and only if there is a subset with that sum (as the value of the matching is a sum of the subset $A'$).


Analyzing rules of articles in languages I'm interested in finding a solution for the following problem:

problem space: any language that has more than 1 article
let's take German language as example. So the articles in German are "der", "die", "das". - every word has an article as prefix and you must use the article. for example you can't say just "Auto"(car), you must say "das Auto".
If you are not a native German speaker, you have bad luck, because you have to memorize the article too, when learning a new word, since there are only 3-4 rules to know which word takes which article. And those rules are perhaps about max. 10% percent of the vocabulary. (for example if a word ends with "-ung", it takes "die")

So here comes the funny part: as a non-native-German-speaker, i wanted to analyze the language from an IT-point of view and asked some friends of mine random words with the following properties:

first I reduced the input set from "any German word" to "a German word", for which no known article rule exists".
then I extended the input set with "made up words", which do not exist.

Every candidate had the same answer for German words, which should be not surprise. But when I asked them per word "why do you think/feel that the article of the word is "der/die/das"?" they couldnt give an answer. They just know it, without knowing why.

Here comes the real hammer: every candidate had the same answer for any made-up non-German word. I say anything, make any meaningful voice, and they all give the same answer (ie. article).

I'm pretty sure that I'm not the first human being in the world who made thoughts about this topic. And I'm interested in any scientific papers/research about that topic.
By the way, what I definitely do NOT need is, any method (like neural networks) which outputs a pure mathematical function. I thought about following possibilities:

focusing on feelings of subjects psychologically (I think it can be managed with colors somehow etc.)
analyzing the words statistically according to their syllable structure

Where can I begin? What are your suggestions? Are there any Machine Learning research about that topic?

A language is a result of a complex historical development. If the development were guarded by simple language generating rules it would've been different like some artificial languages such as the Esperanto language.

Many natural languages have nouns split into several categories. These categories are often referred to as the Gender. Though the link between the grammatical gender and the natural or biological gender is not always obvious.

In Slavic languages for instance the gender of a word can be guessed from the flection at the end of the word. E.g. in Russian "облако" (a cloud) is neutral, "-о" is the flection, and "зима" (the Winter) is femenine, "-а" is the flection.

In Old English the category gender did exist but was eliminated during the evolution towards the Modern English. In general all languages that stem from the Latin language inherited some form of grammatical gender (for more details see the discussion in Wikipedia).

When learning the language one has to memorize at least the words and there meaning. In learning languages that keep grammatical gender one has to memorize the gender as well. You can find the gender of a word in any German dictionary.

Look at the small letter f, m, or n, printed in italics next to the word.

E.g.

Bündel, n a bundle;

Bus, m a bus;

Tasse, f a cup;

That is "Das Bündel", and "Der Bus", and "Die Tasse".

When a comprehensive dictionary is available for a language with all the nouns annotated with their respective grammatical gender, I guess there is little space left for machine learning. It is much more easy to keep the complete dictionary in memory than to devise a set of rules that would always be prone to errors.


Which neural network topology is the most efficient to generate randomly shaped letters? I have created some unique shapes, so-called "letters" for a custom alphabet, all of which can fit into 9x9 pixels. Instead of drawing countless more, I try to combine two solutions I saw in a relevant part of Reddit, and decided to let a neural network create some additional examples.

Desconstructing the problem: letters are formed in a graph of 25 nodes (always ordered into a 5x5 square) by spontaneously connecting only the adjacent nodes - no diagonal or non-adjacent edges are present.

For a neural network input, I drew these runes into 9x9 blocks, where each row has 5 "pixels" for each nodes, and 4 more as a place for indicating connection.

Below is the current letter set, with an example of an empty graph and the only example generated by my network in the last line.

I've made a perceptron (tried 1, 2 and even 3 hidden layers) where input layer had 6 neurons, using them as a binary code (zero values mean -1 activation, and one values are the 1 activation), andthe output layer had 81 neurons. (9x9 to plot out the desired shapes)

My aim was to be able to produce additional letters by defining letters as sample and making the network to learn it. Then, I assumed that by activating the network with undefined inputs, I can find new letter shapes.

I used built-in functions froM JavaNNS and backpropagation as learning method.

Which are the parts of my topology, where I could possibly go wrong? What is the most suitable solution for this task?

I think it's unlikely you're going to get good results.  Neural networks typically require a large training set.  With only a few dozen or so examples, I doubt you'll have a large enough training set for this to work well.

So, what could possibly go wrong?  I suspect the most likely outcome is that you'll get useless results.

That said, if you really insist on trying neural networks, you could try using a variational autoencoder.  An autoencoder consists of two halves: the first half maps the input $x$ to a value $z$ in the "latent space", and the second half maps $z$ to an output $x'$.  You train the autoencoder to ensure that (hopefully) $x$ and $x'$ are very similar, for all the instances $x$ in your training set.  The idea is that you make the latent space much smaller than the space of inputs/outputs, and you hope this forces it to generalize.

For instance, the input might be a 40-vector $x \in \mathbb{R}^{40}$, encoded by a one-hot encoding ($x_i=1$ means that you include a black line in the $i$th position; $x_i=-1$ means you don't include it).  The latent space might be $\mathbb{R}^2$ or $\mathbb{R}^3$ or so.  You might include a few layers of a convolutional network to map from $x$ to $z$, and then the inverse architecture to map from $z$ to $x'$.  Then, you could train the network using a standard loss function for variational autoencoders, along with some regularization term.


Complexity of generating non-uniform random variates What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) hypergeometric variates in (expected) constant time (i.e. independent of the distribution parameters)?

There is quite a bunch of literature; however, it’s hard to understand a lot of the papers. Moreover, I found some statements that seem contradictory to me (probably due to wrong understanding).

For example, Stadlober (or similar here) mentions a "generalization [of the ratio-of-uniforms approach] to any unimodal discrete distribution". The ratio-of-uniforms approach has been called uniformly fast, which is a synonym for constant time, I suppose (?). That would mean that we can generate random variates for each discrete distribution in (expected) constant time.

However, in another paper, I found the following theorem: On a RAM with word size $w$, any algorithm sampling a geometric random variate $Geo(p)$ with parameter $p \in (0,1)$ needs at least expected runtime $\Omega(1 + \log(1/p)/w)$.

Apparently, this means that it is not possible to generate negative binomial variates in time independent of the distribution parameters.

The binomial, negative binomial, and hypergeometric distributions are discrete distributions. Knuth and Yao (1976) gave complexity results for discrete distributions in general. Given a stream of i.i.d. unbiased random bits, any algorithm that samples from a discrete distribution will require at least—$$b = -\sum_{x\in\Omega} \mathbb{P}(X=x)*\log_2(\mathbb{P}(X=x))$$random bits on average to sample a variate $X$ from that distribution (where $\Omega$ is the distribution's support), and they gave an algorithm that comes within 2 bits of this lower bound (and showed that coming within 2 bits is the best possible for any algorithm).
The case of continuous distributions such as the normal distribution is more complicated, but Devroye and Gravel gave complexity results for sampling a continuous variate to a desired accuracy, given a stream of i.i.d. unbiased random bits, using Wasserstein distance as the accuracy metric.
I also want to note one more thing. If the distribution of $X$ has a continuous and bounded quantile function (inverse cumulative distribution function) $F^{-1}$, I suspect that the bit complexity of sampling $X$ also depends on the modulus of continuity of $F^{-1}$, call it $\omega(h)$. In this sense, Lipschitz continuous quantile functions (where $\omega(h) = O(h)$) are the simplest cases of such functions and in that case it's simple to describe an algorithm to sample $X$ to a desired accuracy. For such functions, the algorithm uses—$$ceil(\ln(\max(1, L))-\ln(\epsilon))/\ln(\beta))$$random digits, where $L$ is the Lipschitz constant, $\epsilon$ is the desired accuracy, and $\beta$ is the digit base (such as 2 for binary). I suspect that with other moduli of continuity, the complexity will be as follows: $$ceil(-\ln(\omega^{-1}(\epsilon))/\ln(\beta)).$$
REFERENCES:

Knuth, Donald E. And Andrew Chi-Chih Yao. "The complexity of nonuniform random number generation", in Algorithms and Complexity: New Directions and Recent Results, 1976.
Devroye, L., Gravel, C., "Random variate generation using only finitely many unbiased, independently and identically distributed random bits", arXiv:1502.02539v6 [cs.IT], 2020.


Is P/poly known to be in RE? Is P/poly known to be in RE?
If yes what other classes is it known to be part of.

$P/poly$ is NOT a subset of $RE$. Specifically, the unary non-halting problem (i.e. given a Turing Machine encoded in unary, does it run forever?) is in $P/poly$ but not $RE$. In fact, every undecidable unary language is in $P/poly$.


Modular exponentiation in P I need to prove that the following language is in $\mathsf{P}$:
$$ L = \{\langle x,y,z,d \rangle : xˆy \equiv z \pmod{d}\}.$$

I'm assuming I just have to prove with an algorithm or negate that it's part of NP. But I don't know how to do it with this mathematical formula.

First of all, anything in $P$ is also in $NP$, so proving that it's not in $NP$ will be an exercise in futility. I'm also going to change your variable names a bit to make them clearer; the letters I use stand for base, exponent, and modulus.

What you seem to be looking for is a modular exponentiation algorithm. In other words, a way to compute $b^e \mod m$ in polynomial time. Several of these exist, but here's the simplest one I know of:

function modular_exponent(b, e, m):
    z ← 1
    b ← b % m
    for i ← 1..e:
        z ← (b × z) % m
    return z

The number of multiplications and modulus operations we do is linear in $e$, and the operands to those operations are never larger than $m$. So the runtime is $O(e (\log{m})^2)$ (assuming multiplication runs in log-squared and modulus runs in logarithmic time; in practice you can make this even a bit more efficient using something like Karatsuba multiplication, but that doesn't matter for this problem).

This is clearly a polynomial runtime, so the modular exponentiation decision problem ("for given $b, e, m, z$, is $b^e\cong{}z \mod m$?") is in $P$.


If you have a DFA M, how do you construct a new NFA that accepts L(M) and {e}? Suppose you're given a DFA $M$ with a 5 tuple of $(Q, \Sigma, \delta, q_0, F)$.

How do you construct an NFA that accepts $L(M)$ and $\{\varepsilon\}$, the set containing the empty string? I know that a DFA is an NFA.

My thought is that you would simply add a new transition from the start state to the accepting state, which takes epsilon/the empty string.

For example (eps. is epsilon/empty string):

Since I've added an empty string transition, the machine is no longer a DFA, but it is an an NFA.

You've got the right idea, but there's a slight bug.
If you add an $\varepsilon$-transition from the start state to all accepting states, then the new machine recognizes a subtly different language.
Let $L_k = \{w_1 \cdots w_k : \exists u_1, \dots, u_{k-1} \in L(M) \text{ such that } w_1 u_1 w_2 \cdots u_{k-1} w_k \in L(M)\}$.
Note that $L_1 = L(M)$.
This new machine will recognize the union of the $L_k$, i.e., it recognizes $\bigcup_{k=1}^{\infty} L_k$.

Instead, you can create a new state $q_{\text{empty}}$, add an $\varepsilon$-transition from $q_0$ to $q_{\text{empty}}$, and take the new set of accepting states to be $F \cup \{q_{\text{empty}}\}$.


What does "finding an optimal action" for a bandit mean? In Sutton and Barto's reinforcement learning book, in multi-armed bandit problem a phrase has been used. "finding an optimal action" using greedy/$\epsilon$-greedy algorithm. When it is said that an algorithm "finds the optimal action " ?

In the bandit setting, to each arm is associated an unknown reward distribution. The optimization goal is to find a policy (a series of level pulls) which yields the maximum sum of rewards.

"Finding an optimal action" thus refers to the process of discovering the arm which gives you the most reward.


Algorithm to find whether there is a path (any path) above length X between two vertices We all know how to find the shortest path between two vertices, but what if I just want to know the answer to this question - is there a path, (any path), between vertex A and B of length larger than some X?

Should start from the shortest path, and then merge adjacent nodes if its length is less than X? (or extend the search "circle" gradually)

I don't want to first find all possible paths and then filter out those shorter than X, I want to stop the moment I find any path above a certain length between the two vertices, (and stop if I haven't found one after some MAX iterations)

(I assume I first do a shortest paths to find if there is at all any path between the nodes to avoid searching if there isn't)

It somehow feels it should be simpler that what I'm making it, but I can't seem to find a text-book algorithm for it (e.g. BFS / DFS / Dijsktra / Bellman Ford are not really helping here, right?)

I'm sure it's simple, but I need some push in the right direction.

(cross posted from https://softwareengineering.stackexchange.com/questions/283038/algorithm-to-find-whether-there-is-a-path-any-path-above-length-x-between-two based on suggestions in the comments)

If you allow duplicate vertices on your path, you can make a network from your graph by giving each edge weight $-1$. Then, use Bellman Ford to find the shortest path and see if it has length $-X$ or less.

If you don't allow repeats, then the problem is NP hard, since finding the longest simple path between two vertices tells you whether there is a Hamiltonian path or not.


Relationship between message entropy and complexity of the best algorithm Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages?

E.g. linear search problem. We have an ordered set of incomparable elements (no < and >, equivalence only) of length $N$, and element for search – A, which could be in set maximum once. Set could be represented as sequence like 00001000, length $N$, where 1/0 means that element here equals A/not equals A. Algorithm parses the message and responds "not contains" (for one message 00000...0 ) and "contains" (all other messages). For uniform probability of being equal A for each position, entropy of responses equals:
$$H=-\frac{1}{N+1}\cdot \log_2\left(\frac{1}{N+1}\right) - \frac{N }{N+1} \cdot \log_2\left(\frac{N}{N+1}\right)$$
$H$ goes to zero quickly:

We also know that $\lfloor\text{entropy}\rfloor+1$ equals the mean message length in case of best coding (Shannon's source coding theorem for symbol codes). That means we could index any message with binary string, and it will take us only one symbol – one step in algorithm!

But existing codes for linear search (e.g. brute force) require $\frac{N+1}{2}>1$ steps, and all improved techniques require comparability (e.g. binary search).

This suggests that entropy of message does not equal the number of step in best possible algorithm of problem solution (=message classification).

But then what is the link between both? Is there any relationship between the number of steps for the abstract "best code" and the entropy of message?

I believe you are looking for algorithmic information theory.  This defines the information contained in a string as proportional to the size of the smallest program that produces that string.  The metric is called Kolmogorov (Колмогоров) complexity.

The problem with normal Shannon entropy, is that it is defined relative to your assumed model of the producer of the information stream.  Shannon entropy really only deals with models that produce infinite and stationary random streams.  When you know that the producer is deterministic then the Shannon entropy of the stream is 0 (even though you don't know the algorithm of the producer.)  You can often model a deterministic stream as some kind of Markov process, but there will always be a Markov process with more states that models the deterministic stream and in which the entropy is smaller.


Are there any exponential-time iterative algorithms? Is it possible to implement an exponential-time algorithm using iteration, as opposed to recursion? I didn't have any particular algorithm in mind, I was just thinking theoretically.

The way I was thinking was to iterate not by adding 1, but by adding a small number j at the end of each loop. So the 3rd parameter in the for-loop would look like i+j instead of i++, and j would be really small (negative exponent perhaps? Like 2^-n)... Still, I'm not sure how such an algorithm could actually work, though.

Thanks for any input.

Yes. Given an input of length $n$, overwrite it and use the space to count to $2^n$ in binary.

Once you've done that, you could write out $2^n$ zeroes and then count to $2^{2^n}$ and so on, ad infinitum.


Exponential time algorithms Wiki define Polynomial time as fallow:

  An algorithm is said to be of polynomial time if its running time is
  upper bounded by a polynomial expression in the size of the input for
  the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$

I understand that in general speaking the difference between Polynomial time and Exponential time is that exponential function grows strictly faster than any polynomial function, asymptotically(reference).

I am trying to understand the core definition of Exponential time.

What elements will make one algorithm to run in Exponential time?
What change do I need to do in the polynomial expression to make it Exponential time?(By it I am referring to the algorithm definition in the beginning of the question)

There's no easy answer for this one, though there are signs to look out for. Examining every possible subset of a set, for instance, is exponential - so if I had a set of integers $\{x_1,...,x_n\}$, and wanted to check every subset of these to see if they sum to $0$, I'd have to consider exactly $2^n$ subsets, which makes this method exponential time. Several different traps can make an algorithm exponential time, however, so rather than looking out for broad categories, analyse algorithms on a case-by-case basis.
If an algorithm takes $n^2$ steps to complete, then it's polynomial. If it takes $2^n$ steps, it's exponential. The difference is the position of the $n$. If something is $O(n^m)$ for $n> 1$, $m>0$, then it's polynomial in $n$ for fixed $m$, but exponential in $m$ for fixed $n$.


What will trigger a worst time search for a binary heap and what is the run time? I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of $\mathcal{O}(n)$ because you will have to go through each and every single node to get to the value you want.

However, many sources state that heap has a worst case of $\mathcal{O}(n\log n)$ for (all?) transactions.

I don't see how you can do $n\log n$ for a monotonically increasing binary heap.

Can someone clarity?

Heaps are maintained so that they are always balanced. A heap containing $n$ elements will have height $O(\log n)$. All operations on heaps take time linear in the height.


1-sparse recovery algorithm In the reference below, a 1-sparse recovery algorithm over a vector $a \in R^n$ is defined as follows. My question is why do we need the modulus (i.e. $x \mod p$)?
Algorithm:

Keep track of
$$
   \begin{split}
   w_1 &= \sum a_i \\
   w_2 &= \sum i a_i \\
   w_3 &= \sum a_i z^i \mod p
   \end{split}
   $$
Test if
$$
   \begin{split}
   w_3 \equiv w_1 \cdot z^{w_2 / w_1} \mod p
   \end{split}
   $$
For some large prime $p$.

Reference: Section 3.2, "1-sparse recovery: second attempt", https://web.stanford.edu/class/cs369g/files/lectures/lec11.pdf

Without the mod p, the running time to check the condition would be exponential, which is unacceptable.  Also, it would require exponential space to store $w_3$ and to check the condition.
Also, the procedure involves choosing an integer $z$ uniformly at random from $\>0,\dots,p-1\}$.  You can choose an integer uniformly at random from $\{0,\dots,p-1\}$, but you can't choose it uniformly at random from the set of all integers.  So, you'd have to think about exactly what alternative approach you had in mind if you wanted to omit the mod p.


Simple Uniform Hashing Assumption and worst-case complexity for hash tables Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)?

It says in the Wikipedia article that this assumption implies that the average length of a chain is $\alpha = n / m$, but...

...this is true even without this assumption, right? If the distribution is [4, 0, 0, 0] the average length is still 1.
...this is a probabilistic statement, which is of little use when discussing worst case complexity, right?

It seems to me like a different assumption would be needed. Something like:

  The difference between the largest and smallest bucket is bounded by a constant factor.

Maybe this is this implied by SUHA? If so, I don't see how.

I think the answer is no, SUHA does not imply anything regarding worst-case time complexity.

The bottom line is that

the hashing is (even though uniform) still viewed as random, and
the keys are unknown.

Regardless of how small the probability is for all keys to hash to the same bucket, it's still a theoretical possibility, thus the theoretical worst-case is still O(n).

When discussing hash tables and complexity, I think this is mentioned briefly, regarded as irrelevant in practice and then the discussion moves on to expected run time complexity, and we're in O(1) land.

With the assumption mentioned in the question...

  The difference between the largest and smallest bucket is bounded by a constant factor.

...(which is strictly stronger than SUHA) it can indeed be shown that the worst-case run time complexity is O(1). This assumption implies that even the largest bucket is within a constant factor of the load factor limit. This in turn means all linked lists are bounded by a constant and we get O(1) as worst case.

This assumption however is somewhat unreasonable. While it's quite probable that it holds true for any descent hash function and non-pathological set of keys, how would one guarantee such property? One would have to push this assumption further down and make constraints on what keys are allowed to be stored in the hash table and so on. This is what makes it unreasonable in a sense.


Where would someone find amortized analysis more useful than average analysis and the opposite? I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing in each step, while average analysis produces an expected cost based on probabilities.

For them to both exist as separate ways of doing analysis of algorithms, then one must be preferred over the other one in some cases, however I can't figure a case to actually show that.

The two are not mutually exclusive. In most situations you're interested in amortized analysis, since usually operations are fast enough so that no user would notice a one time long running time, the real performance being determined by the amortized running time. A good example is garbage collection, essential to many modern computer languages. Garbage collection is extremely slow, but the cost is amortized to be very manageable.

The only notable exception to this is real time applications. For example, if you're operating a hard drive, you need to be fast always. Same goes for some other services provided by the operating system. But that's a specialized area.

Average case analysis is relevant when you can expect the data to be random enough. For example, a long scientific simulation could include a random element, and can be analyzed accordingly. Other data should not be assumed to be random for security reasons. For example, a web server distributing work across other servers can be attacked if load balancing relies only on input randomness.

Sometimes the average case is hard to define. For example, the simplex algorithm and SAT solvers often seen to run much faster than the worst case, but it's hard to attribute this to average case behavior since it's difficult to come up with a relevant average case distribution. Instead, one could point out some relevant features of the input, but doing this rigorously is very hard.


Find an upper bound for a Linear Recurrence Im having a hard time trying to figure out how to find an upper bound to the following recurrence:

$T(N)=T(N-1)+\mathcal{O}(n)$

where i know initially $N=\lfloor\tfrac{n}{logn}\rfloor$

I believe it can be solved as a linear recurrence, but i don't know how to put $n$ in terms of $N$.

You say that $N=\lfloor\tfrac{n}{logn}\rfloor$. But since you have a linear recurrence in N, not n, you really want n as a function of N.

We have $n ≈ N \log n$.

You substitute this for n and get $n ≈ N \log (N \log n) = N \log N + N \log \log n$.

$\log \log n$ is small compared to $\log N$, so we ignore it and get $T(N)=T(N-1)+\mathcal{O}(N \log N)$

We get $T(N)$ by summing $\mathcal{O}(k \log k)$ for k = 1 to N, which will be $\mathcal{O}(N^2 \log N)$.


Following but not intersecting time segments to detect multiple accounts In some code I'm currently writing, I'm stuck on the following algorithm to implement. The goal is to find real world users using multiple different accounts.

I've a List of UserData. This list is pretty big (> 10M entries)

A UserData is defined as: { userId, List<TimeSegments> }. A TimeSegment is {connectionDate, disconnectionDate}. We can assume here that the average size of the list of timeSegments is 100.

I want do find groups of users such as:

for each group of users, all timeSegments are non overlapping (we assume here that a user cannot be connected with multiple accounts at the same time)
for each user U1 in a group of users, there is a user U2 in the same group such as at least one, U1 disconnected and then U2 connected in the following 15 minutes (or the opposite) (we assume here that at least once, a user will disconnect from an account and with another one immediately after)

Of course, the brute force O(n²) solution (find couples of users and then merge those couples) is not good enough due to the size of data

Any idea of how to start this ?

Thanks !

I would sort all events (logins, logouts) in increasing order by time, then walk through the list.  For each logout event from user $u$ starting at time $t$ encountered during this walk, scan forward from that point until hitting time $t+15$, incrementing a counter for the pair $(\min(u, v), \max(u, v))$ in a hashtable whenever a login event for user $v$ occurs.  (You could alternatively increment two counters, $(u, v)$ and $(v, u)$, but this uses twice the memory and gains nothing.)

Afterwards, every large count in your hashtable corresponds to a "candidate pair" of users.  Walk through the hashtable, and for each counter above a threshold of your choosing, check whether the logged in intervals for this pair of users intersect.  If they don't, flag the pair as likely operated by the same human.

(BTW, I'm not confident that mutually exclusivity of login intervals will apply in practice: Users might run their two accounts simultaneously in different browsers, one in a phone, or one in a private window, etc.  Depending on your application, maybe a better criterion would be to check whether the two users actually interfere with each other to any significant extent -- e.g., for SO, whether the same questions and answers tend to be upvoted/downvoted.)

There will probably be large numbers of pairs in the hashtable with low counts, due simply to chance.  If you find that singleton counts are bloating the hashtable, you could reduce memory usage (at the cost of introducing a very small amount of inaccuracy) by using a Bloom filter to store all "first" encounters of any $(u, v)$ pair, and only creating counts in the main hashtable for a pair $(u, v)$ when $(u, v)$ is already in the Bloom filter.


How is a Turing Test defined? Turing Test definition taken from wikipedia:

  The Turing test is a test of a machine's ability to exhibit
  intelligent behavior equivalent to, or indistinguishable from, that of
  a human. In the original illustrative example, a human judge engages
  in natural language conversations with a human and a machine designed
  to generate performance indistinguishable from that of a human being.
  All participants are separated from one another. If the judge cannot
  reliably tell the machine from the human, the machine is said to have
  passed the test. The test does not check the ability to give the
  correct answer to questions; it checks how closely the answer
  resembles typical human answers. The conversation is limited to a
  text-only channel such as a computer keyboard and screen so that the
  result is not dependent on the machine's ability to render words into
  audio

But how is a Turing Test defined?

What type of questions are considered to be so good that trick the human judge?

What and who defines a human judge suitable to be a judge? (for example if the judge is 5 year old wouldn't he be more easily tricked than a 50 year old computer scientist?)

All those chatbots are considered to pass the Turing Test? Most people are not sure if the chat bot is an actual bot or not.

Although Alan Turing is of course a very important computer scientist, the Turing test is only superficially related to computer science. It is more related to philosophy.

As long as machines exist people have wondered whether it is possible to construct a machine that can think. But to answer this question we must first answer the question what it means -- what is thinking? Turing tried to circumvent this philosophical problem by changing the question a bit: the goal is no longer a thinking machine but a machine which is indistinguishable from a thinking being.

The Turing test was intended as a thought experiment to make the reader think about (artificial) intellingence in some way, but it appealed to a lot of people. So people started to organize Turing tests for real, and if you're doing real Turing tests, then of course you need real rules. Last year the Turing test organized by the University of Reading attracted a lot of attention because, according to the rules fixed for that particular Turing test, one computer program beat the judges. See here for the press release.


Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space Assuming you have a balanced tree, without parent-pointers, with $n$ nodes, and a height $H = \mathcal O(\log n)$.

I know you can traverse the tree in level order in $\mathcal O(n)$ time using a queue. However, even in a balanced tree, the queue can grow to $\mathcal O(n)$ in size.

So the best I came up with is essentially to in/pre/post order traverse the tree in $H$ passes, one for each level in the tree, and simply filter the visits to the level for that pass. This gives an algorithm with $\mathcal O(n\cdot H ) = \mathcal O(n \log n)$ runtime and $\mathcal O(H) = \mathcal O(\log n)$ space.

The question is:

is there a algorithm for traversing a balanced tree without parent-pointers in linear-time, and logarithmic space?
Or at least, in $\mathcal o(n\log n)$ time and $\mathcal O(\log n)$ space (i.e a better result than my naive algorithm).
Or more generally, linear time, but sub-linear space?

Also, no cheating, you cannot alter the tree :)

Let's start by considering the case of a full tree (depth $\lg n$, contains exactly $n$ leaves, where $n$ is a power of two).  It's possible to build an algorithm for this case with space complexity $O(\lg n)$ and total running time $O(n)$.

In particular, Hendrik Jan describes an elegant algorithm whose running time is $O(n)$.  Let me flesh out the details.  Consider a $\lg n$-bit counter, whose value is stored in binary, and that supports one operation: Increment (adds one to the counter).  How many bits needed to be flipped by each invocation of the Increment operation?   The answer is $\lg n$ in the worst case (when you increment from $0111 \cdots 1$ to $1000 \cdots 0$), but a standard analysis shows that the amortized number of bit-flips is $O(1)$ -- the amortized analysis is a standard exercise in many algorithms textbooks.

Note that you can treat any bit-string $x$ of length $\le \lg n$ bits as a specification of a path from the root of the tree to some node $n(x)$ ($0$ means go left; $1$ means go right; the most significant bit is the first branch taken in the path; the least significant bit is the last branch).
Suppose the $\lg n$ bits stored in the counter are denoted $b_1,\dots,b_{\lg k}$.  Treat the bit-string stored in the counter as a specification of a path to a leaf.  Also, for each index $i$, store a pointer to the node $n(b_1 \cdots b_i)$, i.e., the node reached by following the path that corresponds to the first $i$ bits in the counter (the $i$ most significant bits).  This takes $O(\lg n)$ space.

Now we're going to repeatedly increment the counter, and update the pointers.  We only need to update a pointer when its corresponding bit flips: e.g., if $b_i$ changes, we'll need to update the pointer $n(b_1 \cdots b_i)$.  This update can be done in $O(1)$ time, by using the pointer to $n(b_1 \cdots b_{i-1})$ and then looking at its left or right child (depending on whether $b_i=0$ or $b_i=1$ after the update).  Importantly, whenever bit $i$ flips, so do all of the bits $i,i+1,i+2,\dots,\lg n$, so all of the pointers will be updated as necessary.  Thus, at every point in time all $\lg n$ pointers are correct.

What's the running time?  We only update a pointer when its corresponding bit changes.  Each time we update a pointer, we do $O(1)$ work.  Therefore, the total number of operations is equal to the total number of bits that have changed, as we increment the counter from $1$ to $n$.  But now it's a standard result that the amortized running time of the Increment operation is $O(1)$ bit flips: i.e., you can increment the counter $n$ times, at the cost of a total of $O(n)$ bit flips.  Therefore, the running time of this algorithm is $O(n)$, and the space complexity is $O(\lg n)$.  The constants hidden by the big-O notation are relatively small: e.g., the total number of bit flips is $\le 2n$, so you'll follow about $2n$ child pointers, and you only need space for $\lg n$ pointers.

What if the tree is not full?  In other words, maybe the tree has $n$ leaves and depth $c \lg n$.  Then a bunch of subtrees are missing.  However, I think it is possible to just skip over them as you increment the counter.  Therefore, it looks to me like the total running time should remain $O(n)$ for this case, and the space complexity will be $O(\lg n)$.  I confess I haven't checked the details of this part carefully, but it looks like it should work out.


Solving the recurrence of recursive insertion sort I have solved that the recurrence of running time of the algorithm given as

$$
T(n) = \begin{cases} \Theta(1) & \text{if n=1} \\ T(n-1)+\Theta(n) & \text{otherwise} \end{cases}
$$

So the question is that solve the recurrence that I have solved above.

So this is my answer.

Case 1

Show that $T(n) = \Theta(n)$

Guess $T(n) \le dn^2 $

$T(n) \le d(n-1)^2 + cn$

$ = d(n^2-2n+1)+cn $

$ = dn^2 - (2d-c)n + d $

it solves when $d \ge (2d-c) n $, which is same as $ \frac{d}{2d-c} \ge n $

When $ \frac{d}{2d-c} \ge n $ , then $T(n) = O(n^2) $

So this process is equally in Case 2 which is showing $T(n) = \Omega (n^2)$.

Can you please check whether my approach is right?

Thanks for your help.

Why do u need to guess?
T(n) = T(n-1) + cn  {c is a const}
T(n) = T(n-2) +c(n-1) +cn
     = T(n-3) +c*[(n-2)+ (n-1) + n]
.....

Keep going this way till u reach the arithmetic sequence  (2+...+(n-1)+n]. So,

T(n) = T(1) + c* n(n-1)/2 = O(n2)

You may check any Algorithms book or lecture notes on solving recursive equations; we don't usually guess, there r rules and this one is trivial.


How is this lamda function beeing executed in an example for the Y combinator I have spent a few hours now trying to understand how the Y Combinator is working and how it allows us to construct recursive functions with higher order functions.

I have been going through this derivation http://mvanier.livejournal.com/2897.html which is using the factorial function for explanation which I find quite helpful but at some point I am always getting lost.

I still understand this part

  (define (part-factorial self)
    ((lambda (f)
       (lambda (n)
         (if (= n 0)
             1
             (* n (f (- n 1))))))
     (self self)))

  (define factorial (part-factorial part-factorial))
  (factorial 5) ==> 120

We have a function part-factorial which takes as a formal parameter self and applies it as argument (self self) to the first lambda function. So inside the first lambda f will evaluate to (self self) which in case of the factorial function will evaluate to (part-factorial, part-factorial). So in the second lambda then if we take 5 as our n the call to the function f will evaluate to part-factorial part-factorial 4 which will start the recursion.

After a few syntax changes we now define the functions as

  (define almost-factorial
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))

  (define factorial
    ((lambda (x) (x x))
     (lambda (self)
       (almost-factorial (self self)))))

  (factorial 5) ==> 120

And at this point I am confused. I understand the almost-factorial function as it is pretty much unchanged compared to part-factorial however the new factorial function is unclear to me, from a syntax perspective. I don't understand anymore which lamda will be executed with which parameters and in which order.

Could anybody explain to me the execution of this function?

I am just going to write h for almost-factorial because long names can sometimes obscure math.

We consider:

((lambda (x) (x x))
 (lambda (self)
   (h (self self))))

Write foo for ((lambda (x) (x x)) and write bar for (lambda (self) (h (self self)))). Then our expression is just

(foo bar)

Using the definition of foo we see that this is equal to

(bar bar)

Then we use the definition of bar on the first occurrence of bar to see that this is equal to

((lambda (self) (h (self self)))) bar)

which in turn is just

(h (bar bar))

We discovered that (bar bar) is equal to (h (bar bar)). Let us write g for (bar bar), so g is equal to (h g). Taking into account the definition of h (which is jsut almost-factorial from your question) we see that (h g), and therefore g, is equal to

(lambda (n)
  (if (= n 0)
      1
      (* n (g (- n 1)))))

In other words, g is the usual factorial function. I hope I got all the silly lisp parentheses where they are supposed to be.


Construct a DFA from the regular expression (a)*+(aab)* I've broken down the expression into two simpler DFAs but right now I'm stuck.

I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.

The approach of combining two smaller DFAs is right. However, it is not correct to superimpose one DFA on another simply. For example, your combined DFA accepts $aaab$, which is not included in $a^*+(aab)^*$.

The correct way to combine two DFAs so as to produce the union of their languages is to construct the product automaton of them, defining the new final states appropriately. Please check this question and answer for details.

For the current case, we can use more states in the DFA so that it remembers more about the input string and it is deterministic enough to stipulate each transition.

$$\begin{aligned}
q_0&: \text{for the empty string}.\\
q_{a}&: \text{for string }a.\\
q_{aa}&: \text{for string }aa.\\
q_{aaaa^*}&: \text{for strings } aaa, aaaa, \cdots.\\
q_{aab(aab)^*}&: \text{for strings } aab, aabaab, \cdots.\\
q_{aab(aab)^*a}&: \text{for strings } aaba, aabaaba, \cdots.\\
q_{aab(aab)^*aa}&: \text{for strings } aabaa, aabaabaa, \cdots.\\
q_{\text{reject}}&: \text{for all other strings.}\\
\end{aligned}$$

$q_0$ is the initial state. $q_0, q_{a}, q_{aa}, q_{aaaa^*}$ and $q_{aab(aab)^*}$ are accept states. $q_{reject}$ is a dead state.


How to define the languages of the implicit set system problems? There are implicit versions of some set system problems or matroid problems.
A set system is a pair $(U, \mathcal{F})$, where $U$ is a universe of size $n$ and $\mathcal{F}$ is a collection of susbets of $U$. $\mathcal{F}$ may satisfy some properties (e.g. Matroid).
We define $\Phi$ is a polynomial-time oralce which determines whether $S \subseteq \mathcal{F}$ given the universe $U$ and a subset $S \subseteq U$.
We formally define the implicit set system problems: Given a universe $U$, the goal is to determine whether there exists a set $X$ satisfying the property $P$.
For example of the property $P$.

The size of $X \in \mathcal{F}$ at least $k$.
$X$ hits all the elements $S \in \mathcal{F}$.

So the size of the instance is $|U| = n$.
What is the language of the implicit problem? It seems that the input contains an oracle.
How can I know the complexity of this kind of problems.
I think the size of this problem can be smaller (that is $O(\log n)$), because the input can just be a natural number, right?

There are different notions of complexity used for various computational problems, not all tasks fit naturally to the standard model of decision/search problems. The "classic" analysis of complexity talks about how many resources we need to compute $f(x)$ given $x$, but this misses a lot of interesting questions we can ask. Consider communication complexity, where we want to compute $f(x,y)$ where one sides holds $x$ and the other holds $y$, while minimizing the number of bits exchanged between the parties. This requires a new definition of complexity. Same goes for query complexity, where we are given a black box access to some function $f$ and we want to know how many evaluations of $f$ are required to determine if it satisfies some property $P$.
The seemingly natural way (this of course depends on the context) to determine hardness of set system problems would be in terms of standard complexity and the number of queries to the membership oracle. As the set system is given, I don't want to involve hardness of deciding whether some set is in the system, so I'll only charge one operation for querying the membership oracle. This allows, in a sense, to isolate the hardness of evaluating the property from the hardness of the system's description.


Hierarchy of undecidable languages Let us define two languages of Turing machines.
$$
EQ_{TM} = \{<M_1,M_2> : L(M_1) = L(M_2)\}
$$
$$
ALL_{TM} = \{<M> : L(M) = \Sigma^*\}
$$
It is easy to show that neither of the languages are in $RE \cup coRE$, and also it is easy to construct a reduction $ALL_{TM} \leq EQ_{TM}$.

I suspect that there is no reduction in the other direction, but I don't know how to prove it. Is there some sort of hierarchy of undecidable/non-recognizable languages that proves it?

Let's fix the following definition for $L(M)$: it's the set of strings $x$ such that $M$ halts on input $x$.

Given machines $M_1,M_2$, consider a machine $M$ which accepts two inputs $x$ and $t$ and runs the following algorithm:

Run $M_1$ on input $x$ for $t$ steps.
If $M_1$ halted: run $M_2$ on $x$.
Otherwise:

Run $M_2$ on input $x$ for $t$ steps.
If $M_2$ halted: run $M_1$ on $x$.
Otherwise: halt.

The machine $M$ rejects an input $x,t$ iff one of the machines $M_1,M_2$ accepts $x$ within $t$ steps and the other one rejects $x$. So $M$ accepts all inputs iff $L(M_1) = L(M_2)$.


Multiway Cut question I am trying to understand Multiway Cut, and basically how the Multiway Cut works. I am searching google many hours to find a good example to understand. A good example that I am trying to understand is this:

http://crab.rutgers.edu/~rajivg/studentTalks/multiwayCut.pdf

What I cannot understand, and here is the point I need your help, is how did he go from slide 12 to slide 13? How the graph on slide 13 was produced? How do I choose A1*,A2*,A3* ??

The analysis of the approximation algorithm (join all min-cuts between a terminal and the contraction of the remaining terminals, excluding the heaviest cut) starts on slide 13. So there's nothing to compute, simply assume that $A^*$ is the optimal solution with cuts $A_i^*$ separating terminal $i$ from the rest of the graph. To see the argument spelled out more explicitly read e.g. chapter 4 of Vazirani's "Approximation Algorithms".


How can I find the Myhill-Nerode classes for the language A? I have the following task (no homework).

  Find all equivalence classes of the Myhill-Nerode relation of the language $$ \mathrm{A} \triangleq\{w \in \Sigma^{*} | w\text{ does not end with }01\}\,. $$

Because I have no Idea how I to find does classes -I know the theory, but I can't use it -.
So I build a DFA (what i should not do):

Now I know there has to be 3 different classes (because the DFA is minimized), but again, I have no idea how to find them.
I hope you can help me a little bit, because I write a test paper in 5 weeks and this will be a big Troublemaker.

Two strings $x$ and $y$ are in the same Myhill–Nerode class if they can't be distinguished by adding the same string onto the end of them. That is, they're in the same class if, for all strings $z$, either $xz$ and $yz$ are both in the language or neither of them is.

So, for example, the strings $00$ and $01$ are in different classes because we can distinguish then by adding $1$: $001$ is in the language and $011$ is not.  In fact, they're already distinguished by the empty string $\epsilon$, since $01$ is in the language but $00$ is not.

In your case, you can shortcut this because the notion of indistinguishability corresponds exactly to minimal automata: the classes are exactly the sets of strings that take you to each state of the automaton.


Ambiguous context free Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.

Your question is strange. If you do not know what kind of language you
have, the question may well be meaningless, as the concept of
ambiguity can only be defined with respect to a known system of
enumeration of the sentences of the language. There is none if the language is not Recursively Enumerable.

Thus it does not make sense to ask whether a language is ambiguous in
general.

I take this as an opportunity for a little survey of these types of definitions.

In your case, if you specified that your language is context-free (but
you did not), the question makes some more sense since CF languages
have at least one CF grammar, which can be used as reference rewriting
system to generate the sentences of the language (assuming you
restrict to leftmost derivations, as canonical representatives of
equivalence classes of derivations).

However, each CF language has actually an infinity of CF grammars
generating it, and ambiguity has to be defined with respect to a
single generation system. Hence the concept of ambiguity makes sense
for the language of a given CFG with respect to that CFG, but does not
make sense a priori for the langage alone.

However, computer science developed the concept of inherent
ambiguity.

  A CF language is inherently ambiguous iff all CF grammars generating that
  language are ambiguous.

It is however becoming common to say that a CF language is ambiguous
to mean that it is inherenlty ambiguous.

Notes:

Given any CF grammar G, it is trivial to give an ambiguous
CF grammar G' that generates the same language. So, what can be
interesting is not to know whether a CF language may have an ambiguous CF
grammar (that is always possible), but whether it has only ambiguous CF
grammars.
This refers only to CF grammars. It is possible that an inherently ambiguous CF language can be generated unambiguously by a grammar that is not CF. For example, I would conjecture that there is an inherenlty ambiguous CF language that can be generated by an unambiguous Tree Adjoining Grammar (TAG) (but I do not know whether it is true or easy to check).
This kind of knowledge organization framework can apply to other properties related to the generation or recognition process associated with a language. A good example is determinism of automata of a given family recognizing the language.
Precision is always important: a language may be inherently non-deterministic with respect to a left-to-right PDA recognizer, but not when the PDA recognizer is right-to-left.
This kind of framework, whether for ambiguity or other properties, can also be developed for other families of
languages and enumeration mechanisms (possibly up to some notion of
generative equivalence, such as the order of rule application in the
case of CF grammar derivations).

Hence your question should be better phrased as:

If I am given a language L that is Context-Free, is there any
technique to prove that it is not ambiguous.

It is even better if you say "... that it is not inherently
ambiguous".

Note that even there, there is the implicit assumption that you refer to the leftmost derivations of CF grammars.

In the case of CF languages and grammars, you have many answers that
you can find on the CS Theory site at the question Ambiguity in
regular and context-free languages.

In particular:

it is undecidable whether a given CF grammar is ambiguous (1962-63, Cantor - Floyd - Chomsky and Schutzenberger)
it is undecidable whether a given CF language is inherently ambiguous (Ginsburg and Ullian - 1966).


Computational complexity vs other complexities Complexities, such as time complexity, space complexity, communication complexity and sample complexity, are often used to analyze the performance of algorithms. As far as I know, time complexity and space complexity are collectively referred to as computational complexity.

Are there other common complexities in theoretical computer science? Is there any theory that can cover all these complexities?

I wouldn't call communication and sample complexities "common". Space and time complexities apply to all algorithms, but the other complexities only apply to certain classes of algorithms. Hence, only space and time complexities should be deemed "common" and thus no others deserve such description.

There isn't any theory that covers all these complexities.