Quicksort dual pivot or single I've seen to explanations for the quick sort algorithm.

One in which a pivot is chosen, and put into place, before both sides of the pivot are recursively pivot-sorted.

Another involved a more complicated solution involving two pivots which interchanged.

What are the benefits of either solution, why was the dual-pivot solution created? Is it faster?

Basically Dual-pivot Quicksort buys you two items:
The best case running time is $\Theta(n \log_3 n)$ instead of $\Theta(n \log_2 n)$ since each partition is the third part of the entire current range. Also, if one pivot is not good (it is close to one of the ends of the current range), there is a good chance that the second pivot will be better.


compilers and their inheritance If compilers have an inheritance of compilers(for example, a compiler needs to be compiled by another compiler, and that compiler needs to be compiled by another compiler, and so on) then if there is an inefficiency in one of the compilers up the line of inheritance(like the compiler's compiler's compiler's compiler), would the current compiler inherit that inefficiency?

The inefficiency in compiler would make the next compiler work slower, but the result of work will be the same.
So in next compiler you wouldn't even know about that inefficiency.


Why does using unary in subset sum problem result polynomial time complexity? From my understanding, the complexity of the algorithm is O(number of inputs * number of bits for input).
The number of bits in binary notation is obviously less than the number of bits in unary notation. Then why is it that for binary, complexity is exponential but for unary, it is polynomial?

EDIT: I think the binary time is still faster. It just appears to be faster in case of unary due to notations.
If x bits are used, then n has to be less than equal to x. So it becomes polynomial.
while in case of binary, it's obviously O(n*2^number of bits).
There might be something wrong in my explanation. Feel free add an answer to correct it.

Consider the following (silly) function cow, which accepts a number $n$:

def cow(n):
   k = 0
   for i in range(0, n):
       k =  k + 1
   return k

The loop takes $n$ steps, so the time needed for the function to complete on input $n$ is $\Theta(n)$.

However, the size of the input is not $n$ but rather $\log_2 n$ because computers represent numbers in binary. That is, if $b =
\log_2 n$ is the size of the input, then the complexity is $\Theta(2^b)$ (because $n = 2^{\log_2 n}$), which is an exponential algorithm when measured in size of the input $b$. If we measure in terms of $n$ then it is a linear algorithm.

If we represented numbers in unary then we would have $b = n$, i.e., it would take $n$ "units" (not "bits" anymore) to represent $n$. In this case the complexity would be $\Theta(b)$, a linear algorithm.


A data structure to do a specific lookup fast I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p_0$ to $p_{29}$ and their value is an integer between 0 and 5. I want to store these items in a data structure where I can do this lookup quickly: find the parameter with a given value for $(p_0, \ldots, p_{29})$.

All items that have $p_i$ less than or equal $x_i$.

So having 50 values $x_0$ to $x_{29}$ I run the above lookup and it returns all items that satisfy it. I used PostgreSQL and created indices for each of these parameters. Querying in PostgreSQL happens in ~20ms. I stored them in a Python list and did a simple [i for i in items if all(i['p' + str(j)] < n[j] for j in range(30))] and it takes ~250ms. By using 30 dicts each containing 6 sets for different values of each parameter and doing the lookup in dicts and intersecting sets I was able to each ~10ms (a bit memory consuming but not that much). Does anyone know about a better data structure to do this query faster? Memory is not an issue as long as it's below 2GB.

In formal language I'd describe it this way:
I have 30,000 records; each record contains 30 values, each in range 0..5:

type Record: array[1..30] of 0..5
var Store: array[1..30000] of Record

I need to find all records in the store, where each element is smaller than in the target one:

procedure Find(target: Record):
  for item in Store:
    if item[0]<=target[0] and item[1]<=target[1] and ... and item[30]<=target[30]:
      print item

I need to perform Find quick, and can preprocess the Store to make the lookups faster. What data structure and algorithm can I use?

Using SSE2 operations, you can save the entire dataset in 512 KB and search through it, with 4-core CPU, is less than 10 microseconds.

PCMPB+PMOVMSKB instructions will give you 16-bit mask made from 16 byte-wide comparisons. You need to combine two such masks as a<<16+b and make sure that result is all 0s.

Even faster approach is to make bitmap for each p[i]<k condition, overall you need 30*6=180 bitmaps. Each bitmap takes 30K/8=3.75 KB, overall 675 KB.

You need to AND-combine 30 maps corresponding to chosen x[i], i.e. AND-process 675/6=112.5 KB of data. With 128-bit SSE operations, this requires 7K operations, and on the same 4-core CPU, it's less than microsecond long.


Origin of the concept of types About the state of art that I'm running ahead of Type Theory I have the these questions all related about history of Types.

Where did the idea of Type come from? (It seems that all start when Russell and Whitehead propose a way to avoid the contradiction that we know today as Russell's Paradox, am I right?)
Before considering the type concept, was there something similar? (Maybe a refinement of a set, but I don't find a reference distinct of Russell).
Who was the first person to put it on formal terms? (Was Russell with this paper of 1908 or ?

Depends on how deep you want to go.  I believe Russell was the guy who introduced the concept in a specifically set-theoretic context, but the concept itself is as old as the hills, it's really the notion of universals and particulars expressed in a modern mathematical / computational form.  I wouldn't be surprised if Liebniz did something vaguely like types, if you look at his stuff in the right way.

You might have better luck at the History of Math and Science exchange.


When is splitting a collection coins two ways NP-complete? Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters).  In the first two problems, we want to know whether it is possible to divide the money in the jar equally between two people; in the third one, we're satisfied if the money can be divided almost equally.  What is the complexity of these problems?

$D = \{1, 2, 4, 8, \dots\}$.
$D = \{1, 2, 3, 4, \dots\}$.
$D = \{1, 2, 3, 4, \dots\}$ but we only require the two people to be given amounts $x$ and $y$, respectively, satisfying $|x-y|< 10$.

My main question is what sets $D$ lead to the problem being in P and what makes it NP-complete.

Problem 2 is the same as the NP-complete problem PARTITION. Problem 3 is also NP-complete, since we can always arrange all denominations to be multiples of 10 cents.

The most interesting case is Problem 1. If the jar contains in total $2S$ cents, then we are looking for a subset of the jar summing to $S$. If $S$ is odd then there is no solution unless the jar contains a 1 cent coin, in which case we take one such coin and put it aside (it forms part of the solution), and update the target sum to $S-1$. Is $S$ is even we do nothing. In both cases, the new target sum is even. The number of 1 cent coins which appear in a solution must be even, and so we can group the 1 cent coins in pairs, replacing them with 2 cent coins (if there is an odd number, we just throws the odd one out). Now we repeat the same procedure with the 2 cent coins, the 4 cent coins, and so on, until we either reach the target sum or find out that the target sum is not reachable. This algorithm runs in polynomial time.


In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations? I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree.

So, my question is: Why is it necessary to do both of them? What are we trying to really prove by doing them?

For one particular parse tree there are many possible derivations, depending on the order in which the expansions are done. In a sense, a parse tree represent all of the derivations you'd consider "the same" (as you state). It is easy to see that for a given derivation tree there is exactly one leftmost and one rightmost derivation, which in a sense also represent the set of the derivations you'd deem "the same".

For applications, you are interested in the parse tree as a representation of some underlying structure that has a specific meaning. For example, the parse tree of an expression describes the order in which operations are to be performed. If some string has several parse trees, there is no single meaning (the grammar is ambiguous), that is clearly useless.

Reconstructing a (hopefully the only) parse tree for a string is parsing, different parsing methods reconstruct leftmost or rightmost derivations.


Hash table: When is it suitable to use modulo power of 2? I am implementing a hash table that may need to grow and shrink as the number of stored keys varies. I have a hashcode function that uniformly hashes keys to positive 32-bit integers. The table itself will use a smaller array of approximate size M.

If I wanted to use the hash function to produce a value between 0 and P-1 (if P is close to M), can I use mod P if P is a power of 2?

What about using mod P, where P is a prime?

The exact size of the backing array is not that important only that it can hold enough buckets.

The reason why power of 2 is often used is because this can be implemented as a bitmask instead of a integer divide. Integer divides are pretty slow compared to other operation so they are often avoided by people trying to optimize data structures.


Analysis and classification based on data points I'm not sure if this is the correct stack exchange or correct tags, but my question is as follows:

I am working on a sort-of ratings system for players in a particular game. After allowing the ratings to develop for many games, I have set up a "database" (not sure if this is the correct term) for matches: a point in the database would consist of the score difference between the players (i.e if it's >0 player 1 won) and the rating discrepancy between the two players before this match.

The idea is to use this database in order to predict the score difference of a match that has not yet occurred: I measure the rating discrepancy between the 2 players, and lookup in my database for the score differences in games of a "similar" rating discrepancy, and based on these games I am able to predict, say, a rough probability of each score difference occurring in this match that has not yet happened.

I actually have two questions:

1) what is a good approach to using the database to predict the probability of each score difference, i.e what qualifies as a "similar" rating discrepancy, how do I deal with extreme cases where the rating discrepancy is very large and I have few data examples of such matches (should I relax my definition of "similar"?), etc. A bit of googling shows that maybe I am looking for something relating to data clusters.

2)how would I go about implementing an algorithm as above? are there good standard implementations of such classification algorithms? I am writing in C# if it makes a difference.

One option is to use the Elo rating system.  It is based upon some mathematical theory of the sort you are mentioning.

The Bradley-Terry model is another mathematical approach that may also interest you.  It assumes that each player has an (unknown) strength, which can be quantified as a real number, and the probability that Alice beats Bob is determined by some smooth function of the difference of their strengths.  Then, given the pairwise win/loss records, it estimates the strength of each player.

See also:

https://stats.stackexchange.com/q/6379/2921
https://stats.stackexchange.com/q/30976/2921
https://stats.stackexchange.com/q/15776/2921


Is a language containing set of binary numbers which are divisible by number N Regular? Let N be any positive integer, then is following language regular for every $N$?

$L$ = { $B_n : B_n(modN) == 0$ } where $B_n$ is binary representation of a number.

E.g, $L=\lbrace B_n : B_nmod31 == 0,B_n \ is \ a \ binary \ number \rbrace$ is regular? Will the language be regular for any positive number in place of $31$.

You can produce a finite automaton to recognize binary strings divisible by $N$ for any $N>0$. Use $N+1$ states, $s$ (the start state) and $q_i$, where being in state $q_i$ corresponds to having seen input $B$ which is congruent to $i\bmod N$.

The transitions are then easy enough: in state $q_i$ and seeing a $0$ input the machine would pass to state $q_k$, where $k\equiv 2i\bmod N$, since appending a zero to a binary string doubles the number represented. Similarly $\delta(q_i, 1)=q_k$, where $k\equiv 2i+1\bmod N$.

The start state is there solely to avoid the question of what number the empty string represents, and obviously $q_0$ is the final state.


Minimal set of rows and columns covering all non-zero entries in matrix Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns in $I$.

What I have tried

Create an intermediate column (between $s$ and $t$) for every column and row.

For every column, draw an edge from that column to $t$ with a capacity equal to the number of $1$s it has in it.

For every row, draw an edge from that row to $t$ with a capacity equal to the number of $1$s it has in it.

Take the cut between this intermediate column and $t$, calculate the entry with the most capacity, add that to set $I$.

For the selected row or column, remove all $1$s from that column and recalculate the network flow.

Continue to do this until the flow is $0$, i.e., all $1$s have been accounted for.

Examples
1 1 0
1 0 0
1 0 0

We would take column 1, and row 1 here.
1 1 1
0 0 0
0 0 0

We would take row 1 here.
Is there a better approach?

Your problem can be phrased as minimum vertex cover in a bipartite graph: there is a vertex for each row and column, and each non-zero entry contributes an edge. You can find a minimum vertex cover by finding a maximum matching; see Kőnig's theorem.


What does it mean that HDLs "explicitly include the notion of time"? I got onto the topic of HDLs (Hardware Description Languages) from a comment elsewhere on this site.

The Wikipedia article states, rather tantalizingly:

  One important difference between most programming languages and HDLs is that HDLs explicitly include the notion of time.

I tried to dig deeper in the article to better understand this statement, but I didn't get far.

One thing I did find was this great diagram of a flip flop, which certainly demonstrates the need to consider timing in hardware design.  Rather than dealing with explicit on/off states, you are also dealing with high/low voltage propagation.

Naively, though, my immediate thought was, "Huh?  All imperative languages include the notion of time.  Only declarative or functional programming languages could be said to exclude the notion of time, and only by certain specific interpretations."

I think there is a valid point being made here, though, and I would very much like to better understand it.  It's even stated to be an "important" difference.  :)

So, again, what does it mean that HDLs "explicitly include the notion of time"?  How does that distinguish them from programming languages in general from a CS standpoint?

Programming languages usually don't have a notion of time.  They describe how things are sequenced, but usually they don't go further.  When they do, that's relegated to the library part of the language, and it is to handle time computation or to handle real time measurement and delay.

HDL are used for two purposes: synthesis and simulation.  For the first purpose, there is no more use of time than for a programming language.  For the second purpose, time is inherently part of what is to be simulated.  You need to know after which delay $Q$ will change after a change of $R$, and after which delay $\bar Q$ will do the same.  The time here is thus not the real time, but a simulated one, which has no easy relationship with the real time during which the simulation will occurs.

Your circuit will be described in a VHDL-like syntax:

Q <= not (R or QBar) delay 1ns;
QBar <= not (S or Q) delay 1ns;

You can also write an oscillator, with no stable state:

Clock <= not Clock delay 5ns;

Time is thus present in the syntax of the language, and in its semantic as well (the language clearly states that $\bar Q$ will change 2ns of simulated time after $R$ does).


Any very user friendly resources on the Baum-Welch algorithm? I'd like to understand the Baum-Welch algorithm. I liked this video on the Forward-Backward algorithm so I'd like a similar one for Baum-Welch.

I'm having trouble coming up with good resources for Baum-Welch. Any ideas?

A simple web search leads to a whole lecture by Christopher Lee. I did not watch it entirely, but it seems to be a slow, thorough take on the algorithm with an example walk-through on paper similar to the video you link (if longer).


Proof that no O(n) multiplication algorithm exists For the multiplication of two $n$ digit numbers, the best known algorithm has complexity $O(n \log n)$. Has it been proven that this is the best possible, or that an algorithm $O(n)$ is not possible?

There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.


Complexity of inverting a diagonal matrix What is the complexity of inverting a $n \times n$ diagonal matrix?
From what I learn in algebra, the inverse of a diagonal matrix is obtained by replacing each element in the diagonal with its reciprocal.
So is it correct to say that the complexity of inverting a diagonal matrix is $\mathcal{O}(n)$?

It's unclear what $n$ is in your question. If your matrix has dimensions $n \times n$ and your model of computation allows you to perform
basic arithmetic operations in constant time then, yes, computing the inverse matrix takes $O(n)$ time.


How to discuss coefficients in big-O notation What notation is used to discuss the coefficients of functions in big-O notation?

I have two functions:

$f(x) = 7x^2 + 4x +2$
$g(x) = 3x^2 + 5x +4$

Obviously, both functions are $O(x^2)$, indeed $\Theta(x^2)$, but that doesn't allow a comparison further than that.  How do I discuss the the coefficients 7 and 3. Reducing the coefficient to 3 doesn't change the asymptotic complexity but it still makes a significant difference to runtime/memory usage.

Is it wrong to say that $f$ is $O(7x^2)$ and $g$ is $O(3x^2)$ ?
Is there other notation that does take coefficients into consideration? Or what would be the best way to discuss this?

Big-$O$ and big-$\Theta$ notations hide coefficients of the leading term, so if you have two functions that are both $\Theta(n^2)$ you cannot compare their absolute values without looking at the functions themselves.  It's not wrong per se to say that $7x^2 + 4x + 2 = \Theta(7x^2)$, but it's not informative because $7x^2 + 4x + 2 = \Theta(3x^2)$ is also true (and, in fact, it's $\Theta(kx^2)$ for any positive constant $k$).

There are other notations you might want to use instead.  For example, $\sim$ notation is a much stronger claim than big-$\Theta$:

$\qquad \displaystyle f(x) \sim g(x) \iff \lim_{x \to \infty} \frac{f(x)}{g(x)} = 1$

For example, $7x^2 + 4x + 2 \sim 7x^2$, but the claim $7x^2 + 4x + 2 \sim 3x^2$ would be false.  You can think of tilde notation as $\Theta$ notation that preserves the leading coefficients, which seems to be what you're looking for if you do care about the leading coefficient of the dominant growth term.


Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem.
The professor has used a while loop to find the root of the element, while I have implemented it using a recursive approach.
Which approach is better in terms of space complexity, and scalability for large arrays?

//Quick union method for Union-find algorithm. Lazy approach

import java.util.Scanner;

public class QuickUnionUF {

    private int [] id;
    public QuickUnionUF(int N)
    {
        id= new int[N];
        for(int i=0; i<id.length;++i)
        {
            id[i]=i;
        }
    }

    public int root(int p)
    {
        if(id[p]==p) return p;
        else return(root(id[p]));
    }

    public boolean isConnected(int p, int q)
    {
        return (root(p)==root(q));
    }

    public void union(int p, int q){
        int proot= root(p);
        int qroot= root(q);

        id[proot]= qroot;
    }

}

For the root function, the professor has used -

public int root(int p) {
        while (p != id[p])
            p = id[p];
        return p;
    }

https://algs4.cs.princeton.edu/15uf/

The time complexity for both versions is exactly the same. It is linear in terms of the distance between $p$ and the $root$.

Space complexity is a little different.
It's easy to see that the iterative version will use constant space.
The recursive function will use linear space on paper (each recursive call must store some information about the current function call, for instance in a call stack via stack pointer).

This might give problems, if the distance between $p$ and $root$ is very long. Image a tree with $id[0] = 0$ and $id[p] = p - 1$ for $p > 0$. Then finding the root for a large element $p$ might exceed the allocated stack and crash the program.

However in practice the situation might look a bit different. Depending on the programming language, the compiler/interpreter, configuration this linear space can be optimized to constant space. The concept that allows such an optimization is called tail recursion. E.g. gcc -O3 will generate exactly the same assembler code for both versions: example. But be careful, not all languages, compiler / interpreter have these optimizations implemented.


Partial type inference for dependent types I'm looking for resources on (partial) type inference for dependent types.

For example there could be a type inference scheme that fails if the term doesn't have a principal type, or a scheme that makes some choices and infers non-principal types.

I'm also not sure how to integrate type inference into constraint-based type checking.

Are there any papers on this?

I recommend to look at (1) first, which might be the canonical early work on this problem and lead to the ATS programming language. (2) is a recent work on the same problem.

As to using constraints for type inference, (3) is probably the canonical reference.

H. Xi, F. Pfenning, Dependent Types in Practical Programming.
T. Terauchi, Dependent Types from Counterexamples.
F. Pottier, D. Remy, The Essence of ML Type Inference.


Relaxed Bin Packing Problem The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin.

Is there an efficient way of doing this? Is there a way that will assure there is approximately the same amount in each bin? Does having a good guess at the probability distribution of the masses help?

More explicitly:

I have $q$ objects $\{o_1...o_q\}$, each has a size $w(o_i) \in \mathbb{N}$.

I need to find a collection of $n$ disjoint bins $B = \{b_1...b_n\}$ containing the objects such that

$$\forall b_i \in B: \sum_{o \in b_i}w(o) > m$$

for some $m$. When it is possible that is.

The problem is NP-complete because it is in NP and captures the partition problem with $n = 2$ and $m = \frac12 \sum_{i = 1}^q{w(o_i)} - \frac12 \min_{i}w(o_i)$. If an equal weight partition exists, then the items can be packed in two bins each of weight $\frac12 \sum_{i = 1}^q{w(o_i)}>m$. If it doesn't, then one of the two bins would have weight at most $m$.


Confused about beta-reduction/shifting in untyped $\lambda$-calculus with de Bruijn terms In Types and Programming Languages, the family of sets of terms with de Bruijn indices in the untyped $\lambda$-calculus is defined in this way:

Let $T$ be the smallest family of sets $\{T_0, T_1, T_2, ...\}$ such that

$k \in T_n$ whenever $0 \le k \lt n$;
if $t_1 \in T_n$ and $n \gt 0$, then $\lambda. t_1 \in T_{n-1}$;
if $t_1 \in T_n$ and $t_2 \in T_n$, then $(t_1\ t_2) \in T_n$.

The $\beta$-reduction operation is then defined as $(\lambda. t_{12})\ v_2 \rightarrow\ \uparrow^{-1}([0 \mapsto\ \uparrow^1(v_2)]t_{12})$, where $\uparrow^d(t)$ is the function to add $d$ to the indices of all free variables in $t$. By the definition of the $\uparrow$ function, if $t \in T_n$, then $\uparrow^d(t) \in T_{n+d}$. Substitution is defined like so:

$[j \mapsto s]k = s\ $if $k = j; k$ otherwise
$[j \mapsto s](\lambda. t_1) = \lambda. [j+1 \mapsto\ \uparrow^1(s)]t_1$
$[j \mapsto s](t_1\ t_2) = ([j \mapsto s]t_1\ [j \mapsto s]t_2)$

I can't seem to get these definitions to work properly in manually reducing the term $((\lambda. 0)\ (\lambda. 0))$ (i.e. the identity function applied to itself). Here are the steps I've gone through in attempting to apply the $\beta$-reduction rule; I'll add a subscript to each term indicating which set in $T$ I think the term is in, so e.g. $(\lambda. 0_1)_0$ is an abstraction of $0 \in T_1$, and the abstraction itself is in $T_0$. I believe that if done properly, $((\lambda. 0_1)_0\ (\lambda. 0_1)_0)$ should reduce to $(\lambda. 0_1)_0$.

$(\lambda. 0_1)_0\ (\lambda. 0_1)_0$
(by def. of $\beta$-reduction) $\rightarrow\ \uparrow^{-1}([0 \mapsto\ \uparrow^1((\lambda. 0_1)_0)] (\lambda. 0_1)_0)$
(by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}([0 \mapsto (\lambda. 0_2)_1] (\lambda. 0_1)_0)$
(by def. 2 of substitution) $\rightarrow\ \uparrow^{-1}(\lambda. [1 \mapsto\ \uparrow^1((\lambda. 0_2)_1)]0_1)$
(by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}(\lambda. [1 \mapsto (\lambda. 0_3)_2]0_1)$
(by def. 1 of substitution) $\rightarrow\ \uparrow^{-1}(\lambda. 0_1)$

Now I've worked myself into a corner - $\uparrow^{-1}(\lambda. 0_1)$ should reduce to $(\lambda. 0_0)_{-1}$, which is nonsensical. I also haven't actually performed any substitutions, which seems like it must be incorrect. Am I misapplying these definitions somehow?

I figured it out - I was messing up the $\beta$-reduction in the first step by applying the substitution to $(\lambda. 0_1)_0$ instead of just $0_1$. This is the correct sequence of reduction steps:

$(\lambda. 0_1)_0\ (\lambda. 0_1)_0$
(by def. of $\beta$-reduction) $\rightarrow\ \uparrow^{-1}([0 \mapsto\ \uparrow^1((\lambda. 0_1)_0)] 0_1)$
(by def. of $\uparrow$) $\rightarrow\ \uparrow^{-1}([0 \mapsto (\lambda. 0_2)_1] 0_1)$
(by def. 1 of substitution) $\rightarrow\ \uparrow^{-1}((\lambda. 0_2)_1)$
(by def. of $\uparrow$) $\rightarrow\ (\lambda. 0_1)_0$


Kleene closure, concatenation problem If $L_1 = \emptyset$ , $L_2= \{a\}$
then what is $$L_1\cdot L_2^* \cup L_1^*$$

The answer given is $\{\epsilon\}$ but I think it should be $\{\epsilon,a\}$.
My Approach :
$L_1^* = \{\epsilon\}$
$L_2^* = \{\epsilon,a\}$
$L_1\cdot L_2^* = \{\epsilon,a\}$
$L_1\cdot L_2^* \cup L_1^* = \{\epsilon,a\}$.

Where's my mistake?

For any language $L$, $$\emptyset⋅L=\emptyset$$.

Therefore,
$$L_1\cdot L_2^* = \emptyset \cdot L_2^* = \emptyset$$

And thus $$L_1\cdot L_2^*\cup L_1^* = \emptyset \cup L_1^*= L_1^* = \{\epsilon\}$$.


Which memory holds the copy of the program that is to be executed? I don't know whether it is RAM or cache; I can say that isn't the registers since their memory capacity is very small.

It's the RAM.

But further, in order to enhance speed, the CACHE stores a shadow of the RAM content, so it may hold a copy of the program as well (similarly, the RAM has a copy of the program that previously was stored on the hard-drive).

Eventually, parts of the code goes into the CPU and gets stored in one of its registers (not the general purpose ones, but rather some designated registers you have no access to; just think about them as flip-flops). From that point, the program is being executed, one instruction at a time, by the CPU hardware.


Why exactly are Regular Languages decidable? I am trying to revise for my exams and going through my lecture slides and recordings, my lecturer didn't really give a clear example of why Regular languages are decidable.

She mentioned that it was because Regular Languages can be represented in Finite Automata, and can be classified as a subset of regular languages. As finite automata are special kinds of Turing Machines with bounded tapes in which you don't write anything, and just gave the definition of what decidable is, which in her words are "a Language L is Turing-decidable if there exists a TM that can decides it".

I sort of what she is getting at, but it seems extremely vague and over generalised that I don't fully understand what she is saying.

I will try to explain it without a formal proof,

Imagine a turing machine where you have input written over a tape you can only but read only the input and not modify it. In addition you can only visit the length of the tape where the input is written. This gives you a finite number of configurations to traverse. Thus after a finite number of moves you can $Decide$ whether or not the word word belongs to the input language ; making regular languages decidable.


Which languages are recognized by one-counter machines? Counter machines with two or more counters are typically shown to be equivalent to Turing machines in courses on the theory of computation.  However, I have not seen a formal analysis of which languages can be recognized by a one-counter machine.  Are these languages equivalent to the context-free languages (perhaps by some clever construction relating them to PDAs), or are they an entirely different class of languages?

A one counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). Languages recognized by one counter automata form a proper subset of the context free languages.

For example a 1-counter automata can recognize the language $\{a^nb^n\}$ which is not regular, but cannot recognize the language $\{a^nb^ma^mb^n\}$ which is context free and can be recognized by a 2-counter automata, too.

If k-DCA is a deterministic k-counter automata, and k-NCA is a nondeterministic k-counter automata, then we have the following proper inclusions:

DFA (regular languages) $\subset$ 1-DCA  $\subset$  2-DCA

1-DCA $\subset$ 1-NCA

If we don't allow $\epsilon$ transitions (switch to real time) then k-DCA $\subset$ k'-DCA for k < k'.

Just for completion: there are languages that are context free but cannot be recgnized by counter automatas (k-DCA with k $\geq$ 2) (for example $\{ww^R\}$), and languages recognized by counter automatas that are not context free (for example $\{a^nb^nc^n\}$). A counter automata (in particular a two counter automata) can be Turing complete only if its input and output are properly encoded (see Wikipedia entry for details).


Proof for optimal interval scheduling using a Greedy Approach You are given a set of n jobs, where each job j is associated with a size
  s(how much time it takes to process the job) and a weight w(how important the
  job is). Suppose you have only one machine that can process one unit of jobs per
  time slot. Assume all jobs are given at time t = 0 and are to be processed one by one using this machine. Let C > to be the time that job j is completed. The goal is
  to find a schedule (of all the jobs) that minimizes the weighted completion time, i.Σ(j=1 to n) wj * CjApproach 1: Process Jobs according to the highest weight firstApproach 2: Process jobs in ascending order of their sizeApproach 3: Process jobs in descending order of their density (w/s)

So basically, I need to find out which approach is optimal and why the other 2 wouldn't work. My understanding is as follows:Approach 1 wouldn't be optimal if the higher weights(w) have a greater size(s).Approach 3 wouldn't work if the weight was equal to the size in case of all the jobs. If w=s for all the jobs, you wouldn't be able to determine what to chose first.Hence, my answer is that Approach 2 would be the optimal choice out of the 3 as it focuses on minimizing w*c. Is this answer correct? Is there a better way to prove why approach 2 is the optimal choice in this question?

Let's consider two jobs in the sequence you obtained:

$A$, of weight $w_A$ begins at $t_0$ and finish at $t_0 + s_A$
$B$ coming just after $A$, of weight $w_B$ begins at $t_0 + s_A$ and finish at $t_0 + s_A + s_B$

If we compute only $K_{A, B}$ the contribution of $A$ and $B$ in $K = \sum_j w_j C_j$:

$K_{A, B} = w_A (t_0 + s_A) + w_B (t_0 + s_A + s_B)$

If A and B are inversed in the sequence, we have $K'_{A, B}$:

$K'_{A, B} = w_A (t_0 + s_A + s_B) + w_B (t_0 + s_B)$

The difference is:

$\Delta K_{A, B} = K'_{A, B} - K_{A, B}$

$= w_A s_B - w_B s_A$

$= (w_A/s_A - w_B/s_B) \times (s_A s_B)$

The switch should be done if and only if $\Delta K_{A, B}$ is negative in order to minimize $K$. Only the approach 3 provides you a sequence where no more switch is worth.

If two jobs have the same $w/s$ ratio, just take them in any order, the final $K$ would remain unchanged.


hardware interrupts and context switch I have recently studied about interrupts and context switch i have read that the hardware interrupts cause the interrupt service subroutine to execute for this i read  mixed articles saying that there no need for a context switch to kernel mode and some say we need a context switch to kernel mode from user mode do we need a switch to kernel mode in case of hardware interrupts

I think the answer partially intersects that of Do system calls always means a context switch?: it depends on the exact definition of "context switch". On most CPUs, an interrupt is not serviced in user mode but rather in a more privileged mode (IRQ mode on ARM, on x86 the IDT can specify the ring level). This is necessary because simply clearing the interrupt or determining its source requires accessing hardware registers (which by definition user mode cannot in general). That being said, the OS does not need to run the entire ISR in a privilege mode. Typically in a microkernel, an IRQ will be added to a queue and processed by a (user space) driver.

So an interrupt implies a privilege switch, which implies some amount of context switching (saving registers for example) but not necessarily a full process switch, depending on the architecture and the kernel.


Huffman tree and maximum depth Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?

Huffman coding (asymptotically) gets within one bit of the entropy of the sequence.  This means that if you calculate the entropy of your symbol frequencies, you will be (asymptotically) within one bit of the average length (i.e. height) of your code.  You can use this average to bound the longest length (on average), or you can use combinatorial methods to get determinsitic bounds.


Prove that if a problem L can be decided in polynomial time, then L ≤p L' for any other problem L' So we know that there exists a Turing Machine $M$ and a polynomial $T$ such that:

$M$ halts on all inputs within at most $T(|x|)$ steps
If $x$ is in $L$ then $M$ accepts $x$
If $x$ is not in $L$ then $M$ rejects $x$

We need to show that for any other problem $L'$, there exists a polynomial time computable function $f$ such that for all $x$, $f(x)$ is in $L'$ if and only if $x$ is in $L$.

I imagine the answer is simple but I'm stumped.

We show a karp reduction from $L$ to any other language $L'$, as long as $L'\notin\{\Sigma^*,\emptyset\}$.

The reduction proceeds as follows. Since $L'$ is non-trivial, there exists $x,y$ such that $x\in L'$ and $y\notin L'$.
Given input $w$, the reduction runs $M$ on $w$ (which takes polynomial time). Then, if $w\in L$ the reduction outputs $x$, and if $w\notin L$ it outputs $y$.

Proving correctness is trivial.

As @dkuper states, this is simply not true if we allow $L'$ to be trivial. However, it is a common mistake to ignore these end-cases in exercises (which I assume this is).


Prove that a language is not regular with process of elimination When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular.

Easiest way to prove that a language is regular, is just by making an automaton for it. But if the automaton is not regular, you can't just say that it's not regular because you couldn't build an automaton for it.

So I am wondering, how to prove that a language is not regular the simplest way?

Given language:

$$ L = \{a^n b^n | n > 0\} $$

Definition: The language accepts series of a's and b's where the amount of as equals to the amount of bs. This is not a regular language.

How can you prove that it's not a regular language?

From what I remember (I didn't understand it much), you had to take a sub-langauge of that language, and mark it as W

So $$ W = \{a^i\} $$

Then select 2 words from W and mark them as w1 and w2

$$ w1 = a^i $$
   $$ w2 = a^j $$

where i != j

And then I don't really remember what to do.

A simple technique is using the pumping lemma:

For any regular language $L$ there exists an integer $n$ such that for all $x \in L$, with $|x| \geq n$ there exists $u,v,w \in \Sigma^*$, such that,

$x = uvw$
$|uv| \leq n$
$|v| \geq 1$
for all $i \geq 0: uv^iw \in L$

Assumption: Suppose your language is regular.

Consider $s = a^nb^n$. Clearly $s \in L$ and $|s| \geq n$. We get that $uvw = a^nb^n$ and we know that $|uv| \leq n$, i.e $v$ can only contain $a$'s and since $|v| \geq 1$ it must contain at least one $a$. According to the last condition of the pumping lemma, $uv^0w \in L$ but this is clearly not the case. We now have a contradiction as we assumed the language to be regular:

The assumption must be wrong implying non-regularity of the language


Why is this not a regular language So I recently had a problem where I had to create a regular language. After consulting my professor on my solution he told me it was close to correct but to check my definition of a regular language. I am somewhat lost on why my solution is not regular?

From my understanding it meets the requirements of being a right regular language since there is only one non-terminal on the right side of the expression and the non-terminal is the rightmost symbol on the right side of the expression. Are pipe symbols not allowed?

The derivation $T_1 \to U_1$ is not right-regular.  It does not fall into the three allowed categories of rules.  See Wikipedia on right-regular grammars.  If you have a non-terminal on the right-hand side, it needs to be preceded by a terminal.


Prove that $L_1 = \{\, 0^m 1^k 2^n \,\vert\, \lvert m - n \rvert = k \,\}$ is not regular using Pumping lemma I have been trying to understand Pumping lemmas for a while now, I am doing this exercise and I think that the pin has finally dropped. However, I am unsure if I am doing it even remotely correctly. I will briefly explain my attempt and thus my solution. Thereafter I would discuss a few points that are not as clear to me just yet. The exercise is the same as in the title. Here is my solution, but in-case you have forgotten:

Prove that $L_1 = \left\{\, 0^m 1^k 2^n \,\vert\, \lvert m - n \rvert = k \,\right\}$ is not regular using Pumping lemma

So, in order to show that a language is not regular, we first must assume it to be regular (in-order to be able to use pumping lemma). If $L_1$ is regular, then there exists a constant $n$ such that  $ s \in L_1 $  and $ |s| \ge n$ implies that there is a string $xyz$ satisfying

$s = xyz$
$ |y| \ge 1 $ and $ |xy| \le n $
$xy^iz \in L1 $ for all $ i \ge 0 $

We'll try to extract a contradiction. This is how I did it
I first create a string such that $ m + k = n $, my string was $0^1 1^1 2^2$ or just $0 1 2 2 $ I then split this string into three parts $ x y z $ so that $x = 0 \\ y = 1 \\ z = 22$

I then selected $ i \Rightarrow 2 $ which gives us , by the third rule, $ xy^2z  $. This gives us the string
$ 01122 \notin L1 $ because $1 + 2 \neq 2 $

That is my solution, I hope you could understand it. Now to my discussion points:
As you see, I have provided a contradiction,  which should be enough. However, what I also want to know is that in other exercises , say $\{\, a^n b^n \,|\, n \ge 1 \,\}$ you select a Pumping length $P$ and then typically get a string that is $a^p b^p$ i.e say that $ P = 3 $ you'd get $aaabbb $  AND then you divide into strings, but since the powers are all different in my exercise, picking a $P$ would not be as helpful, right?

Is it possible to select a Pumping length $P$ here too? Do I need to check the other conditions as well? As I understand it, a language is proven non-regular if it can't satisfy all of the requirements at the same time.

To clarify the question, when I meant 'how do I apply $P$'? I meant, how do I apply to the already existing powers ($m$, $k$ and $n$). Do I simply attach P to each power which would make it $ 0^{PM} 1^{PK} 2^{PN} $ ? A follow-up question: When I select $P$, must I then also select $M$, $K$ and $N$? So say I select $ P = 3 $ , should I also select $M = 1$, $K = 1$ and $N = 2$?

Thanks to the guy down under I know understand how to select a string ($ 0^p 1^p 2^2p $) for instance. But, then I don't know how to split the string. Can do it like this:

$x= 0^r$ , $y=0^{p-r}1^t$ and $z = 1^{p-t}2^{2p} $? Would this string be in the language ? I assume it would be as $xyz = 0^p 1^p 2^{2p} $ BUT Idk, I might be doing it all wrong

Then if I select $i = 2$ so $xy^2z$ I would get $xy^2z = 0^r 0^{2p-2r} 1^{2t} 1^{p-t}2^{2p} = 0^{2p-r}1^{p + t}2^{2p} \notin L$ Thus our contradiction, is this correct thinking then?

To answer the guy below:
Assume $L$ is regular, then there exist a constant $p$ such that $ s \in L$ and $|s| \ge p$ implies that there exist string $xyz$ satisfying following:
$1) s = xyz$
$2) |y| \ge 1$ and $|xy| \le p $
$3) xy^iz \in L$ for very $i \ge 0$

(Which answers your first question)
We pick our string $s = o^p 1^p 2^{2p}$ as the property of a string in a language must be $m + k = n  $ $  (p + p = 2p)$
We then split the string into three parts $xyz$ , I am going to split them differently to you. $x = 0^p$ $ y = 1^p $ and $z = 2^{2p} $ if we then select $ i = 2$ we get  $xy^2z = 0^p 1^{2p} 2^{2p} \notin L $ BECAUSE $ 1 + 2 \neq 2$

For your choice of $s=0^11^12^2$, the pumping lemma might not apply. Remember, assuming that the language is regular means that there is an (unknown) integer $p$ such that the pumping lemma applies to every string of length $p$ or more. You don't know what $p$ is: if it were, say, 6 then since $|s|=4$ the PL simply wouldn't apply to your string and you could draw no conclusion.

That's why the strings chosen for pumping almost invariably involve $p$: it's there to assure that no matter what $p$ was, the pumped string would be at least $p$ characters long. For your example, you could choose $0^p1^p2^{2p}$ or $0^p1\,2^{p+1}$ or $0^p2^p$ even something like $0^{p^2}1^{2p+1}2^{(p+1)^2}$.

Here's what a PL proof of this result looks like, with some bits for you to fill in: Assume the language $L$ is regular. Choose $s=0^p1^p2^{2p}\in L$, where $p$ is the integer of the pumping lemma (why can we say the PL applies to $s$?). Then if we write $s=xyz$ as in the PL, we'll have $y=0^t$ for some $0<t\le p$ (why?) and then $xy^2z\notin L$ (why?), a contradiction (why?).

The proof without the PL is an example of a more or less common idiom: using closure properties. If $L$ were regular, then $L\cap 0^*2^*$ would be also, since regular languages are closed under intersection. However
$$
L\cap 0^*2^*=\{0^n2^n\mid n\ge 0\}
$$
(since we set $k=0$ when doing the intersection) but we know that that language isn't regular, so we have a contradiction and hence $L$ must not be regular.


Select the maximum number of links to satisfy per-link constraint. How to prove is NP-hard? I asked, incorrectly, my previous question here. I would like to thank D.W. for his answer though. He answeres that the problem is polynomial time solvable. The thing is that the cited paper shows that it is NP-hard. So I corrected my question. But I don't understand, am I missing something? In the paper, as shows the figure (page 2, right column in the paper), the authors says:

They show that that problem is NP-hard.

So here is the new question.

Instance: A matrix of size $n\times n$ of non-negative real numbers $\mathbf{G}=\left[g_{ij}\right]$, a positive number $k\le n$, and a positive number $\tau$ and a positive number $\epsilon$.

Question: Is there a subset $S$ of $\{1,\ldots,n\}$ of cardinality $|S|\geq k$ such that

$$\dfrac{g_{ii}}{\epsilon-g_{ii}+\sum\limits_{j\in S}g_{ij}}\geq \tau,\text{ for all } i \in S.$$

Can you see a simple, direct reduction from an NP-hard problem?

Note.  This problem is studied in wireless communication where the set represents links in a wireless network, the $g_{ij}$ represents the powers and the constraint represent a quality of service guarantee.

I believe a more general problem is proven NP-hard, see for example paper, but the reduction is very hard for me.

Even when each entry of G is in {0,1}, that is W[1]-hard by reduction from independent set:

$\mathbf{G}$  =  adjacency matrix + identity matrix    and    $\tau = 2$    and    $0 < \epsilon < 1/\hspace{.02 in}2$    .


Average number of comparisons to locate item in BST This is a GRE practice question.

If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (nodes) in the tree chosen at random?

(A) 1.75

(B) 2

(C) 2.75

(D) 3

(E) 3.25

My answer was 3 because $n=8$ and $\lg(n)$ comparisons should be made, and $\lg(8) = 3$. But the correct answer is 2.75. Can someone explain the correct answer? Thanks!

Recall, how expected value is defined. You count the for every element $X$ in the tree the number of comparisons it takes to locate it, say $C(X)$. Then
$$E[\text{# of comparisons}]=\sum_{X\in\{A,\ldots,H\}} p_X \cdot C(X),$$
where $p_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the average over the $C(X)$s.


How to compare two circular sequences in linear time? We have two circular sequences, which means there is no start or end in the sequences, how to test if two sequence are equal or not in linear time? I have two circular sequences of E. Coli bacteria with length (4,639,221). I thought about attaching two sample of the first sequence and find the other one in it in linear time, but I was looking for a better idea, using a suffix tree is a suggestion that I think works for this problem.

Start with computing the lexicographlcally least circular substrings$^1$ of the both circular sequences and then compare them directly.

Alternatively you can check for the substring $A$ (the first seqience) in the string $BB$ (a concatenation of $B$, the second sequence) circular sequence with itself) using for example the KMP$^2$

You might also be interested in the application of the Suffix Trees (also Suffix Arrays) and this thesis reviewing the applications to DNA sequences.

$^{[1]}$(described in K. S. Booth. Lexicographically least circular substrings.
Inf. Process. Lett., 10(4/5):240-242, 1980., and here
$^{[2]}$(Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt,  SIAM J. Comput., 6(2), 323–350. Fast Pattern Matching in Strings


Under which conditions a given program is deterministic on x86_64 machines? Given a certain x86_64 "vanilla" binary, without micro-architecture instructions, which can therefore be executed by any x86_64 computer, what are the conditions for the result to be deterministic ?
Can we assume that without parallelization, without the use of entropy-generating instructions, the result will be "bit-perfect" on different CPU models ? If not: why ? Can the floating point implementation from different CPUs change the results ?
By deterministic, I mean the same inputs will always produce the same outputs. I also assume inputs are what we classically assume to be inputs: parameters of the programs that can be fully controlled by the user like what we can pass as command line parameters, for example.
To be clear, I'm not talking about the program generation, or the use of specific instructions on different micro-architecture, or scheduling differences, I'm wondering about the "best case scenario": is this best case scenario reproducible, and can we ensure some program will be reproducible ?

I don't have all the details, but I think the conditions are not easy to identify.  I am aware of several categories of challenges:

Many instructions may have undefined behavior (e.g., the opcodes are reserved, or the spec does not define their behavior for some inputs), and thus it is possible that their behavior might vary on different CPU models.  For instance, many instructions specify that some aspects of their effects are undefined, e.g., the effect on some flag bits may be undefined.  As another example, SHLD says that the contents of the destination operand is undefined in certain cases.

There are certain instructions that explicitly perform I/O or read external data: e.g., IN, OUT, RDTSC, RDTSCP, RDRAND, RDSEED, etc.

Concurrency can cause nondeterminism, so you would have to rule out all associated instructions (e.g., LOCK).  Also I think there is a lot of nondeterminism in the memory model when there is any concurrency or shared memory.  So, you have to ensure that no other process/thread/etc. has access to any shared memory.  You'll also need to make sure that the program does not make a system call to the OS to initiate DMA.

System calls or interrupts (e.g., the INT, SYSCALL, SYSENTER instructions) might not have deterministic behavior.

I'm not sure, but I suspect reading machine state might have nondeterministic behavior, e.g., reading the machine status word, global descriptors, reading timers and performance counters (e.g., RDPMC), CPUID, model-specific registers (RDMSR), etc.

Supervisor-level / kernel-mode instructions are complex to analyze and I don't know whether they will be deterministic.  If you want to ensure determinism I would suggest you ensure the code runs in user mode (e.g., ring 3).  For instance, I don't want to think about instructions like VMLOAD, VMRUN, modifications to the page tables, etc.

The initial state of memory before it is written to is not defined and thus any program that reads from uninitialized memory may trigger nondeterministic behavior.  On the other hand, many operating systems zero out pages before handing them to the program, which eliminates this issue.

This is a complex topic and I wouldn't be surprised in the least to discover that I have missed other important challenges.
I don't know whether floating-point arithmetic is guaranteed to be deterministic and bit-for-bit identical on all platforms.
I think it is plausible that, given enough effort, you could come up with a subset of x86 instructions and an initial state for the process where, if the process only executes those instructions, its behavior will be deterministic.  However, coming up with this subset might be quite tricky and require a lot of time with the Intel manual.  Enforcing that the process only executes instructions from this subset will be quite challenging, given the ability to execute self-modifying code and runtime-generated code.  It is also not clear how you will deal with instructions where some of their results are undefined.  For instance, it's not clear how you'll deal with instructions that leave some of the flags undefined (and there are many of them), as there is a risk that a later instruction reads one of those flags whose value is undefined, and this could introduce nondeterminism (the spec makes no promises that undefined values will be a deterministic function of the inputs you care about).  So, I suspect ensuring determinism at the x86 level would be a non-trivial project.
If it is helpful, I know of some efforts to enforce determinism in the context of higher-level programming languages, where the enforcement becomes easier; you could ask a separate question about that, if it is of interest.


Computability of Kolmogorov Complexity Fix a universal Turing machine $M$.

Let $A^*=\{0,1\}^n$ be the set of all binary string of length $n$.

Determine the Kolmorogov complexity $K(x)$ of each $x\in A$, w.r.t. $M$.

Just for a matter of simplicity assume that $K(x)'=\min(|x|,K(x))$.

Let $B^*=\{0,1\}^n$ be the set of all programs $y\in B$ of $T$: $x= M(y)$.

Now, suppose a parallel machine $M_p$ that can run each program $y\in B$ for each element in $A$, in parallel. So we can get the length of all the programs $y$ whose machine ended with the right string $x$, and take the minimum as $K(x)'$.

So, should I assume that the non-computability is due to the fact that some machines that has not ended jet whose inputs $y$ are less than the current minimal program  will eventually halt? What's the probability of this?

Also, maybe a measure of complexity should include a minimal length with a probabilistic confidence? Say $P(K(x)\geq l)\geq p$?

That's right. You can run all machines in parallel and you'll find shorter and shorter descriptions, but at some point there will always be a shorter program still running, for which you can't prove that it won't halt with $x$ as output.

The probability you describe (of a program not halting, assuming some distribution on inputs) is the complement to Chaitin's omega: the probability that a program will halt. Of course, Chaiting's omega is also not computable and the best way we have of approximating it, is just by running all programs in parallel and summing the probabilities for the ones we've seen halting.

If you start with a probability distribution on outputs, the probabilities have different bounds. If you take a uniform distribution on strings of length $n$, then as $n \rightarrow \infty$, the proportion of strings compressible by more than a few bits is negligible, ie. $K(x) \approx |x|$ with near certainty for large $n$. If you take the universal distribution, then every computable pattern will appear in your string with some probability.


maximum bipartite matching I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that ﬁnds a maximum-sized subset of the rooks such that if we leave this subset on the chessboard and remove all other rooks, then no two rooks attack one another. (Two rooks are said to attack one another if and only if they are either in the same row or in the same column with no other intervening rooks between them.)

My idea for solving this problem is to consider a bipartite graph (X,Y) where X is the rows in the chessboard and Y is the columns. if a row and column have a rook placed at their intersection, then there is an edge between the those vertices from x to y. This can be converted into a maximum flow network and the value of max flow is the max matching.

In order to find a polynomial time algorithm i can run maybe BFS.

I wanted to know that if i build my solution on this idea shall it be correct. Is there a better algorithm (polynomial in m and n)?

Any help is appreciated.

As you mention, your problem is finding a maximum matching in an unweighted bipartite graph. There are several polynomial time algorithms for solving this problem. You can read about some of them on the Wikipedia page.


Visualized definition of cohomology I cannot imagine how cohomology is related to graph theory, actually I read solid definition from wiki, and to be honest, I cannot understand it.
e.g I know what is homotopy (in simple term), group of functions such that I can continuously convert each of them to another one, and I think this is useful for understanding homology, but, is there similar visualization method for cohomology? (I'm not looking for exact definition, I want to imagine it, actually this is in graph theoretic concept). for more information see introduction of this paper. I want to understand it in this paper, how is useful? how to imagine it?

P.S1: my field is not related to group theory, and as in introduction author wrote, this paper doesn't need deep group theoretic definition! and I don't want to be deep in group theory. Just looking for simple way to understand them.

P.S2: I think I can imagine what is free group (which is in introduction of paper), at least by Calay graph seems to be easy to imagine it.

P.S3: I also asked this in math.stackexchange but I think this is something between two field and may I get some mathematical answer there and some others here (from CS point of view) to understand it well.

Apparently all algebraic topology is useful for is earning imaginary internet points. More than I expected, I guess... (Actually now that I've finished writing I expect to lose points on this...)

tl;dr: Honestly, I don't think anyone here can give you an easy way to really understand what homology and cohomology are, with just a short description. I made an attempt below, but I took a whole course on the subject and I still don't really know what they are. Particularly if you don't know, or care to know, what a group is. These things are groups, that's sort of the whole point. As they relate to graph theory, you can treat a graph as a simplicial complex of dimension 1. Thus you can consider the homology and cohomology groups of the graph and use them to understand the topology of the graph. Here are some notes by Herbert Edelsbrunner on homology and cohomology, the latter of which provides a useful example.

Before I can define cohomology I must first make sure you understand the definition of homology. For simplicity I'll describe everything using simplicial complexes, but (co)homology can be, and usually are, defined for more complex complexes (see what I did there?). Simplicial complexes are enough for graph theory, at least as far as I've seen.

It turns out that it's really difficult to try to create homeomorphisms between two topological spaces to show that they're topologically equivalent. It's even harder to try an show that no such homeomorphism exists. So the idea is to establish topological invariants, a property that must be equal for two topological spaces if they are topologically equivalent. If the invariant isn't the same for both spaces, then they can't possibly be topologically equivalent. Homology and cohomology groups are two such invariants. They attempt to put a group structure on a topological space, so that we can work with groups and homomorphisms instead of topological spaces and homeomorphisms. Computer scientists like homology groups because they are easy to compute and lead to fast algorithms. The downside is they're much more difficult to visualize.

So how do we describe a topological space in such a way that we can place a group structure on it? Well we build our topological space with a set of simplicies, called a simplicial complex. A 0-dimensional simplex is a vertex, a 1-dim simplex is an edge, 2-simplex is a triangle, 3-simplex is a tetrahedron, etc. A valid simplicial complex must obey certain rules about how it's simplices connect to one another: the intersection of two simplices must also be a simplex in the set and all subsimplces must be in the set. Notice that graphs can be thought about in this way.

It makes sense to talk about sums of simplices of the same dimension $p$, what we call $p$-chains. So a $p$-chain can be written as $\sum_{i} a_i \sigma_i$ where $\sigma_i$ is a $p$-simplex and $a_i$ is an integer.  With this operation we can define the group of $p$-chains $(C_p,+)$, or just $C_p$.

We also have one more operation called the boundary operator, which takes a chain to it's boundary. So for an edge $(v,u)$ in some graph, the boundary is just the sum of its vertices $u+v$. The boundary operator of a $p$-simplex $\sigma = [u_0,\ldots, u_1]$ is defined as $\partial \sigma = \sum_{i}[u_0, \ldots, \hat{u_i}, \ldots, u_n]$ where $\hat{u_i}$ means that we remove the $u_i$ simplex and create a sum of $p-1$-simplices. To apply the boundary operator to a $p$-chain $c$, we just apply it to each of it's $p$-simplices, $\partial c = \sum_{i}a_i \partial \sigma_i$.

Now there are two very important types of chains which we use to construct homology groups, cycles and boundaries. A $p$-cycles is a $p$-chain $c$ with no boundary, meaning $\partial c = 0$. A $p$-boundary $c$ is a $p$-chain that is the boundary of some $p+1$-chain $d$, $c = \partial d$. Once again we can define groups $Z_p$ (our group $p$-cycles) and $B_p$ (our group of $p$-boundaries). The group $B_p$ is a subgroup of $Z_p$ which is a subgroup of $C_p$.

Homology groups are not a group of functions where one element can be deformed into another. Intuitively, what the homology group is trying to do is characterize the different loops. Think of a torus (donut) which has two distinct loops, colored in the image below. I can move the blue loop anywhere around the torus, but it's still the same loop because it differs only by it's boundary.

The elements of a homology group are equivalence classes, where two $p$-cycles in the simplicial complex are in the same equivalence class if and only if they differ only by a boundary chain. Meaning if you take two cycles $c,d \in Z_p$, and there exists boundaries $a,b \in B_p$ such that $c+a = d+b$, then $c$ and $d$ are in the same equivalence class. They are constructed as the quotient groups $H_p = Z_p/B_p$.

Now cohomology is much less geometrically intuitive and motivated by algebraic considerations.

We define cohomology groups in terms of cochains. A $p$-cochain is a homomorphism $\psi: C_p \rightarrow G$, where $G$ is the group used for the coefficients $a_i$ (usually $\mathbb{Z}$ or $\mathbb{Z_2}$). Instead of considering a group of chains, we consider the group of cochains, all homomorphisms between $C_p$ and $G$ denoted as $C^p=Hom(C_p, G)$.

Similarly we can define a boundary operator on cochains, as the dual homomorphism of $\partial$, which we denote $\delta: C^{p} \rightarrow C^{p+1}$. Notice that since the boundary operator $\partial$ took $p+1$-chains to $p$-chains, the dual homomorphism takes $p$-cochains to $p+1$-cochains. Now consider a $(p-1)$-cochain $\psi$ and $\partial c$ a $p-1$-chain. The coboundary operator $\delta$ requires that $\psi$ applied to $\partial c$ is the same as $\delta \psi$ applied to $c$.

Once we have the coboundary operator, we can define cocycle and coboundary groups, denoted $Z^{p}$ and $B^{p}$, just as we did before. Then the $p$th cohomology group is a set of equivalence classes where two cocylces are equivalent iff they differ by a coboundary. They are constructed as the quotient groups $H^{p}=Z^{p}/B^{p}$. Do you see why this is much less geometrically intuitive?


Matrix equality up to row/column permutations problem name Sorry for the trivial question; has the following decision problem an "official" (possibly short) name?

Given two  $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same up to row and column permutations.

(something like the short names used in complexity theory for decision problems: e.g. 3SAT, GI (Graph Isomorphism), X3C (Exact Cover By Three Set), CLIQUE, ...)

After a few observation in the comments (thanks to Hendrik Jan, Yuval Filmus, and D.W), I post an extended comment as an answer.

It seems (unless I'm missing something) that the problem is equivalent to Hypergraph isomorphism (HI):

to prove that it is equivalent to HI, it is enough to use incidence matrices: every column represents a node of the hypergraph, every row represents an hyperedge (the $1$s are placed on the columns corresponding to the nodes of the hyperedge).

  The question remains valid ... is there a short name for the problem other than Hypergraph Isomorphism (if it appears somewhere not related to graph theory) ?

(if nobody post another answer in a few days I'll temporarily accept mine).

Additional stuff:

for proving that it is GI-complete it is enough to consider the incidence matrix of the source graphs $G_1, G_2$;
the reverse reduction is similar to the well known reduction from HI to GI: it is enough to consider the incidence matrix of the source hypergraphs $H_1, H_2$, transform them to graphs: every column becomes a node $c_i$, every row becomes a node $r_i$; an edge $(c_i,r_i)$ is added if and only if the corresponding cell contains a $1$; and finally a new triangle is linked to every set of nodes $\{c_{i_1},...,c_{i_m}\}$ that represents an hyperedge to preserve hyperedge mapping.


Confused in calculating the shortest-path using Dijkstra's Algorithm I am required to find the shortest path using Dijkstra's Algorithm. After performing the calculations, am I getting the following values correct?:

A=0
B=13
C=8
D=20
E=14
F=25
G=31
H=38
I=46
J=52

Assuming that you only want to know the distance from A to a certain point, your first calculations are right.
However A to H should be 37. Check that again.
Also, there are shorter paths from A to I and A to J. Just have a look again - the other values are correct.


How to prove existence of the language Consider such question:

(Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$.

I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally different classes ($TIME(2^{n})$ and $NTIME(n)$ are the same classes, i guess). How to prove it strictly? (Or my guess is incorrect?)

Combine the following two facts:

$\mathsf{NTIME}(n) \subseteq \mathsf{TIME}(2^{O(n)})$, by deterministic simulation of nondeterminism.
$\mathsf{TIME}(2^{O(n)}) \subsetneq \mathsf{TIME}(2^{n^2})$, by the time hierarchy theorem.


Is there a faster solution for the Google Code Jam Great Wall Problem Consider the following Google Code Jam round 1C question:

The Great Wall of China starts out as an infinite line, where the height at all locations is $0$.

Some number of tribes $N$, $N \le 1000$, will attack the wall the wall according to the following parameters - a start day, $D$, a start strength $S$, a start west-coordinate, $W$, and a start east-coordinate, $E$.  This first attack occurs on day $D$, on range $[W,E]$, at strength $S$.  If there is any portion of the Great Wall within $[W,E]$ that has height $< S$, the attack is successful, and at the end of the day, the wall will be built up such that any segment of it within $[W,E]$ of height $< S$ would then be at height $S$ (or greater, if some other attack that day hit upon the same segment with strength $S' > S$)

Each tribe will perform up to $1000$ attacks before retreating, and each attack will be determined iteratively from the one before it.  Every tribe has some $\delta_D$, $\delta_X$, and $\delta_S$ that determines their sequence of attacks:  The will wait $\delta_D \ge 1$ days between attacks, they will move their attack range $\delta_X$ units for each attack (negative = west, positive = east), though the size of the range will stay the same, and their strength will also increase/decrease by a constant value after each attack.

The goal of the problem is, given a complete description of the attacking tribes, determine how many of their attacks will be successful.

I managed to code a solution that does work, running in about 20 seconds:  I believe the solution I implemented takes $O(A\log A + (A+X)\log X)$ time, where $A =$ the total number of attacks in a simulation (max $1000000$), and $X =$ the total number of unique edge points on attack ranges (max $2000000$).

At a high level, my solution:

Reads in all the Tribe information
Calculates all the unique $X$-coordinates for attack ranges - $O(A)$
Represents the Wall as a lazily-updated binary tree over the $X$ ranges that tracks minimum height values.  A leaf is the span of two $X$ coordinates with nothing in-between, and all parent nodes represent the continuous interval covered by their children. - $O(X \log X)$
Generates all the Attacks every Tribe will perform, and sorts them by day - $O(A \log A)$
For each attack, see if it would be successful ($\log X$ query time).  When the day changes, loop through all unprocessed successful attacks and update the wall accordingly ($\log X$ update time for each attack). - $O(A\log X)$

My question is this:  Is there a way to do better than $O(A\log A + (A+X)\log X)$?  Perhaps, is there some strategic way to take advantage of the linear nature of Tribes' successive attacks? 20 seconds feels too long for an intended solution (although Java might be to blame for that).

The obvious room for improvement is this step:

  Generates all the Attacks every Tribe will perform, and sorts them by day - $O(A\log A)$

We know that the tribes will attack from a particular day, in regular intervals. That means we should be essentially merging lots of pre-sorted lists. Also the problem statement tells us that there will never be more than 1,000 tribes (i.e. 1,000 lists to merge); a tiny number compared with the 1,000,000 maximum attacks! Depending on your implementation's relative timings, switching this could cut the processing time in half.

That's really all I can suggest for optimising the theoretical complexity, but I have no proof that it would be optimal after this change.

I gave the puzzle a go myself, but I used a much dumber representation of the wall: a binary search tree (C++'s std::map to be precise) storing locations where the wall's height changes. With this, I was able to add and removed nodes as required (i.e. if a complicated section was subject to a large, overwhelming attack, or multiple attacks of the same strength touched, the number of nodes would reduce significantly). This solved the large input in 3.9 seconds (on my mid-spec development laptop). I suspect there are several reasons for the improvement:

As you pointed out, boxing and unboxing can get expensive, but C++'s template-based containers avoid this entirely.
While the wall representation I used is theoretically worse, in the vast majority of cases being able to dynamically reduce the number of nodes made it super-fast (most test cases maxed-out at under 1k nodes, and all but 2 were under 10k). In fact, the only case which took any significant time was #7, which seems to have been testing lots of non-intersecting ranges.
I used no pre-processing (stages are determined by keeping track of when each tribe will next attack, and searching for the joint-lowest each turn). Again this is theoretically worse, but for the majority of cases I suspect the lower overhead means it was faster (I'll test this and get back to you). Update: I added a priority queue for attacks, similar to the method described above (although instead of creating the large array I calculated it on-the-fly) and saw the time decrease to 3.0 seconds for the large input.

In short, while I think your algorithm is near-optimal in the general case, there are several ways you could speed it up for typical inputs.


Unique triangulation duals of simple polygons Given a triangulation (without Steiner points) of a simple polygon $P$, one can consider the dual of this triangulation, which is defined as follows. We create a vertex for every triangle in our triangulation, and we connect two vertices if the corresponding triangles share an edge. The dual graph is known to be a tree with maximum degree three.

For my application, I am interested in the following. Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$. Here, the triangulation of $P$ may not be unique, but I require that the dual graph be unique.

This is certainly true when $T$ is a path, but becomes unclear when you have vertices of degree three.

Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$?

Yes. To show this, I will give a procedure to get the seemingly slightly stronger result*:

  Given a tree $T$ with maximum degree three, construct a simple polygon $P$, such that the unique triangulation of $P$ (without Steiner points) has $T$ as its dual.

Start by creating an initial triangle $\Delta_0$, representing some vertex $v_0$ in $T$ and add $v_0$ to the queue $Q$.
Then, repeat the following until $Q$ is empty:

Pop the top element, $v$, from the queue.
For each neighboring vertex $w$ that for which we have not placed a triangle yet, choose a side $AB$ of triangle $\Delta_v$ and a point $D$ inside the conical regions generated by the line through $AB$ and its neighboring segments, such that the triangle $\Delta ABD$ does not intersect any other triangles. (See figure below) Set $\Delta_w\leftarrow\Delta ABD$ and add $w$ to $Q$.

This image gives an example of a possible polygon $P$ (left) for the given $T$ (right)

To see why this procedure works, first note that after creating a new triangle, the segments $AB$ and $AD$ generate a cone that has a non-empty region not-intersecting with the existing triangles (see also the earlier figure), so we can find a suitable point at every step and create a polygon.

Second, we have chosen the triangles such that line segment between $CD$ does not completely lie inside $P$. If there exists a corner-point $Q \notin \{B,D\}$ of the already placed triangles such that $DQ$ is fully in $P$, then it must lie inside the cones generated by $AD$ and $BD$. However, since the part of this cone that does not lie inside $\Delta ABD$ is contained in the cone generated by the earlier placed triangle, such a $Q$ exists only if there exists an analogous point for the earlier placed triangle. Since there does not exist such a point for the first triangle, this means there is no such point for any triangle we add.

This means that all pairs $(X,Y)$ of any corner point of $P$ for which the segment $XY$ is fully contained in $P$ is already in the constructed triangulation, so the triangulation is unique for $P$ (all triangulations add the same number of internal segments)

Note that the polygons constructed in this method tend to have rather sharp angles. I suspect arbitrary large graphs require polygons with arbitrary small angles, which could be a problem when drawing these polygons with finite precision.

*: The difference is that, if we interpret 'unique' as up to isomorphism (which is consistent with uniqueness of triangulations and duals being different), we would be ok with a polygon having multiple triangulations that all have isomorphic duals. However, it is possible to 'attach' more triangles to those polygons to ensure some duals are no longer isomorphic.


Scheduling N variable-time interdependent tasks across M workers I have N tasks, each of them requires some time to complete. Time to complete is not the same for all tasks. Each task may depend on a number of other tasks (assume, that no dependency cycles are present). I have M (M is fixed, small and << N) workers that may be used to complete the tasks. I need to find a sequence of tasks, that each worker must complete in order to minimize the total processing time.

How is this problem formalized / modelled?
I am not sure, which textbook or paper I should read in order to understand, how one might approach this problem (looking for keywords here).

If there is a need to "peg" some tasks (not all) to certain workers, how is the problem "affected"? That is, does it become significantly harder to solve or reason about?

This can been seen as a variation of the job shop problem where you want to find the policy that yields the minimum makespan (time taken for all machines to process all jobs); as well as a variation of the assignment problem (find the optimal pairing of workers to jobs that minimizes cost). The variation in both cases is an added dependency between jobs (Job A must complete before Job C) etc. This collection of combinatorial optimization problems is NP-Hard. Most of what you'd find in the literature is approximation heuristics to find a near optimal policy (sequence of tasks per worker).

This paper is one such approach: "Approximation Algorithms for Multiprocessor Scheduling under Uncertainty"

A quick way to solve your problem (quick as in prototype a solution, not necessarily runtime, or necessarily near optimal), is to construct a topological sort of your job dependency graph, use breadth first search to batch all jobs of a given height and put that batch on a stack (assumes directed edge represents a depends on relationship, with zero out degree nodes having no dependencies). Afterwards, Until the stack is empty, pop a batch and treat it as a traditional assignment problem and solve using the Hungarian algorithm, then enqueue the tasks to each assigned worker's task queue. Afterwards you'd have a policy. (When you go to execute the policy, you'd have to have some signalling mechanism that a task completed so that workers don't start on a task whose dependencies haven't finished yet.)


Floating-point oblivious way to compute multiset numbers I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be:
$$
R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{1\cdot 2\ \cdots\ k}.$$
The problem is that, if you compute the numerator and denominator separately, you will run very soon into overflow territory, so a better way to calculate this division, since both parts of the fraction have same number of components, is by: $$R = \left(\frac{n+1}{1}\right)\left(\frac{n+2}{2}\right)\cdots\left(\frac{n+k}{k}\right) = \prod_{i=1}^k\frac{n+i}{i} = \prod_{i=1}^k\left(\frac{n}{i} + 1\right)$$
The problem of this approach is that you have to apply floating point arithmetic to do the divisions, which are way more inefficient than using simple integral arithmetic.
But, knowing that the final result would be integral, is there any[1] way to split the big fraction into a sequence of products of fractions so that each fraction has a numerator that is a multiple of its denominator? The idea is to remove any floating point operation to calculate $R$.
Has this formula any property that guarantees that such sequence exists?
[1] Ok, maybe not "any" way would be valid. If the process to avoid the floating point arithmetic would cost more than the floating point arithmetic itself, it won't be worthy.

One common way to work with binomial coefficients without overflow is to use prime factorisation.
Legendre discovered the formula for this, and it is worth proving it for yourself. The factorial of a number can be factorised as powers of primes:
$$n! = p_1^{q_1} p_2^{q_2} \cdots$$
where:
$$q_i = \sum_{k=1}^{\left\lfloor \log_{p_i} n \right\rfloor} \left\lfloor \frac{n}{p_i^k}\right\rfloor$$
Instead of multiplying and dividing, therefore, you can just add and subtract exponents of primes.


Decide if there is a sbugroup of edges in graph that every vertex meets exactly k edges from subgroup I've been trying to solve the following question:

  Show a polynomial algorithm for the following problem. Let $G = (V,
> E)$ a graph. The goal is to decide if there is $E' ⊆ E$ , such that
  for every vertex $v ∈ V$, $v$ meets or exactly $k$ edges from $E'$.
  (Namely, for $k = 1$ you get the perfect matching problem). hint -
  start with $k = 2$, duplicate vertices.

I was able to develop an algorithm which works but I couldn't prove it find the largest subgroup, your help is needed :)

The algorithm:

For every $v$ in $V$:

Check the degree, if it equal to k or not connected to any edge in
the subgroup - color it
Check if the colored $v$ has a colored vertex,
if it has the edge between them belongs to the subgroup.
Traverse on all vertices (BFS or DFS) When done you'll find the subgroup, the only one thing the prove it is the largest and I couldn't find any
proof for it.

Thanks in advance!

The question is a bit misleading, since the proposed algorithm finds whether there is a "multisubset" of the edges set which is $k$-regular — that is, you are allowed to take the same edge several times, if it helps. Deciding whether the graph contains a bona fide $k$-factor (a $k$-regular subgraph which touches all vertices) is much more tricky — see Meijer, Núñez-Rodríguez, and Rappaport, An algorithm for computing simple $k$-factors.


Provability of NP /= P? I'm a novice to the topic of provability so bear with me...

During a discussion with a friend, the question came up whether it could be possible that proving that $NP \neq P$ (or $NP = P$) is an unprovable statement. My friend opposed that, if indeed it was unprovable, then this would imply that there cannot be a polynomial time algorithm for NP-hard problems (as the existence of such proves the statement), thus implying $NP \neq P$. This seems to be imply that the statement cannot be unprovable or am I missing something?

Statements that are independent are not true or false, their truth value just cannot be decided given the axioms. For example, consider natural numbers. It is true that a given number is a product of primes. It is unprovable that a given number is prime, nor that it is not prime – since it depends on the number. For each given number, it is either prime or not, but it depends.

The same goes for independent statements – the "number" is here replaced with the set-theoretic universe (or whatever universe you base your logic in). It could be that in some universes P equals NP, while in some universes the two are different. The "real world" is one of these particular universes, but as Gödel showed, it is impossible to completely describe the real world: there will always be independent statements. When faced with one, we could try to find other properties of the real world which help determine the statement. This approach hasn't fared so well on the canonical example, the continuum hypothesis.

Despite the foregoing, it is not considered likely that the P vs. NP question is one of these independent statements. That's a declaration of faith. Even though it seems hard to settle, most theoreticians believe that it is just a difficult question, similar to many other difficult questions in mathematics, some of which have been solved one way or another (for example, Fermat's last theorem), some of them haven't (for example, the Riemann hypothesis).


Proof that total computable functions are not enumerable In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made:

  Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all total computable functions from N to N, such that every $f_e$ was total, then $g(i)=f_i(i)+1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

I really don't understand why

  then $g(i)=f_i(i)+1$ would also be a total computable function

Indeed if $g$ was a total computable function, then $\exists k, f_k=g$, so that $g(k) = f_k(k) + 1 = g(k) + 1$, which is impossible.

So it seems to me that building $g$ is impossible, so that we cannot reach a contradiction by saying that we have built another total computable function which is not in our enumeration.

I tried shifting the diagonal to avoid this effect, but other loops of the same kind can't be ruled out.

$g$ is total computable by definition.

By assumption $f : \mathbb{N}^2 \to \mathbb{N}$ is total computable.
$1$ certainly is.
$+$ certainly is.
The concatenation of $+$ and $f$ is computable by construction, and that's $g$.

The details depend on the exact definition of "computable" (i.e. the machine model) you use; see e.g. here.

So under the assumption that such $f$ existed, $g$ is computable; therefore, it must have an index in $f$, which is impossible (as you note); therefore, the assumption must be false.


Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:

  Suppose that a friend tells you that a given
  graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of $V$ and whether each of the consecutive edges along the cycle actually exists in the graph. You could certainly implement this verification algorithm to run in $O(n^2)$ time, where $n$ is the length of the encoding
  of $G$.

To me, for each consecutive pair $(u,v)$ of the given cycle, we could verify if it's an edge in $G$. Further we could use some color coding for each vertex to ensure we don't revisit a vertex. By doing so, we could verify if the given cycle is Hamiltonian in $O(E)=O(m^2)$ time where $m$ is the  number of vertices in $G$. Further we can see the minimum encoding $n$ of $G$ is $m^2=n$. Thus $O(E)=O(m^2)=O(n)$. Can anyone help me understand, why it is mentioned as $O(n^2)$ instead!

The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this?

First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has an encoding of size $V^2$. However, if an adjacency list encoding is used, we would only need an encoding of size $O(E \log V + V)$.

Your algorithm does indeed run in $O(n)$ time for a dense graph (with $\sim V^2$ edges); does it also run in $O(n)$ time if the graph is sparse ($O(V)$ edges)? In that case, the encoding might be shorter (if an adjacency matrix is used). Is your algorithm still $O(n)$ in that case? If it enumerates over all potential edges or creates and adjacency matrix, it would not be.

CLRS wants to avoid peculiarities with having to implement the algorithm in a particular way or having to specify a specific encoding, which is why they state "you could certainly implement this algorithm to run in $O(n^2)$ time". The "certainly" means "in any case, you can get $O(n^2)$, but it might be possible to do better". In any case, all they care about is that it is polynomial, which both $O(n)$ and $O(n^2)$ are.


Show linear bounded automata accepting w is PSPACE-complete ALBA={⟨M;w⟩ | M is linear bounded automata which accepts input w}

Show that ALBA is PSPACE-complete.
How I would try to solve it...

We need to prove ALBA belongs to PSPACE. So I would construct TM A which accepts <M;w>. Simulate M till qng^n steps or when it halts. If it halts: Accept <M,w> if M accepts w, otherwise reject.
How would be space complexity? I would say it will need n (=size of the tape) so space complexity should be O(n) and then ALBA belongs to PSPACE. Is it correct?

We need to do reduction from TQBH to ALBA to prove that ALBA is NP hard, but I have no idea how to do it. How should this reduction be done? TQBF must be 1 if ALBA accepts w i guess, but dont know how to show the proof...

Savitch's theorem shows that PSPACE=NPSPACE, which immediately implies that ALBA is in PSPACE.
In the other direction, suppose that $L$ is a language in PSPACE. Thus $L$ is accepted by some machine that uses space $p(n)$. We can construct another machine $L'$ which accepts an input $(x,y)$, erases $y$, and simulates $L$ on $x$. We can reduce $L$ to ALBA by mapping $L$ to $L'$ and $x$ to $(x,0^{p(|x|)})$.


NP-Complete reductionTrue/False question explanation Why is the above statement true? my understanding is:

(1)3SAT reduces to X implies X is NP-complete or harder.

(2)Set Cover reduces to X implies X is neither NP-Complete nor harder.

This contradiction gets me a bit lost as to why  the conjunction of 1 and 2 implies that X exists in P. I'm hoping someone can explain this to me. Note: both 3SAT and Set Cover are NP-Complete.

Your understanding is correct, but the takeaway here is that assuming the contradictions implies that anything can be true. Perhaps reading up on some logic rules might help, the important rule here is that $\bot$ (false) implies everything. Here is a little proof of the problem just for fun:

We know that both 3-SAT and Set Cover are NP-Complete problems.
Now, assume that 3-SAT $\leq^{m}_P$ X and that Set Cover $\nleq^{m}_P$ X. We want to show that X $\in$ P.

Since both 3-SAT and Set Cover are NP-Complete problems, we know that Set Cover $\leq^{m}_P$ 3-SAT. We also know that 3-SAT $\leq^{m}_P$ X. By the transitive property of reductions, we know that Set Cover $\leq^{m}_P$ X. Now we know that Set Cover $\leq^{m}_P$ X and Set Cover $\nleq^{m}_P$ X, which is a contradiction. Since false implies everything, we can say that X $\in$ P. (In fact we can also say that pigs can fly faster than superman can)

Q.E.D.


Why does NTIME consider the length of the longest computation? In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows:

  Let $N$ be a nondeterministic Turing machine that is a decider.  The running time of $N$ is the function $f : \mathbb{N} \rightarrow \mathbb{N}$, where $f(n)$ is the maximum number of steps that $N$ uses on any branch of its computation on any input of length $n$ [...].

Part of this definition says that the running time of the machine $N$ is the maximum number of steps taken by that machine on any branch.  Is there a reason that all branches are considered?  It seems like the length of the shortest accepting computation would be a better measure (assuming, of course, that the machine halts), since you would never need to run the machine any longer than this before you could conclude whether the machine was going to accept or not.

Because you don't know ahead of time whether or not any given input is a 'yes' instance — that is, whether there exists any accepting path — it makes sense for the sake of uniformity to bound the run-time independently of any particular feature of the computational paths. Thus, it makes sense to require the worst-case behaviour to be polynomial time, regardless of whether or not any accepting paths exist.


Confusion related to time complexity of dynamic programming algorithm for knapsack problem I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming

I didn't get how the time complexity of the algorithm came out to be $O(nV^*)$

Since computing each cell in the table is $O(1)$, the running time is just the size of the table. The first coordinate ranges from $1$ to $n$, and the second one from $0$ to the maximal value ever encountered (so it's really a dynamic table), which is $V^*$.


Treating undirected graphs as a subcategory of directed graphs Roughly, an undirected graph is very similar to a directed graph where for each edge (v, w), there is always an edge (w, v). That suggests that it might be acceptable to view undirected graphs as a subset of directed graphs (perhaps with an additional restriction that adding/deleting edges can only be done in matching pairs).

However, textbooks usually don't follow this treatment, and prefer to define undirected graphs as a separate concept, rather than a subcategory of directed graphs. Is there any reason for that?

You are absolutely correct; that's a perfectly valid way to view undirected graphs.

Sometimes, in undirected graphs, some things become easier and cleaner to reason about.  For instance, you don't have to worry about the difference between weakly connected vs strongly connected components in undirected graphs.  Algorithms for undirected graphs can sometimes be more efficient or simpler than if we were to apply the corresponding algorithm for directed graphs.

So: perhaps some textbooks choose to follow this treatment because it lets them introduce a problem first in the (easier) context of undirected graphs, and then generalize to the (harder) case of directed graphs.  That's just speculation.


Shortest path including all nodes in a subset Given a directed graph $G=(V, E)$, two nodes $s, t \in V$ and a subset of nodes $U \subseteq V$.
Provide an algorithm that determines if there is a shortest path from $s$ to $t$ that passes via all nodes in $U$.
I came across a solution that starts with the following steps

Run BFS on G, notate $d_s(v) \quad \forall v \in V$
Calculate $G^T$ (transposed graph)
Run BFS on $G^T$, notate $d_t(v) \quad \forall v \in V$
Build $G^{'} = (V, E^{'})$ where $E^{'} = \{(u,v)\in E | d_s(u) + 1 + d_t(v) = d_s(t)\}$

I don't quite understand the intuition for this specific build. It resembles the building of G scc with DFS which doesn't contribute much to my understanding.
Why would I want to build the graph this way and not use the shortest-path-tree I got from the first BFS execution?
EDIT: continued algorithm steps are:

Run topological sort on $G^{'}$, notate the result with $a_1, a_2,...,a_k$.
Initialize field $c(v)=0 \quad \forall v \in V$
Initialize starting node $v \leftarrow t$
For all v in the reverse topological order do: (until arriving at s)
{
$\forall (x, v) \in E^{'}$
{
if $v \in U, c(x) \leftarrow max\{c(x), c(v)+1\}$
else $c(x) \leftarrow max \{c(x), c(v)\}$
}
}
Return $c(s) == |U|$

The purpose of the BFS in the transposed graph is to eliminate edges that are part of shortest paths to some vertex, but not to $t$. These "useless" edges could otherwise lead to false positives in the traceback phase that builds $c(\cdot)$.
Consider the digraph with $E=\{st,su\}$ and $U=\{u\}$. The unique shortest path is the single edge $st$, so the answer is NO, but unless you know that the $su$ edge should be ignored (by making use of the transposed graph), the traceback phase will process it (on either its first or second iteration) and assign $c(s)=1$, resulting in YES being reported.
(Alternatively, you could augment the traceback phase by "marking" $t$ and any edge into a marked vertex, and considering only values of $c(\cdot)$ for marked vertices. This is fairly similar to just performing a backwards BFS from $t$, and probably a little more efficient in practice.)


Creating a CFG that connects lengths of three blocks I have to create a CFG which generates

$$\{a^n (ab)^n c^m d^\ell e^k \mid n>0, k, \ell, m\ge0, k<m, m=\ell+k\}$$

The first part is easy enough, I came up with

$$\begin{align*}
    S &\to aS_2abS_3 \\
    S_2 &\to aS_2ab \mid \epsilon
\end{align*}$$

However, the second part is very confusing. So far I have

$$S_3 \to S_4 \mid \epsilon$$

The problem I have is how do I possibly keep track of all of these variables? $k$ has to be less than $m$, $m$ has to be equal to $\ell + k$, and $\ell$ must be at least $1$ by extension. Can someone give me some general tips for approaching these CFG's?

Here comes the grammar based on your part of the answer and the comments of Raphael and Rick Decker (including $l\ge 1$). At first, your part:

$S\to aA_1abA_2$
$A_1\to aA_1ab\mid\varepsilon$

Secondly, we create rules for $A_2$ such that we get words of the form $c^kA_3e^k$

$A_2\to cA_2e\mid A_3$

Finally, we create rules for $A_3$ such that we get words $c^ld^l$ with $l\ge1$:

$A_3\to cA_3d\mid cd$