Can a graph with more than |V| - 1 edges have the maximum weighted edge as part of its MST? Consider a graph graph G with |V| vertices and more than |V|-1 edges, is it possible for an edge to be the 'heaviest' and also be unique, but still be part of the graph's MST? If so, in which cases is  it applicable?
From what I've been thinking so far, if the maximum edge is the only part that connects some vertex with the rest of the tree, it has to be part of the MST regardless, but that is regardless of the constraint of having more than |V| - 1 edges.
So am I correct to assume that, having more than |V| - 1 edges you can have the heaviest edge as part of the MST? Also, why is the constraint of edges being more than |V| - 1 applied here, what purpose does it serve?
Thanks.

Consider the following example:

You can clearly see that the heaviest edge (connecting vertices 3 and 4) is in any MST of this graph. In general, the heaviest edge (assuming it is unique) will be part of the MST of a graph if and only if it is a bridge (meaning that if we remove that edge the graph gets disconnected). The condition $|E| \geq |V| - 1$ doesn't really change anything. However, in order for MST to make sense, we need the graph to be connected. Note that $|E| \geq |V| - 1$ does not guarantee that.


How to convert a recursive function to a non recursive one using stack while keeping memoization? Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'.
I could simply count it using a recursive function as follows:
def num_ways(s: str) -> int:
    if len(s) > 0 and s[0] == '0':
        return 0

    if len(s) <= 1:
        return 1

    if len(s) >= 2 and int(s[:2]) > 26:
        return num_ways(s[1:])

    return num_ways(s[1:]) + num_ways(s[2:])

However, this function can be easily optimized by using memoization technique. (I'll avoid showing off memoization into that code to keep it tidy, but you can assume I could use such a decorator that would be responsible for this job)
Alright! But what if I want to use a stack to replace that recursion? (I don't want to use a bottom-up dynamic programming approach in this case)
So I could have something like this:
def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)

    ways = 0
    while stack:
        cur_s = stack.pop()

        if len(cur_s) > 0 and cur_s[0] == '0':
            continue

        if len(cur_s) <= 1:
            ways += 1
            continue

        if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
            stack.append(cur_s[1:])
            continue

        stack.append(cur_s[1:])
        stack.append(cur_s[2:])

    return ways

It works! But how can I optimize it by memoizing duplicate work as well as I'm able to do in the recursive method? Moreover, is there a better way to convert from a recursive function to a stack-based non-recursive one?

You can simply maintain a (hash)table, just like in the recursive case. Basically, you need to treat items on the stack like function arguments in recursion. Every time you pop items off the stack for processing, you check whether the particular entry in the table had been filled first. This gives you an equivalent memoized algorithm.
Additionally, you also need to check whether the table already contains the entry when you add an item to the stack; this avoids blowing up the stack with already memoized entries.
maintain a hashtable T of strings.

def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)

    ways = 0
    while stack:
        cur_s = stack.pop()
        if cur_s is in T, then discard cur_s and continue

        if len(cur_s) > 0 and cur_s[0] == '0':
            continue

        if len(cur_s) <= 1:
            ways += 1
            continue

        if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
            stack.append(cur_s[1:])
            continue

        if cur_s[1:] is not in T:
            stack.append(cur_s[1:])
        if cur_s[2:] is not in T:
        stack.append(cur_s[2:])

    return ways

To answer your second question, which is if there are other methods of converting recursion to iteration, there certainly is. For certain functions that are tail-recursive (and if not, you can try rewriting them into tail-recursive ones using continuous-passing style) you can convert them to equivalent iterative algorithms without keeping a stack but a bunch of variables.
For dynamic programming recurrences, the conventional practice for iterative computation is you identify an order which can be used to correctly fill up the memoization table (e.g. row-major, column-major, or diagonal) and use nested loops to iteratively compute the values in the memoization table. This potentially saves space, as it avoids the need to maintain a stack during the recursion.


Dijkstra's shortest path algorithm without relaxation Although I have found a very similar question to what I want to ask here (https://codereview.stackexchange.com/questions/96064/dijkstras-algorithm-without-relaxation), yet I didn't find a satisfactory answer there, hence comes this question.

So I have done competitive programming for fun for a while, whenever I need to find shortest path, I always implement something like this:

For the sake of brevity, this algorithm only finds shortest path's weight from a vertext s to a vertex d (instead of all vertices) (assuming there is no negative cycle in the graph of course)

1. Create an empty min heap with comparator is the weight
2. Create an empty set (most of the time hash set)
3. Add s to the heap with weight is 0
4. Add s to the set
5. while (heap is not empty)
6.    min = extract min from heap
7.    if (min == d) return min.weight
8.    add min to set
9.    for (v in adj of min)
10.        if (set is not already contains v)
11.           add v to heap with weight is min.weight + weight(min, v)

I have always believed that this is Dijkstra shortest path algorithm until today when I saw a video of lecture on Dijkstra algorithm from MIT. I realized that I never had the relaxation step in my Dijkstra algorithm.

So I'm really not sure if it is or just a variant of Dijkstra or not even Dijkstra (maybe A*? I'm not sure)?
Also, I have used this algorithm in programming contests many times, it always worked, but now I doubt about its correctness?

Yet, half of me still thinks this algorithm is correct because this not very formal proof:

At a given time, there could be multiple paths to v with different
weights in the heap, but once we extract first path to v from the
heap (calls it min_path), it has to be smallest weight path to v
in all the paths.
For all the other paths to v which haven't been
added to the heap, they have to have weight more than min_path's
weight because: when they are added to the heap, they can only be
added after extracting some other paths which have bigger weight than
min_path's weight, so their weights are bigger than min_path's
weight.

If my algorithm is correct, then I think the running time would be O(ElogV) and O(E) of space because:

The heap can have at most E elements at a given time

extract min costs log(E) < log(V^2) = 2log(V) = log(V)
same goes to adding an elmenet to the heap

In total, O(ElogV) for running time.

So in the end, I believe my algorithm has same running time with standard Dijkstra that has relaxation and decrease key step (that costs logV), only downside is my algorithm costs O(E) for space. Is this correct?

UPDATE1: Java sample code

public class Test30 {
    public static void main(String[] args) {
        List<int[]>[] map = new List[4];
        map[0] = Arrays.asList(new int[]{1, 2}, new int[]{2, 2});
        map[1] = Arrays.asList(new int[]{3, 9});
        map[2] = Arrays.asList(new int[]{3, 1});
        System.out.println(dijkstra(map, 4, 0, 3));
    }

    public static int dijkstra(List<int[]>[] map, int n, int src, int dst) {
        boolean[] been = new boolean[n];
        // 0: vertex, 1: weight
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        been[src] = true;
        pq.add(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int[] pop = pq.remove();
            int v = pop[0];
            int weight = pop[1];

            if (v == dst) return weight;

            for (int[] i : map[v]) {
                if (been[i[0]]) continue;
                pq.add(new int[]{i[0], weight + i[1]});
            }
        }
        return -1; // impossible
    }
}

This answer refers to a previous version of the pseudocode, which had a bug. Once reaching a vertex, it doesn't update its weight ever again.

Your algorithm isn't Dijkstra's algorithm. Worse, it doesn't calculate shortest paths. As a simple example, consider a graph with nodes $\{s,a,b,t\}$ and the following edges:

$s\to a$ with weight 1.
$s\to b$ with weight 2.
$a\to t$ with weight 9.
$b\to t$ with weight 1.

The shortest path from $s$ to $t$ is via $b$, but your algorithm will discover $t$ via $a$ and will therefore output a distance of 10 rather than the correct distance, which is only 3.

Finally, you mention that the space complexity is $O(E)$. In fact, since the heap and set contain vertices rather than edges, it is $O(V)$.


Pumping lemma: why x in ∣xy∣ ≤ p? Looking at the pumping lemma, I've noticed that in the string $xy^pz$, there seems to be no rule explicitly stated for $x$ and $z$. If I understand correctly, $x$ and $z$ are basically anything on the 2 sides of the string $y^p$ that we're pumping and thus can be anything in $L$.
Rule 2 & 3 of the pumping lemma are:

$|y| \geq 1$
$|xy| \leq p$

Since $|x| = 0$ and $|z| = 0$ seem to be allowed, as they only need to be of non-negative length, we shouldn't need $x$ in rule 2 and it can be rewritten as $1 \leq |y| \leq p$.
Are $x$ and $y$ not just a substitute for whatever are on the 2 sides of $y^p$ which we're pumping? Why is $x$ in rule 2 if it doesn't seem to make a difference? If $x$ is necessary, why is there no $|yz| \leq p$?

You said:

If I understand correctly, $x$ and $z$ are basically anything on the 2
sides of the string $y^p$ that we're pumping and thus can be anything
in .

This is not true. The pumping lemma suggests that for every long enough word $w$  such that $w\in L$, there is a partition of $w$ into three words $w = xyz$ such that the three conditions of the lemma hold. You only know that such $x, y$ and $z$ exist, you do not know whether this is true for all $x, y, $ and $z$ that partition $w$. Thus, you cannot force $x$ or $z$ to be empty. In fact, this is far from being true. For example, consider the language of the regex $a b^*$. Here $y$ cannot contain the letter $a$, thus you cannot force $x$ to be the empty word.
You also said:

If $x$ is necessary, why is there no $|yz|\leq p$?

This condition is too strong as, along with the condition on $|xy|$, it suggests that every long enough word $w$ in the language, has to be of length at most $2p$, which is not correct.
Also, once you have the condition $|xy|\leq p$, there is no need to have a condition on $|yz|$. The pumping lemma conditions come up naturally from how a run of length at least $|Q|+1$ looks. In such long runs, two states have to repeat in the first $|Q|+1$ states of the run, and thus the condition on $|xy|$ arises. You can think about considering the last $|Q|+1$ states in a long run, and that might give you another variant of the pumping lemma (where $x$ and $z$ replace rules) but I don't see how this may be more useful or more appealing than the standard pumping lemma.


Problem with determining the shape and direction of the Huffman Diagram I have the phrase "abracadabra" and I want to encode it through the Huffman method. I first took the frequencies of each letters;
$$a=5$$
$$b=3$$
$$c=1$$
$$d=2$$
$$r=2$$
But I'm not sure as to how the diagram should look like. I made a few and some of them are correct. Also what determines the direction the branches take? Is there any fixed criteria for it?

Huffman's algorithm is non-deterministic — at several junctures you have more than one admissible choice. For example, at the first step, you can merge either $c$ and $d$ or $c$ and $r$. As another example, you can choose which child is left and which is right arbitrarily. Any particular implementation of Huffman's algorithm has some tie-breaking rule which makes it deterministic, but any choice would lead to a minimum redundancy code, and the generic Huffman algorithm doesn't specify any specific tie-breaking rule.

Huffman's algorithm is guaranteed to produce a minimum redundancy code, but not every minimum redundancy code can be produced by an admissible run of Huffman's algorithm. See Gallager's classic paper Variations on a theme by Huffman.


Identify the function call statement in the following snippet I know that the main(sys.argv[1:]) is the function call statement but I have no idea about the other two variables and why it's used. Can anyone explain?

Are you writing an interview test right now ?

__name__ is not a function. Is a special keyword used by Python and its value is ‘__main__’ if the script is run directly from terminal.
So if another script.py imports the one in the photo, the code inside the if statement won’t execute.

sys.argv

Is a list of the arguments of the script, if given any from the terminal. The reason of sys.argv[1:] is to exclude the first argument which is the file name of the script.

So you are right. The only function call statement is the main(...)

As far as for why the notorious

if __name__ == ‘__main__:’

is used, I would say for testing purposes. Imagine having a lot of .py files which import other .py files. You need to test each one separately from the other.


Find shortest paths in complement graph I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, where $E$ is the number of edges in the original graph (not the complement graph).

If $G$ is a graph, the complement graph is defined to be the following graph: $e$ is an edge in the complement graph, if and only if it isn't an edge in the original graph. In other words we delete all existing edges, and add all the edges that were missing from the original graph.

So first I of course thought of "building" the complement graph (replacing the vertices in the adjacency list with those that don't appear there), then running BFS on the new list, but of course that would mean that the run-time would be based on the edges in the complement graph, not the original one.

I also noticed of course that after running BFS on the original graph, any vertex that has a distance from $s$ that is greater than 1 (in the original graph) should become 1 in the complement graph (because if they weren't neighbors in the original graph, they are neighbors in the complement graph). But I couldn't get the algorithm to continue according to some specific rules as to when should the distance be updated and to what.  Any suggestions?

I personally, do not see why this is left as unanswered.

Finding something in complement graph and finding that same thing in the graph is essentially have the same time complexity (up to constant factor).

Since swapping between edge $(u,v)$ and non-edge $(u,v)$ is just $O(1)$-time operation. We do not have to transform or convert anything just negate every query output.


Why AKS primality test is called polynomial? It's complexity is $\mathcal{O}(\log^6n)$ and $\log^6n$ is not a polynomial. Can we say that primality testing is strictly contained in $P$ then?

The time complexity of the AKS primality test is $O(n^6)$, where $n$ is the length of the input. The length of an integer $N$ is roughly $\log N$, so the time complexity of the AKS primality test applied to the integer $N$ is $O(\log^6 N)$.

Finally, I'm not sure what you mean by a problem being strictly contained in P. Every problem in P is contained in some smaller class $\mathsf{TIME}(O(n^k))$ for some $k$.


Minimum Number of People Such That No Two People Know the Same Two People In a population of $n$ people, each person knows $k$ other people and each person is known by the same $k$ people.  However, no two people, p1 and p2, know the same two people p3 and p4.  What is the minimum $n$ such that this is possible for a given $k$?  Or, in other words, what's the minimum number of nodes that must exist such that it is possible to connect each node to $k$ other nodes while not allowing a cycle of length 4?

Also, if it is possible, is there a program that can generate these graphs?

I don't have much on this problem yet besides a weak lower bound of $n\geq k^2-k+2$.

In the graphs below, an edge means that the two people it connects know each other.  In 1), this is a demonstration of what we don't want, both A and C know D and B.  In 2) these are configurations that work for k=2.  For k=2, n=3 and all n>4 work.  In 3) n=10, this is the smallest possible configuration for k=3.

The comment of Carlos actually gives an upper bound. There is a much better (and almost tight) upper bound for $k+1$ being a prime number: $n=k(k+1)$. The construction is a classical result in extremal graph theory, namely $C_4$-free $k$-regular graphs, which can be found here.

The vertices are labeled with $(a,b)$ where $1\leq a\leq k, 0\leq b\leq k$. Two vertices $(a,b)$ and $(c,d)$ are linked if and only if $ac\equiv b+d\mod (k+1)$.
Notice that for any given pair $(a,b)$ the number of solutions $(c,d)$ is exactly $k$, so the graph is $k$-regular. To see the graph is $C_4$-free, consider the following congruence equations
$$\left\{ \begin{array}{ll}ax\equiv b+y\mod (k+1)\\ cx\equiv d+y\mod (k+1)\end{array} \right.$$
Since these imply $(a-c)x\equiv b-d \mod (k+1)$, and $k+1$ is prime, there is at most one solution whenever $(a,b)\neq (c,d)$, so the graph contains no $4$-cycle.

There are many other constructions among this context, for instance, when $k-1$ is a prime power there is a construction of size $n=2(k^2-k+1)$ with bipartite incidence graph (See, e.g., here).


Need help with ER diagram I am making database on Disaster Management. There are four tables.

DisasterEvent (eventid, name, glideID, status, description, date_occurred,  date_ended, disaster_type)
People(eventid, num_deaths, num_injuries, num_affected)
Homes (eventid, num_homes_destroyed, num_homes_damaged, total_insured_loss, total_uninsured_loss)
Place (place_id, city, state, country, postal_code)

In my design, I have one to one relationship between People and DisasterEvent , and one to one relationship between Home and DisasterEvent because for a particular disaster there is only one People table that we are concerned and same for Home table.
Now, Place has many to many relationship with DisasterEvent because at particular place there can be many disasters over time and same disaster could occur many place at once.

What am I trying to achieve is able to map number of affected people by the particular disaster event at certain place. For this I think there needs to be three way relationship among DisasterEvent, Place and People. How do I achieve this?

Since you have a 1-1 relationship between DisasterEvent and People now, you can not distinguish any relation between People and Place. If several Places are related to a single DisasterEvent, all those places are related to the same instance of People.

If you want to map the People affected by the Event at a Place, you should relate People to Place instead of to DisasterEvent.

As long as an event always occurs at at least one place, you can always relate your People to your DisasterEvent via the Place where it occurred.

On a sidenote, I would use Location instead of Place, and maybe the more precise Victims for People, as well as maybe Damage for Home.


Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT In Cormen's Algorithms book on NP-completeness they prove various problems are NP-complete by reducing a previously proved NP-complete problem (call $K$) to current problem (call $L$). Each proof involves some clever construction which reduces all instances of $K$ to few instances of $L$. Here is the proof order they follow. CIRCUIT-SAT, SAT, 3 CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP. e.g. in reducing VERTEX-COVER to HAM-CYCLE they use a widget which does the trick.

After this previous question of mine, I think one can reduce back. i.e. one can reduce HAM-CYCLE to VERTEX-COVER problem. I tried searching web for such reductions, but most of the link return the normal reduction order. I'm interested to see if one can reduce in reverse order. i.e. TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

I'm looking for reverse constructive proofs. I know all of these problems belong to NP-complete hence equivalent.

You don't have to give complete proof as an answer. Proof sketches are fine too. If you can point me where these proofs are available online, that's completely fine too. I'm just trying to lean how constructions are leveraged among problems that look so different on surface. Thanks!

A couple of the ones you're looking at here are pretty simple actually (at least to sketch!). For all of these, there are many other ways to do it, even many other sensible ways, so these are just attempts to pick the simpler approaches (we'll see if I succeed).

As mentioned in one of the comments on the question, $3SAT$ to $SAT$ is trivial, an instance of $3SAT$ is already and instance of $SAT$, so there's no work needed at all.

To get from $VERTEX$ $COVER$ $(VC)$ to $CLIQUE$ we can do a couple of short jumps, that'll also put another problem in the loop. $VC$ is the dual of $INDEPENDENT$ $SET$ $(IS)$, that is, we can find a vertex cover of size $k$ in a graph $G$ iff we can find an independent set of size $n-k$ in $G$. Play around with this a little and you'll see why this is true. If we then take the edge-complement graph $\bar{G}$ of $G$, an independent set of size $t$ in $G$ is the same as a clique of size $t$ in $\bar{G}$, so that gets us to $CLIQUE$.


Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'? I am new to this and an amateur... please help.

My Question in practical terms:
Given The three following inputs... determine the number of unique group arrangements as an ordered set.

INPUT:
'a' = Students
'b' = Groups
'c' = students per group

OUPUT ANSWER:
'z' as an integer

OUTPUT RULES:
 - All elements considered are ordered from left to right starting with the smallest number.
 - Order is not important... (1,2,3)=(2,3,1)=(3,2,1)=(3,1,2)=(1,3,2)=(2,1,3)...THEREFORE (1,2,3) is the only unique group that is to be counted.

Problem Example #1:
I have 12 students that I need to arrange into 4 groups.  I want the 4 groups to each contain 3 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 880 ordered arrangements.
[Output Format: (1,2,3)(4,5,6)(7,8,9)(10,11,12)]

Problem Example #2:
I have 12 students that I need to arrange into 3 groups.  I want the 3 groups to each contain 2 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 13,860 ordered arrangements.
[Output Format: (1,4)(3,6)(7,11)]

Problem Example #3:
I have 24 students that I need to arrange into 3 groups.  I want the 3 groups to each contain 6 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 125,847,260 ordered arrangements.
[Output Format: (1,2,3,4,5,6)(9,10,11,12,13)(15,16,17,18,19,20)]

Unless I am mistaken, these are not 'combinations' or 'permutation's or 'complete sets' or 'hoyosa index'.  So, for lack of better terms I am calling them ordered sets within ordered groups for now.

Is there a known formula to generate the answer without generating all possible solutions and searching?

20130822---ADDENDUM---
The numbers provided are accurate. The closest description tat I can call relate this to would be "Independent Edge Set AKA Matching"... except that I BELIEVE matching has a limit of two students per group. Sticking to the "Two Students per group" this can be determined using factorials similar to those you have provided.  HOWEVER, I cannot find a formula that allows for the three INPUTS a,b,c as provided and ONLY accounts for unique ordered sets.

Using Problem Example #2:  12 Students (a), 2 groups (b), 3 students (c), = 13,860 unique ordered sets
Set #1[(1,2,3,)(4,5,6)]
Set #2[(1,2,3,)(4,5,7)]
Set #3[(1,2,3,)(4,5,8)]
... Set #13,860 [(7,8,9)(10,11,12)]

Here the explanation for the numbers we found in the comments, which unfortunately do not match yours. If you have additional explanations I can delete this answer, or perhaps improve.

Goal: given $a$ students, make $b$ groups, each consisting of $c$ persons, $bc \le a$. What is the number of possibilities?

My assumptions, the groups are unordered, so $(1,2,3)$ is the same group as $(3,1,2)$. Also the solution $(1,2)(3,4)$ is equal to $(3,4)(1,2)$

Put your students in a row: $a!$ possibilities. The first $b$ students form the first group, the next $b$ students the second group, etc. The order in the line-up between each group of students does not matter, so we have to divide by th1s number of possibilities which is $(c!)^b$. Again we divide by $(a-bc)!$ the number of permutations of the not chosen ones. Also, the order of the groups themselves does not matter, we additionally divide by $b!$.

Answer: $a!\;/\;{(c!)^b (a-bc)! \;b!}$

Another way of obtaining the same number. Choose a group of $c$ students from total $a$, then a group of $c$ students from the remaining $c-b$, etc. This can be done in ${a \choose c}{a-c\choose c}\dots{a-c(b-1)\choose c}$. Again I divide by the possible orderings of the groups which is $b!$.
Thus $\frac{a!}{c!(a-c)!}\frac{(a-c)!}{c!(a-2c)!}\dots \frac{(a-(b-1)c)!}{c!(a-bc)!} / b!$

Your first example $a=12$, $b=4$, $c=3$. You have 880, this number is 15400.

Second example  $a=12$, $b=3$, $c=2$. 13680, we agree.


NFA's number of states I have read that  the NFA size (i.e., the number of states) is linear in the number of characters in the regular expression. This holds even in the presence of character repetitions.

I would like to know why is it so?

If I have a pattern like this , [b-d]at then the number of states will be just 4 incase of NFA ? Size of DFA for this regular expression will also be 4?

What is meant by NFA size is linear in the number of characters in the patternset is that there exists constants $A,B$ such that every pattern of length $n$ is accepted by some NFA of size at most $An+B$. This is proved by structural induction on the patternset, and is a rather straightforward exercise.

Without knowing the constants $A,B$, you can't predict what the general claim gives you for any particular pattern. If you work out the proof, you will get values for $A,B$, and then you will be able to obtain a bound on the NFA size for your sample pattern; that bound probably would be worse than $4$. DFA size could be much bigger. For example, for an alphabet of size $n$, the set of all words not containing all characters has a description of size $O(n^2)$, but has DFA size $2^n$ (NFA size is $n$ or $n+1$, depending on the definition).


A Hexastore data structure I'm reading an article about indexing in Redis. There is a link to so-called Hexastore, it's referred to as a data structure. The link doesn't work, which makes me feel I'm missing something.

I understand from the article that

  the hexastore provides a representation for relations between objects,
  formed by a subject, a predicate and an object. A simple relation
  between objects could be

  antirez is-friend-of matteocollina

What are the key use cases of Hexastore as a data structure? Which indexing problems can it solve along with the quoted example above? How does it work?

There is a paper about Hexastore on the internet, which has a long explanation. Could anybody put it in a nutshell?

I only skimmed the paper for 10 seconds, but AFAICS, the fundamental idea (and the reason why it is called the Hexastore) is that the relationship triple (Subject, Relationship, Object) is stored in all 6 of its permutations separately:

(Subject, Relationship, Object)
(Subject, Object, Relationship)
(Object, Relationship, Subject)
(Object, Subject, Relationship)
(Relationship, Subject, Object)
(Relationship, Object, Subject)

Now, you can ask any question you want and the answers will only require a prefix search on the index.

Want to know about any relationship between Anna and Billy? Search for (A, B) or (B, A) (order doesn't matter since both are stored). Want to know all of Anna's Friends? Search for (A, f). Want to know about all married couples? Search for (m) and throw away every odd result. And so on.

Whether you are trying to find relationships between two fixed persons, finding a person that a fixed person has a fixed relationship with, finding all pairs of persons that have a particular relationship, finding all relationships a particular person has with anybody, all of that is fast because all of that is just an index search.

The paper does not actually store all six of those in the same index, rather they use six indices. (Whereas I believe the Redis article suggests to use a single index.)


Is Not-STCON is NL-Complete? $STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$
$Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$

I've tried the following proof:
Let $S\in NL$, and let $S^\complement \in coNL$. ($S^\complement$ complement is $S$)
Let $M_S$ be the NDTM  that solves $S$.
$x\in S \iff x\notin S^\complement$, so If I can decide membership in $S^\complement$, I can decide membership in $S$. Then I claim that $x\in S^\complement \iff(G_x,v_0,v_{acc}) \in Co-STCON$, where $G_x$ is the configuration graph of $M_S(x)$, $v_0$ is starting configuration, and $V_{acc}$ is a single accepting configuration.

The problem I have with the proof above is that it has the form $x\in S \iff (G_x,v_0,v_{acc}) \notin Co-STCON$, so I feel like I'm missing something essential here. Is it correct?

Your proof doesn't work, since you're using an oracle reduction rather than a many-one reduction.

To show that a problem $A$ is NL-complete, you need to show that for every $S \in \mathsf{L}$ there is a logspace-computable function $f_S$ such that $x \in S$ iff $f_S(x) \in A$ (that's the definition); it's enough to show such a reduction for a single NL-complete problem $S$ (exercise). You show instead that $x \in S$ iff $f_S(x) \notin A$.

Showing that nonSTCON is NL-complete is actually not so easy. Even showing that nonSTCON is in NL is not so easy; it is equivalent to showing that NL equals coNL. This is a non-trivial result due to Immerman and Szelepcsényi.


Algorithm for evaluating polynomials I'm reading The Algorithm Design Manual and I stumbled upon this problem.
I can't really get my head around this, I don't even know how the number of multiplications could differ, what I mean is that there is no polynomial that would make this algorithm perform poorly.
I also have no idea how this could get improved, every operation seems necessary to me.
Any help would be much appreciated.

The number of multiplications in the algorithm is $2n - 1$, but the number of multiplications in the Horner's method is $n$, which means this algorithm is not optimal.
As mentioned in the Wiki page, Horner's method in evaluating a polynomial is optimal, therefore we can change this algorithm so that it uses the Horner's method.
p = a[n]

for i = n-1 to 0:
   p = p.x + a[i]


Task calendar scheduling algorithm I want to write a scheduling algorithm for the following scenario:

There is a set of tasks to complete, each one with a due date, difficulty (easy, normal, hard) and progress on the task. The idea is that the user specifies the amount of daily hours available to work on tasks, so the algorithm can create a weekly schedule so the user can work in the tasks that require most attention, scheduled within the interval of hours (e.g. from 9:00 AM to 1:00 PM) the user decides. I have thought to require the user to specificate an approximate amount of time it needs to be used to complete each of the tasks.

The criteria would be priorizing the tasks with the nearest due date, highest difficulty and lowest progress first, then go for the tasks with nearest due date, highest difficulty and medium progress afterwards and so on.

What came to my mind was to create a function to calculate the value of a specific task, the higher the value, the more importance it has. With that in mind, sort all tasks by due date and by this calculated value using some greedy technique, but the issue here is what amount of time to dedicate on each task per day.

What kind of algorithm would this be? Is there any solution or book reference?

This issue is simply creating a weighted function modeling the importance of each assignment. The priority function should take into account the difficulty, due date, and other factors you choose with a weighted sum of these factors.

As for the difficulty, my suggestion would be to have a difficulty scale 1-10 that the user chooses, and create your weighted function based on that, so more difficult assignments will have a higher priority.


Complexity for finding a ball that maximizes the number of points lying in it Given a set of points $x_1, \ldots, x_n \in \mathbb{R}^2$ and a radius $r$. Which is the complexity of finding the point with higher number of points at a distance smaller than $r$. E.g the one that maximizes $\sum_{i=1}^n \mathbb{1}_{\|x - x_i\| \leq r}$?

A brute force algorithm would be to go over every point and count the number of points that are at distance smaller than $r$. That would give a complexity of $\mathcal{O}(n^2)$.

Is there a better approach?

It looks like a sublinear algorithm for the Ball Range Counting Problem isn't known for now.

However, if you could accept a non-exact answer then you could approximate a disk by a set of squares with different orientation. For each orientation you'll have to build a Range Tree, which will allow you to count all points inside a square in $O(log^2(n)+k)$ time (k - a number of resulting points).

Each range tree will require $O(n \cdot log(n))$ memory, the better approximation you want the more orientations you should use. For example, two orientations will give you an octagon, which approximates a disk with area error less than 6%.


Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time? So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time complexity faster than O(N log N)? So I'm going to go into what I've been pondering, but have a couple specific questions at the bottom.

Comparision based
So the baseline case would just be to compare every element in array_a against every element in array_b, being O(N^2). So what I was thinking was using a sort O(N log N), and then iterating through each of the arrays, making comparing array[i] with array[i+1], if they are not equal, copy array[i] to a new array (or a linked list, since I'd just be accessing it in order for the next step) and then increment i, so that way I have arrays without duplicates. Then do a preliminary check to see whether the # of elements are the same in both lists. Then with the list, compare whether the first element in the linked lists are equivalent, then check the next node in the linked list, and so on. If all checks are equal then they represent the same set. So this would be O(N log N). Doing a sort with a tree might work as well, but again would still be in the same complexity class of O(N log N)...

Hashing?
So what I was thinking initially was looking at using hashsets to remove duplicates since operations with those would be amortised constant time, doing a preliminary check by checking whether both arrays have the same amount of distinct elements, adding the hashes of the elements of both arrays if they are not equal then there's no point in checking every element of each array and comparing it so that way a response of false would be relatively quick, if they are equal, then to check against collisions I'd sort it and then check arr_1[i] with arr2_[i] for i = 0, ..., n-1 - so the step of sorting would be the slowest giving this a time complexity of O(n log n) based on the sorting function used.

Questions
Other than using hashing-based structures or algorithms that would require elements to be sorted first,, what other data structures (like trees would work I'd supposed) could I use to remove duplicates in an efficient way? Are there any novel data structures (even if impractical in practice) or different approaches for removing duplicates?

If the only information known about the sets is that they have a total order relation, would this make any impact on whether each element can be hashed and the quality of the hashes on a theoretical point of view?

Are there any properties in set theory that I could exploit somehow for a faster algorithm design in a language-agnostic way?

I believe a hashing approach should give you $O(N)$ time, where $N$ is the length of the longer array (we can relax the constraint that they are the same size).

Simply put all the elements in the first array into a hashset, and then check whether each element in the second array exists in the hashset.

You could even account for duplicates by instead using a hashmap and storing the counts of each element in the first array. When checking elements in the second array for inclusion (or nonzero value), decrement the value of each key that is a match.


What is the best way to avoid using goto statements in the pesudocode for an algorithm? What is the best way to avoid using goto statements when writing the pseudocode for an algorithm?

I want to avoid it and use another way to replace it.

In many cases, GOTO statement can be replaced by loops. For example, in your case, the inner loop is just "while string(i) = path(j), decrease both i and j", and the outer loop is a "loop forever", also known by the C idiom "while true".


What are the tradeoffs between implenting dataframes as a series of columns vs a series of tuples I was reading the documentation for Julia's Dataframe package, and the package implements Dataframe by a series of a columns each of a single type. From reading the docs, it looks like that's how R implements Dataframes as well. Is there any reason this is a better way than having a Dataframe being a collection of tuples with elements of different types? The later seems more natural to me.

What are the trade-offs or reasons one would implement Dataframes as a list of columns vs a list of rows?

At the level of an actual implementation, Array of structures versus structure of arrays makes an enormous performance difference; particularly when SIMD parallelism is involved.  If you want to add together all of the values of one field, then all of those values are sitting next to each other.

SIMD instructions add/mul entire arrays all at once, rather than looping over each struct member.  If you need to jump around memory to add all of these, you will invalidate memory caches.  Also, suppose that only one column has non-default values, and the other dozen columns have zero values.  The implementation can simply not bring over columns that are all zero.  Run-length coding can be used on columns, or differential encoding.

In the BigData world, there are different serialization standards in use.  Parquet is one option, picked because it has these characteristics due to being a columnar format.  These kinds of formats are oriented towards doing stream processing.  For example: you can get the next 1024 rows as a batch out of a cursor, but as an implementation detail they are packed in a columnar format.


Rigorous reason against the seemingly wrong way of substitution Let us consider the lambda calculus expression .

$ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$

Now $\lambda x.x$ is seen as an argument . How to decide which bound variable should the value of the argument go to ?

The books I am going through suggest that in this kind of case when there is one argument available  the first bound variable should take that arguments value .

To the best of knowledge I don't remember reading anything rigorous till what Ii have covered of these books that would provide rigorous reasoning as to why the first argument should go to the first bind variable .

I understand it makes sense and a meaningful expression when seen as a function demanding two arguments but being provided one as it makes a function again demanding one more argument . This thing is provided in every introduction to functional programming but still somehow I wonder if we can rigorously show that the first bound variable should be taking the value of the first argument .

I have read about beta reduction and I tried applying that to the above expression :

so  $ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$
can be seen as $ (\lambda func.(\lambda arg$ $( func$ $ arg))$ $\lambda x.x)$
and will be in a form $ (\lambda x$$.M) N$ form  so here I can justify the first argument being used for  $func$.

But can I not see it as follow :
$ (\lambda func.((\lambda arg$ $( func$ $ arg))$ $\lambda x.x))$ thereby making it in a form  :

$ \lambda func.($ $( \lambda x .M)N$) thereby allowing the second bound variable to take the value of the argument ?

So how to provide a rigorous reason for the first bind variable taking the first argument ?

You're not going to find a rigorous reason, because there is no semantic reason. The reason is purely syntactic.

The key is to remember that lambda calculus expression are, in fact, trees. A node is either a variable, with no children, an application with two children, or a lambda, with two children, one of which is the variable it binds.

Trees are hard to write, so we have a syntax for writing expression trees in a linear way. If we wrap every expression in parentheses, there's an unambiguous mapping between linear expressions and trees. But any time that parentheses are missing, we need precedence rules to disambiguate.

The choice of precedence rules is arbitrary, and is purely catered towards human understanding.

Once you're working with trees, or at least fully parenthesized expressions, then it should be more clear why the argument is given as the outermost bound variable: application is a binary operation between siblings in the trees. Other than the substitution operation, we don't want to have to look up or down the tree when applying a reduction.

If you want a syntax where you don't always apply arguments this way, you may be interested in the spine calculus, which is a syntax that nicely captures the idea of applying multiple arguments to a single core, called the head.


computer science in the movies as an educational angle recently there have been a few questions on teaching CS in both cs.se & tcs.se and there are many high-rated related questions on the two sites on the topic. thinking over the latest one made me realize that a lot of students get exposed to some aspects of STEM through the media (sometimes inaccurately), and one of the most powerful media outlets is movies.

it seems that maybe instead of rolling ones eyes or recoiling from their unrealism, these have some potential and can be used as a teaching tool (aka "teachable moment") by taking them as a student experience to build on, as case studies for students to learn about certain concepts and how the concepts actually work vs the screenwritten, "hollywood" version, ie address (possible widespread?) misconceptions about the field and its essential aspects.

  what are key or compelling movies introducing CS-type concepts and what is accurate/inaccurate about the portrayal? [or is it roughly correct?]

teaching high school TCS tcs.se
what should I do with a bunch of 16/17yr olds to get them interested in CS cs.se

I haven't seen it yet, but Travelling Salesman could be pretty interesting.


Simulation BPP by Pseudorandom Generator I use the following scribe to study  Pseudorandom Generators.

The most intriguing question for me is how exactly PRG can be used in order to simulate BPP.

Let $A(x,r) \in BPP$, where $x$ is primary input and $r$ - randomness provided by BPP. Instead of $r$ we can provide $A$ with pseudorandom input $G(U_{d(n^c)})$ and according to the Claim 7.6 from the scribe. $A$ with pseudorandom input differs from $A$ with random $r$ in less than half of running cases. The proof of Lemma shows that if it's so, that there is a distinguisher that distinguishes $U_{d(n^c)}$ from $U_{n^c}$ with advantage at least $\frac{1}{2} - \frac{1}{3} > \frac{1}{8}$ which is contradicts to the definition of PRG.

Q: Where this advantage comes from? I simply don't understand what these numbers mean.

Q: Construction question. Why do need to run over all seeds of length $d(n^c)$ there are $2^{(d(n^c))}$ such string. For me it sounds like a strengthening of randomness because after that we use the majority as a result. But actually why do need that, why we cannot use single seed of length $d(n^c)$.

Q:Philosophical question. Why do we need PRG to be non-uniformly strong? Why we cannot use uniformly indistinguishable PRG? I saw the idea that the primary input $x$ to the $A$ can be used as advice, but I still don't understand why do we need it.

The idea of a PRNG is coming up with a "deterministic" sequence that "looks like" random, in the sense that programs getting access to it act (roughly) as if they had access to a completely random string. The PRNG takes a seed or a key, and outputs a larger pseudorandom sequence. When simulating some probabilistic algorithm, instead of choosing a completely random string, it is enough to choose a random seed and use a PRNG.

How would you use a PRNG to simulate (say) a BPP algorithm? Suppose we had a PRNG that takes a seed of length $L = O(\log n)$, and $\epsilon$-fools every BPP algorithm. (Pseudorandom sequences don't look completely random, but in this case, using them instead of a random sequence changes the probability of any event by at most $\epsilon$.) That means that if we pick the seed at random, then the BPP algorithm returns the correct answer with probability at least $2/3-\epsilon$ (supposing that the original success probability was $2/3$ - that depends on your definition of BPP). If $\epsilon < 1/3$, then we have the following property:

If we run the algorithm on a YES instance and a random seed, then it returns YES with probability larger than $1/2$.
If we run the algorithm on a NO instance and a random seed, then it returns YES with probability less than $1/2$.

This property assumes we choose a random seed, but we wanted a deterministic algorithm. To that end, we go over all possible seeds, and calculate the probability that the algorithm returns YES. This is just the number of times that the algorithm returns YES divided by $2^L$. If the probability is larger than $1/2$ then it's a YES instance, otherwise its a NO instance. If indeed $L = O(\log n)$, then $2^L$ is polynomial, and we obtain a deterministic polynomial time algorithm.

Now regarding your questions:

I haven't looked at the scribal notes, but the advantage might come from the BPP algorithm.
Looking at a fixed seed is the same as looking at a fixed "random" sequence - you don't need a PRNG for that. All you know is that on average, the performance of the algorithm on a pseudorandom sequence correlates with whether the input is a YES or a NO instance. That doesn't say anything about a single seed.
As to uniformity, the program that your PRNG should fool is $A(x)$ for an arbitrary input $x$. While $A$ is a uniform circuit, $A(x)$ isn't, since $x$ could be arbitrary. Your PRNG should fool at one and the same time $A(x)$ for all possible inputs $x$.


Does the language of TM's that repeat a configuration infinite times semi-decidable or not? Let us define the following languages:

$$ {L_1 = \{\langle M\rangle :  M  \ \text{is a TM and $\exists w\in \Sigma^*$ s.t $M(w)$ repeats a configuration infinite times}\}} $$

$$ L_2 = \{\langle M\rangle :  M  \ \text{is a TM and on all inputs there exists a configuration  that repeats infinite times}\} $$

My question is what class does this languages belong to ($\mathcal{R},\mathcal{RE\setminus{R}}, etc...$)?
I have shown that:

${H_{TM}}\le_m L_2$:
On input $\langle M,w\rangle$ return a new $TM$ $\langle M' \rangle$ such that on all inputs, runs $M$ on $w$. Keep a counter at the beginning on the number of steps (to avoid entering the same configuration infinite number of times, if it doesn't stop). If it does stop, repeat some configuration in a loop.

So that seem to prove that $L_1,L_2\notin \mathcal{R},\mathcal{co-RE}$.

But is it in $\mathcal{RE}$? I couldn't write a $TM$ that accepts those languages, nor derive a reduction from $\overline{H_{TM}}$, $\overline{A_{TM}}$ or any other relevant language.

Any ideas on solving this? Thanks!

$L_1$ is indeed recursively enumerable. Suppose for simplicity that the input consists of a pair $M,w$ and you want to know whether $M$ repeats a configuration during its computation on $w$. You can then loop over the integers, and for each $n\in\mathbb{N}$ check if $M$ repeats a configuration with input $w$ during the first $n$ steps. This is possible since during the first $n$ steps $M$ uses at most $n$ cells from the tape, hence the number of possible configurations is finite (you can store them in memory and mark those which were seen).

Now, you want to add an additional existential quantifier over the words $w$, and this can be achieved by dovetailing. Simultaneously scan words and computations length, i.e. for each $n$ and for all words of length $\le n$, check if $M$ repeats a configuration during its first $n$ steps.

The additional universal quantifier prevents $L_2$ from being recursively enumerable, you can show this by reduction from the complement of the halting problem. Given $(M,w)$, your reduction outputs a machine which on input $x$ simulates $M$ on $w$ for $|x|$ steps, and enters a loop iff $M$ did not halt in this time.


Is there any algorithm can solve the following equations efficiently? $$ x_1 + x_2 + \cdots +x_n = c_1 $$
$$ \frac{x_1^2}{2} + \frac{x_2^2}{2} + \cdots +\frac{x_n^2}{2} = c_2 $$
$$ \cdots $$
$$ \frac{x_1^n}{n!} + \frac{x_2^n}{n!} + \cdots +\frac{x_n^n}{n!} = c_n $$

$c_1,\cdots,c_n$ are known constants. $x_1 \cdots x_n$ are the unknown variables to solve.

One way, which is numerically probably a bad idea, is to use Newton's identities. They give the value of the elementary symmetric functions given the power sums, and from the elementary symmetric functions you can construct a polynomial whose roots are the answers to your problem. Let $p_k = k! c_k$, and let $e_k$ be the sum of all $\binom{n}{k}$ products of $k$ variables out of $x_1,\ldots,x_n$. Newton's identities state that
$$ ke_k = (-1)^{k-1} p_k + \sum_{i=1}^{k-1} (-1)^{i-1} e_{k-i} p_i. $$
Using these identities, you can compute $e_1,\ldots,e_n$. Now consider the polynomial
$$ P = x^n + \sum_{i=1}^n (-1)^i e_i x^{n-i}. $$
The unique solution to your equations are the $n$ roots of $P$.
As an example, let's do the case $n = 2$. We have $e_1 = p_1$ and
$$ 2e_2 = -p_2 + e_1 p_1 = p_1^2 - p_2. $$
The polynomial $P$ is therefore
$$ x^2 - p_1 x + \frac{p_1^2-p_2}{2}. $$
For $n=3$ we calculate additionally
$$ 3e_3 = p_3 - e_1 p_2 + e_2 p_1 = p_3 - p_1 p_2 + \frac{p_1^2-p_2}{2} p_1 = \frac{2p_3 - 3p_1p_2 + p_1^3}{2}. $$
The polynomial $P$ is therefore
$$ x^3 - p_1 x^2 + \frac{p_1^2-p_2}{2}x - \frac{2p_3 - 3p_1p_2 + p_1^3}{6}. $$


In propositional logic how is the negation equivalent? I am unable to understand how the negation of a sentence into CNF actually makes sense, hopefully somebody can explain it to me in understandable terms!
Given the sentence: If the battery is charged (A) and the screen is not cracked (B) then the phone is working (C)
The following makes perfect sense:
(A ∧ B) => C
I cannot get my head around how the negated form is true or how it works:
¬A ∨ ¬B ∨ C
I am struggling because "not A" means if the battery is not charged? So I cannot see how if the battery is not charged or the "screen is cracked" or the "phone is usable".
If A is false, so battery is not charged, how is that applying ¬A to it does not make it now true?
Any help would be appreciated.

First thing is to accept and understand, that $A \Rightarrow C$ is same as $(\neg A) \lor C$. Using your example we obtain, that "If the battery is charged, then the phone is working" is same with "the battery is not charged or the phone is working".
Now following initial sentence $(A \land B) \Rightarrow C$ we have $\neg(A \land B) \lor C$, where last sounds as "not fulfilling (the battery is charged and the screen is not cracked) or (the phone is working)".
Now we come to negation of $\neg(A \land B) = (\neg A) \lor (\neg B)$. So sentence "not fulfilling (the battery is charged and the screen is not cracked)" is same as "(the battery is not charged) or  (the screen is cracked)"
Putting everything together we have
$$(A \land B) \Rightarrow C \text{ is same with } (\neg A)  \lor (\neg B) \lor C $$
in words last is "(the battery is not charged) or  (the screen is cracked) or (the phone is working)"


Why is the intersection of these two Languages Recursively Enumerable, not Recursive? I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language L3, L3 ∩ L1 is recursively enumerable. But I thought it would be recursive?

Now, the text and I came to the same first conclusion - that it is important to deduce that L1 is a recursive language, since it is regular, and go from there - but my understanding is that if a recursive language had an undecideable intersected, you'll either get the empty set (which is recursive) or you'll get a set of elements common to both. Since all elements in a recursive must lead to halting, then the elements of the intersection all must lead to halting.

Hence '(recursive) ∩ (rec enu but not recursive)' and so 'L1 ∩ L3' should be recursive?

I must have gone wrong somewhere because the text, without explanation, just says it's recursively enumerable - where have I gone wrong? Thanks for your insight.

Let $L_1$ be the full language. Certainly, $L_3 \cap L_1 = L_3$, which by assumption is not recursive.

I didn’t fully follow your reasoning in the second paragraph, but you might want to think some more about which Turing machine “must lead to halting” refers to. In particular, a Turing machine for our $L_1$ will halt on every string, but this does not tell you that any subset of the full language is recursive.

Edit: I’ll try to address your comments here where I have more space.

We are dealing with a double set structure: At the lowermost level, we have words. Languages are set of words, but we are also talking about sets of languages, i.e., sets of sets of words, such as the set of regular languages. The relationship between regular, recursively enumerable and recursive languages happens on the upper level: Let $L$ be any regular language, which means that it is accepted by a finite automaton $\mathcal{A}$. Because every finite automaton $\mathcal{A}$ can be implemented as a Turing machine $\mathcal{M}$, we know that $L$ must also be a recursive language. Since every such element $L$ of the set of regular languages is an element of the set of recursive languages, the former is a subset of the latter.

This does not mean much on the level of individual words. Let’s again take the language $L_1 := \Sigma^*$ of all words. This language is decided by the Turing Machine $\mathcal{M}_1$ that always accepts. Thus, $L_1$ is in the set of recursive languages and every word “leads to halting” for the specific machine $\mathcal{M}_1$. Now let us consider the language $L_3$ of Turing machines that terminate on the empty input. It can be accepted by a universal Turing Machine $\mathcal{M}_3$, so the language is recursively enumerable (and we know that it is not recursive). Sure, every word in the intersection of $L_1$ and $L_3$ will make both $\mathcal{M}_1$ and $\mathcal{M}_3$ terminate and accept.

But how do you build a single Turing machine from that that still accepts the intersection and will reject everything else? The first attempt would be to simulate both Turing machines and accept if both accept. As soon as one rejects, you reject. Indeed, this machine accepts the intersection and proves that the intersection is recursively enumerable. But if $\mathcal{M}_1$ accepts and $\mathcal{M}_3$ diverges, your machine will also diverge. To reject, you would have to figure out in finite time whether $\mathcal{M}_3$ is diverging on the current input or just takes a long time to accept. This is not possible to do for all inputs.


k-tape turing machine I want to create multi-tape Turing machine that recognize language {ww,  $w \in {a,b}$}. With condition that max. steps is less or equal than $\frac{3}{2}\left | x \right | + 2$. Where x is word from language. I have an idea to create x-tapes to solve this problem, but can be the number of tapes not known before reading from input(read-only) tape, and for n-length there will be n-tapes, is that possible ?

All Turing machines are fixed in advance, independent of the input. This applies to all aspects of the machine: the state set, the alphabet, the transition function, the number of tapes. The only thing that changes from input to input is the input!


How to create RGB-colors with equal vector norm? I am trying to do the following:

Interprete RGB color values as a 3-D vektor
Transform the RGB color into polar coordinates L, teta and phi
Create colors with constant L

The math behind this is the standard transformation into spherical coordinates:

b = L * Sin(teta) * Cos(phi)
r = L * Sin(teta) * Sin(phi)
g = L * Cos(teta)

With L beeing the norm of the RGB vektor I want to create.

L=(r^2+b^2+g^2)^0.5 'between 0 and 441.67 = sqrt(3)*255

So far so good. Onto the first issue: r,g and b need to be between 0 and 255

This means that this holds true (I calculated that myself, it's possible that it has errors in it):

If L>255 Then
   arccos(255/L) < teta < pi/2 - arccos(255/L)
   arccos(255/L) < phi < pi/2 - arccos(255/L)
End If

Here my calculations:

The idea is that teta goes from (pi/4 - delta) to (pi/4 + delta) where
Which basically means that teta and phi are restricted in what they can be according to the ratio of 255/L. This restriction gets upto a point were L=441.67 the maximum length. Here phi and teta can only be pi/4.

I think upto this points my conclusions are valid, but there is a problem I cannot figure out.

If phi = teta = pi/4 and L = 441.67 the RGB value should be (255,255,255) and the forumlas above yield: RGB= (221,255,221)

Which is what the forumlas for r,g and b above yield if phi = teta = pi/4 and L = 441.67 are inserted.

So how would one generate RGB vektors with a constant norm that are still valid RGB values? (0 < r,g,b < 255)

So how would one generate RGB vectors with a constant norm that are still valid RGB values? ($0 \le r,g,b \le 255$)

There is a simpler algorithm. Let $L$ be the given norm.

Verify that $0\le L\le 255\sqrt3$.
Let r be a random number between $\sqrt{L^2-\min(2\cdot255^2, L^2)}$ and $\min(255, L)$.
Let $M=\sqrt{L^2-r^2}$. Let g be a random number between $\sqrt{M^2-\min(255^2, M^2)}$ and $\min(255,M)$.
Let $b =\sqrt{L^2-r^2-g^2}$.

Some minor adjustment is needed if $r,g,b$ should be integers, in which case only approximate solutions can be found in general.

Here is the right computation if we want to find the range of $\theta$ and $\phi$.

If $0\le L\le 255$, then $0\le\theta,\phi\le\pi/2$
If $255\lt L\le 255\sqrt3$, let $M=\sqrt{\max(0, L^2-2\cdot255^2})$.
we have
$$\begin{align}
&\quad\quad\begin{cases}b = L \sin(\theta) \cos(\phi)\\
r = L \sin(\theta) \sin(\phi)\\
g = L \cos(\theta)\\
0\le b,r,g\le 255\\
0\le\theta,\phi\le\pi/2
\end{cases}\\
&\Longleftrightarrow
\begin{cases}b = L \sin(\theta) \cos(\phi)\\
r = L \sin(\theta) \sin(\phi)\\
g = L \cos(\theta)\\
\sqrt{\max\left(0,(L\sin(\theta))^2-255^2\right)}\le b,r\le \min(255,L\sin(\theta)) \\
M\le g\le 255\\
0\le\theta,\phi\le\pi/2,\, \theta\not=0
\end{cases}\\
&\Longleftrightarrow
\begin{cases}
\sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta}\right)^2\right)}\le \cos(\phi)\le \min\left(1, \dfrac{255}{L\sin(\theta)}\right)\\
\sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta}\right)^2\right)}\le \sin(\phi)\le \min\left(1, \dfrac{255}{L\sin(\theta)}\right)\\
\dfrac{M}{L}\le \cos(\theta)\le \dfrac{255}L\\
0\le\theta,\phi\le\pi/2,\, \theta\not=0
\end{cases}\\
&(\text{the inequalities on}\cos\phi\text{ put on the same restrictions on }\phi\\
&\text { as the inequalities on }\sin\phi)\\
&\Longleftrightarrow
\begin{cases}
\arccos\left(\min\left(1, \dfrac{255}{L\sin(\theta)}\right)\right)\le \phi\\
\phi\le\arccos\left(\sqrt{\max\left(0,1-\left(\dfrac{255}{L\sin(\theta)}\right)^2\right)}\right)\\
\arccos(\dfrac{255}L)\le\theta\le\arccos(\dfrac{M}{L})
\end{cases}
\end{align}
$$

The formula above tells a way to generate RGB vectors with a given norm $L$. Select $\theta$ and $\phi$ in the range given by the inequalities. Compute $r,g,b$ accordingly.

In particular, if you take $L=255\sqrt3=441.67$, then $\dfrac{255}L=\dfrac{M}L=\dfrac3{\sqrt3}$. $\theta=\arccos(255/L)=0.9553$. Since $\dfrac{255}{L\sin(\theta)}=0.7071$, we will get $\arccos(0.7071)\le \phi\le\arccos(0.7171)$. So $\phi=\pi/4$ and we will arrive at $b=255$, $g=255$ and $r=255$, which is the only possible combination of RGB vector for that value of $L$, as expected.

There have been several computational mistakes in the question. There has been a few in the previous versions of this answer as well. The comments below this answer might have become irrelevant.


Is computer science really a branch or sub-branch of physics? Given that a computer is basically an electronic machine, is computer science really a branch of electronics, which is in turn a branch of physics?

No it is not. Computer science has as much to do with computers as astronomy does with telescopes: they're a tool.

Even if computers didn't exist the science of computing things still would. IMO Computing Science would be a much better name, but we're stuck with what we have I guess.


How to rank these functions in increasing order of complexity [Algorithms]? I have the following functions:

What is the correct order of these functions in increasing complexity?
I could always start entering values in these functions and check the corresponding output to notice the rate of increase. But is there a better, faster way of ranking these functions in order of increasing complexity? For example are there rules of thumb I could use to quickly sort these in order of increasing complexity? (Like I know generally exponential functions are more complex than log functions)

I solved it after understanding asymptotic notation and the complexity of some common functions. Here's the order from least expensive to most expensive:

  log log n, log n ~ ln n, (log n)^2, sqrt(n), n, n log n, n^(1+x), n^2,
  n^3, n-n^3+7n^5, 2^(n-1) ~ 2^n, e^n, n!


How to find middle element of linked list in one pass? One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.

By cheating, and doing two passes at the same time, in parallel. But I do not know whether the recruiters will like this.

Can be done on a single linked list, with a nice trick. Two pointers travel over the list, one with double speed. When the fast one reaches the end, the other one is half-way.


Turing Machine where branches are resolved via arbitrary operator Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is there a name or theory behind the class of Turing Machines where there is no restriction to the Boolean space and the any/all operators?

For example, I want a machine where terminal states output real values and non-terminal states use the min operator to combine the outputs of branches.

Additionally, are there subclasses of this class? I imagine operators which have certain properties (associativity, idempotence, and especially properties related to ordering or transitivity) would have interesting guarantees regarding interruptibility in the same way that a machine using only the any operator can terminate as soon as it finds one accepting state.

Using any/all (a.k.a. or/and) gives rise to alternating Turing machines. Goldschlager and Parberry (On the construction of parallel computers from various bases of boolean functions, Theoretical Computer Science 48:43–58, 1986) consider the generalization to allowing arbitrary Boolean functions, and they call the resulting machines extended Turing machines.

To me, it would make sense to use the same term for what you're proposing. I suggest following the references in Goldschlager and Parberry and looking up who's cited them, to see if the term "extended Turing machine" stuck and if it's been applied to your scenario.


The difference between dense graph and sparse one How to decide whether the following statement is correct?

O(E log E) and O(E log V) are equivalent regardless whether graph is dense or
sparse

You have to be careful with your definitions. For any graph, the number of nodes and the number of edges is a constant, so $O(V) = O(E) = (1)$. This is clearly not helpful.

Sparse and dense only make sense for a family of graphs $\{G_n\}_{n=1}^\infty$.

The edge density of a graph $G$ is the proportion of possible edges that a graph actually has:

$$ D = \frac{|E(G)|}{{|V(G)|}\choose{2}}. $$

The edge density of a family of graphs is

$$ D = \lim_{n \to \infty} \frac{|E(G_n)|}{{|V(G_n)|}\choose{2}}. $$

The family is sparse if $D = 0$ and dense if $D > 0$. You must analyze the performance of your algorithm under either type of family as inputs.

This definition is from Diestel's Graph Theory.


Confluence to show equivalent terms have one common reduct In lemma 30.3.9, Pierce states a confluence property for $F_{\omega}$:

  $S \to_* T \land S \to_* U \implies \exists V. T \to_* V \land U \to_* V$

He then states the following proposition:

  $S \leftrightarrow_* T \implies \exists U. S \to_* U \land T \to_* U$

However, he doesn´t use the above property to prove it. I remember this was the case for other books on term rewriting systems that I read. However, to me it looks very simple to prove using the confluence lemma.

From $S \leftrightarrow_* T$ one has $S \to_* T$ and $S \to_* T \to_* S$ thus by confluence $\exists U. S \to_* U \land T \to_* U$.

Why is this approach not correct?

$S \leftrightarrow^* T$ does not mean that $S \rightarrow^* T$ and $T \rightarrow^* S$! It means that there is a chain of reductions $S = S_0 \rightleftharpoons_1 S_1 \rightleftharpoons_2 S_2 \rightleftharpoons_3 \cdots \rightleftharpoons_n S_n = T$ where each of the $\rightleftharpoons_i$ might be either $\rightarrow$ or $\leftarrow$. The directions can alternate any number of times.

The confluence property does imply generically that if $S \leftrightarrow^* T$ then there exists $W$ such that $S \rightarrow^* W \leftarrow^* T$, but it takes a bit more work to show it. You can combine reductions in $S \leftrightarrow^* T$ to group consecutive reductions in the same direction together: $S = T_0 \leftarrow^* U_1 \rightarrow^* T_1 \leftarrow^* U_2 \rightarrow^* T_2 \leftarrow^* \cdots \leftarrow^* U_n \rightarrow^* T_n = T$. By confluence on $T_{n-1} \leftarrow^* U_n \rightarrow^* T_n$, there exists $V_n$ such that $T_{n-1} \rightarrow^* V_n \leftarrow^* T_n$. So we have $T_{n-2} \leftarrow^* U_{n-1} \rightarrow^* T_{n-1} \rightarrow^* V_n \leftarrow^* T_n$.

$$
\begin{matrix}
    &            & U_1 &            &     &        &         &            & U_{n-1} &            &     &            & U_n &            &     \\
    & _*\swarrow &     & \searrow^* &     & \cdots &         & _*\swarrow &     & \searrow^* &     & _*\swarrow &     & \searrow^* &     \\
T_0 &            &     &            & T_1 &        & T_{n-2} &            &     &            & T_{n-1} &            &     &            & T_n \\
    &            &     &            &     &        &         &            &     &
           &     & \color{green}{\searrow^*} &     & \color{green}{_*\swarrow} &     \\
    &            &     &            &     &        &         &            &         &            &     &            & \color{green}{V_n} &            &     \\
\end{matrix}
$$

Now apply the confluence property again to $T_{n-2} \leftarrow^* U_{n-1} \rightarrow^* V_n$, getting $V_{n-1}$ such that $T_{n-2} \rightarrow^* V_{n-1} \leftarrow^* V_n \leftarrow^* T_n$. Repeat until you get $W = V_1$ such that $T_0 \rightarrow^* V_1 \leftarrow^* T_n$. Formally, this is a proof by induction on the number of alternations of directions in the chain $S \leftrightarrow^* T$. Confluence lets you remove one alternation at a time. In more colorful language, confluence lets you “pop a crease”; each time you pop a crease, you join two depressions together, and if you keep doing that, you eventually get a single depression.


How to reduce constrained proofs to 0-1 IP Consider the following problem:

Can $X$ be proven in fewer than $Y$ steps, from axioms $Z$, with finitely many transition rules $\tau$?

This lies in $NP$, since if I supply a proof $M$, and individual steps can checked against the list of possible transitions $\tau$ in polynomial time, then $M$ can be checked for length $<=Y$ in linaer time, and verified for correctness in $Y*O(n^{O(1)})$

What isn't clear is how to reduce this generic "finite resource" automated theorem proving problem, to 3-SAT.

Obviously it should be reducible since $3-SAT$ is NP Complete but it's not clear how to do that.

If your problem is truly in NP, the reduction follows immediately from the Cook-Levin theorem.  You described how to build a verifier for your problem.  The proof of the Cook-Levin theorem shows how to turn that into a 3SAT instance.  Basically, the variables of the 3SAT formulas are the intermediate states of the verifier, and the formula itself says that each pair of consecutive states are consistent and that the verifier ends up accepting.

I am not persuaded by your proof that it is in NP.  Your proof would be fine if $Y$ is provided on the input in unary, but not if it is provided in binary -- in the latter case, the length of the proof is exponential in the size of the input, so your proposed verifier doesn't run in polynomial time.  If the problem is not in NP, there is no (polynomial-time)  reduction to 3SAT.


DFA for at most two $b$'s and at least one $a$ I'm totally new to DFA's and automata in general – this is the first week or two of class that I've actually seen this – and I'm curious as to a pattern to match the following:

"Match the set of all strings on the alphabet $\{a, b\}$ that have at most two $b$'s and 1 or more $a$'s."

Close your eyes. Tell yourself: I am an automaton.

What is my task? Check whether the number of $a$'s is at most $1$ and the number of $b$'s is at least $2$. So I will count $a$'s and $b$'s. My memory holds two numbers, the respective counts. I start with two zero's. When I see $a$ I add one to the first number, when I read $b$ I add one to the second number.

Ah. When the number of $a$'s reaches $2$ I can stop counting them: my test be be always false. When the number of $b$'s equals $2$ I can stop counting them, I have seen enough of them.

Now open your eyes and write down your state diagram: all possible states (=  memory contents) and actions upon reading a letter to another state. Mark the "good" states.

Done.


Regular expression for binary words with 1 in the middle Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$

I'm having trouble finding a solution for this regular expression. I think it's impossible because you need to have an even amount of 1's and 0's on both sides of the middle 1. You also would need to have the same amount of 1's and 0's on both sides. Since a regular expression has limited memory, would that make this regular expression impossible?

The intersection of your language with $0^*10^*$ is $\{ 0^n 1 0^n : n \geq 0 \}$, which can be shown to be non-regular by reduction to the more well-known $\{ a^n b^n : n \geq 0 \}$. This shows that your language indeed isn't regular.


How to reduce language is finite to language is regular? I'm trying to reduce $FIN \leq REGU$, where:

$$FIN = \{ \langle M \rangle \vert T(M) < \infty \} \\ REGU  = \{\langle M \rangle \vert T(M) \in REG\}$$

Now one thing I have done so far is this:

$ w \in FIN \implies | T(M_w) < \infty \implies \exists n \in N: L(M_w) = \{w_0, \ldots, w_n \} \implies \exists  \ \text{DFA} \  A: L(A) = L(M_w)  $

What I want to show now that : "to decide if a language is regular is at least as hard as deciding wether it is finite"

Thats where I'm stuck.

I want to remark that this is not homework but, but a exam preparation question.

First note, that for a regular language, however encoded, it is decidable wether it is finite or not. So you can use the language $REGU$ as an oracle for $FIN$ in the following way: To check if $\langle M \rangle \in FIN$ you ask the oracle $\langle M \rangle \in REGU$? If the answer is no, you can be sure that $\langle M \rangle \notin FIN$ as every non-regular language is infinite. If the answer is yes there is a proof (e.g. an NFA $\mathcal{A}$) that shows that $M$'s language is regular. Then you run your procedure to check whether $\mathcal{A}$ is finite (this is, as mentioned above decidable).


Minimum number of nodes in AVL tree Let T be an AVL tree of height 3. What is the smallest number of entries it can store? Note that a tree with one node (only the root) has the height of zero and stores one element.

The only method I could think of was just drawing an AVL tree and trying to minimize the number of nodes in which I get an answer of 7.

But this method is prone to error in my opinion and I'm not even sure if my answer is correct. So is there any method or equation to solve this without having to graph it?

Prove a lower bound of 7 vertices:

Since the tree is of height 3, it must have a path of length 3 from the root to a leaf, so we already have to have 4 vertices; $r-v_1-v_2-v_3$.  Now r has to have balance factor in $\{1,0,-1\}$ (i.e. $|\text{BF}(r)|\leq1$) so it must have a path of length at least two on it's other subtree, so we have $r-v_4-v_5$ (at least two more vertices).

For the same reasons (BF) $v_1$ has to have at least one child on it's other subtree, so we have $v_1-v_6$ (at least one more vertex).

So we have proved that an AVL tree of height 3 has to have at least 7 vertices, your example shows that there is an AVL tree with 7 vertices, so the minimum is 7.


Minimizing flow on a 2D matrix network I am currently dealing with a problem that I believe to be a network flow related problem, and I am trying to find some similar solved problems to help me formulate my solution. I want to make it clear that I am not searching for a solution here, but asking a community of more experienced individuals if they have experience with/heard of similar problems to what I am about to describe.
Given an nxn matrix, let some small number of matrix indices (I will refer to them as nodes from now on) be colored blue, and rest of the nodes be colored white. Any white node that is adjacent (not including diagonal) to a blue node will become blue unless a block is placed between them. So for example, in a 2x2 grid, if the node at (0, 0) is blue and the rest are white, the whole grid will become blue unless blocks are placed between (0,0) and (0, 1) as well as (0, 0) and (1, 0).
Now, each block placed has a cost of 1, and each white node being converted to a blue node will have some cost greater than zero (the cost will be the same for all white nodes). The goal is to place blocks on the matrix such that the total cost is minimized.
It most problem instances, especially with a low cost of white nodes becoming blue, it will be optimal to let some white nodes suffer becoming blue. For example, going back to the 2x2 problem instance, if each white to blue conversion only costs .25, then letting all the nodes become blue will cost .75, whereas placing 2 blocks would cost 2, and so the minimum cost would be .75 and letting the blue spread across the grid.
I am wondering if anyone can recall a problem instance/algorithm that is similar to what I am attempting to solve and could suggest researching it? I have scoured the internet relating to min-cut/max-flow algorithms, but I am having trouble relating this problem to anything regarding network flow. Any suggestions of problems to research would be much appreciated.

Build a grid graph, with one node per entry in the matrix, and edges between each pair of adjacent nodes.  Also add a source node $s$ with an edge from $s$ to each blue node, and a sink node $t$ with an edge from each white node to $t$.  Set the capacity of each edge to 1, except the $s$-to-blue edges have capacity $\infty$, and the white-to-$t$ edges have capacity given by the cost of allowing that white node to become blue.
Now, find the minimum $(s,t)$-cut in this graph, using any network flow algorithm.  The $s$ side of this cut will contain all of the nodes that become blue, and the edges that cross the cut will indicate where to place blocks (for blue-to-white edges that cross the cut) and which white nodes become blue (for white-to-$t$ edges that cross the cut).

Why does this work?  We're going to treat the final colors as defining a cut $(B,W)$: $B$ contains all nodes that are ultimately blue (and $s$), and $W$ contains all that remain white (and $t$).  This means that any edge between an ultimately-blue node and an ultimately-white node crosses the cut, which matches the problem requirement that such an edge must have a block on it.  Also, if $b \in B$ is any node that was originally white but becomes blue, then the edge $b \to t$ crosses the cut (since $t \in W$), so we think of it as having a block between it and $t$.  Finally, we want to know the cheapest way to choose a set of blocks.  The total cost of a set of blocks is the sum of the capacities of the edges that were blocked, so this total cost matches the total capacity of the edges that cross the cut $(B,W)$, i.e., the capacity of the cut.  So, finding a min-capacity cut will find you the cheapest way to place a set of blocks that match the problem requirement.


If DFA has two states, which of the conditions hold? Let $L$ be a regular language ,and $M = (Q, Σ, δ, q_0, A)$ is a DFA such that $L(M) = L$.
 Prove that if $|Q| = 2$ then one of the following holds :
a) $L=∅$ b) $ε∈L$ c) $∃a∈Σ$ and $a∈L$

The problem is, I think all of these are FALSE. If there is 2 states, none of them are accepting states, then L will have no elements. This disproves b) and c). However if one of the states is accepting, then a) is false !
I dont see how one of these statements is always true.

You seem to be misunderstanding the statement of the exercise. It wants you to show that if $L$ is a language accepted by a DFA containing two states, then either $L$ is empty, or $L$ contains the empty word, or $L$ contains a word of length 1. Which of the cases holds depends on $L$. More explicitly:

If no state of the DFA is accepting, then $L = \emptyset$.
If the initial state of the DFA is accepting, then $\epsilon \in L$.
If the other state of the DFA is accepting, then either the state is reachable, in which case $\sigma \in L$ for some $\sigma \in \Sigma$, or else it is unreachable, in which case $L = \emptyset$.

More generally, the proof of the pumping lemma shows that if $L$ is accepted by a DFA containing $n$ states, then either $L = \emptyset$ or $L$ contains some word whose length is less than $n$. This is sharp, in the following sense: for each $n \geq 1$ and $m \in \{0,\ldots,n-1\}$, there is a language accepted by a DFA of length $n$ whose shortest word has length exactly $m$ (exercise).


What is the meaning of a prefix-free language? Tried a bunch of resources to read about it, still don't really get it.

This is what Wikipedia says

  A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system.

This is my understanding so far:
I have a language L that has all these words L = {"a", "b"}. From my understanding, right now my language L is prefix free, but if I add a new word to it like "ac", so that my language becomes L = {"a", "b", "ac"}, its not prefix-free anymore?

Is my thinking correct? or am I missing anything?

You are correct: {a, b} is prefix-free, but {a, b, ac} is not.

The idea of a prefix-free code is that once you recognize a word you know for sure it's a word.  So for instance a code that includes both CONNECT and CONNECTICUT is not prefix-free, because if you start parsing a phrase like

ACONNECTICUTYANKEEINKINGARTHURSCOURT

taking every word as soon as you see it you're going to read this as

A, CONNECT, I, CUT, YANK, (error)

since you can't do anything with the string EEINKINGARTHURSCOURT.  (That's assuming you don't also consider CON a word also; if so, things would be even worse.)

Note that adding spaces between words is basically a way of making a code prefix-free: if "connect" by itself isn't considered a word, but "connect " is, then you'll have no trouble parsing

A CONNECTICUT YANKEE IN KING ARTHURS COURT


How many times an empty 4-cycle can be counted in an undirected graph? I have an undirected graph where each node is labelled with an integer key and I'm asked to detect every simple 4-cycle, which can be seen as an empty square (i.e. the two opposite nodes of the cycle have not to be connected).

I know the labels of a generic square in the graph can be permuted in $4! = 24$ ways, but on his paper (pages 33-36) Cohen states that the symmetric group $S_4$ has $S_4 = 8$ elements, and this should allow me to focus only on $24/8 = 3$ distinct cases.

I don't understand this last point. Well, I know he probably means that the suqare has $8$ isometries (four reflections and four rotations), but I don't understand why this leads to the three cases in Figure 7 of the paper.

Thank you.

For each set $\{a,b,c,d\}$ of four vertices, there are three possible squares: $a-b-c-d$, $a-b-d-c$ and $a-c-b-d$. This is $|S_4|/|D_4|$, where $S_4$ is the symmetric group on four points, and $D_4$ is the dihedral group, the group of symmetries of a square.

Hear a square is a set of edges forming a square. So the squares are really $\{\{a,b\},\{b,c\},\{c,d\},\{a,d\}\}$, $\{\{a,b\},\{b,d\},\{c,d\},\{a,c\}\}$ and $\{\{a,c\},\{b,c\},\{b,d\},\{a,d\}\}$. You can check that all are distinct. Every square on $a,b,c,d$ is one of these — try finding any other one. We know that this list is exhaustive because of the computation $|S_4|/|D_4| = 3$.


Bellman-Ford algorithm intuition We recently learned Bellman-Ford algorithm for shortest path in class, but I didn't understand it.
Can you give me intuition for why the algorithm works? And can you please explain why it is correct? Why are we sure to find negative circles?
Also, we learned the following two lemmas:

Lemma (upper bound property): At all times we have that for all $v$, $v.d \ge \delta(s,v)$.

Lemma (Path-relaxation property): Let $p = \langle s=v_1, v_2, \ldots, v_n \rangle$. Following any sequence of relaxations in which the edges $(v_1,v_2),(v_2,v_3),\ldots,(v_{k-1},v_k)$ are relaxed in order, we have that $v_k.d \le w(p)$.

Here:

$v.d$ is the distance of $v$ from the initial vertex $s$. (We constantly update this value using the relax function in the Bellman–Ford algorithm.)

$\delta(s,v)$ is the minimum weight path between $s$ and $v$.

$w(p)$ is the total weight of path $p$.

Can you give me an intuition for the lemmas and what they mean?

I can give you the intuition behind Bellman-Ford.  It is beautiful!  I'm going to do it in an indirect way.  I want to share a warm-up puzzle that might seem unrelated, but stay with me.

Suppose we have a digital door lock with a four-digit code (each digit is 0..9), with a funny property: you can enter in extra stuff between the digits of the code and the lock will still open up.  For instance, if the code was 2749, then you  could enter in 32675049, and the lock would open up, because 32675049 contains 2749 as a subsequence.
Challenge: what is the shortest sequence you can come up with, that will guarantee to open the lock?  You could of course enter in each of the $10^4$ possible codes one by one, but that would require you to enter 40,000 digits; can you find a faster way?

Go ahead, see if you can solve it on your own.
Hint:

 Whatever the secret code is, we need it to appear as a subsequence of your chosen sequence.   If we start with 0123456789, we are guaranteed to get at last one digit into the code.  Can you take it from there?

Hint:

 You should be able to find a sequence of length 40 that suffices.

Really, I want you to solve it yourself!  It'll be rewarding and help you understand Bellman-Ford.

Now back to Bellman-Ford.  Let's consider a graph with no negative cycles, but where edge distances can be positive or negative.  The relax operation has an interesting property:

Suppose the shortest path from $s=v_1$ to
$v_n$ is via the path  $v_1 \to v_2 \to \cdots \to v_{n-1} \to v_n$.  If we do some sequence of relax operations, that includes Relax($v_1,v_2$), Relax($v_2,v_3$), ..., Relax($v_{n-1},v_n$) as a subsequence, then $d[v_n]$ will hold the correct distance from $s$ to $v_n$.

In other words, this refers to a sequence of relax operations where we do some relaxes, then Relax($v_1,v_2$), then relax on some other edges, then Relax($v_2,v_3$), then relax on some more edges, and so on.  The property holds no matter what other relax operations you do in the middle -- you can add as many extra relax operations  in the middle anywhere you want and they won't do any harm.
Moreover, once $d[v_n]$ gets set to the correct value, it stays correct forever.
So if our goal is to come up with the correct distance in $d[v_n]$, we can think of that as a digital door lock   like the one above: there is some secret code (the code is a sequence of edges, namely, $(v_1,v_2),\dots,(v_{n-1},v_n)$) that is not known to us, but if we do a sequence of relax operations on some sequence of edges, and if the secret code appears as a subsequence in there, then the lock will open  (i.e.,, $d[v_n]$ will get set to the correct distance), and will stay open forever after (i.e., $d[v_n]$ will hold the correct value from there on).
So this is just like the digital door lock puzzle above!  The challenge is to construct a sequence of edges, so that if we relax edges in that sequence, it'll surely include the code (the shortest path) as a subsequence.  Now you can verify that the sequence of edge relaxations done by Bellman-Ford exactly matches the solution to the digital door lock puzzle above.
I'll let you prove the property I mentioned above.  It follows from the two lemmas you quoted.


Best problems that are prone to parallelization? What are some problems that are prone to parallelization? When I think about this, the first thing that comes to my mind is matrix multiplication, which yields to faster calculations, meaning you can get speed ups easily. Any other examples like this?

Tasks that are easily parallelizable are sometimes called embarassingly parallel. Straightforward examples are computing fractals like Julia or Mandelbrot sets (since all points are independent of each other) or brute-force searches.

You can find many other examples on the wikipedia page.


Complexity of ANOTHER HAMILTONIAN CIRCUIT problem All references I find about the ANOTHER HAMILTONIAN CIRCUIT problem:

  Given a graph and a hamiltonian circuit on it, is there another
  hamiltonian circuit on it?

I was trying to reduce it to the hamiltonian circuit problem but I always need to add too many or too few circuits to the original one.

Am I going through the good direction? It seems to be very simple...

Edit

Papadimitriou's complexity book refers to its theorem 17.5 for the inspiration for this problem.

I think that a good way for the solution is to consider the graph proposed in Papadimitrious'

One can for each node of the original graph, transform to the graph shown at the left image. Then, one can connect all these new graphs using the poles N and S and thus obtains a hamiltonian circuit. Then, one uses W and E to connect vertex that were connected in the original graph. In principle, one could connect W with W and E with E.

I only have one more doubt, what happens if the original graph is just a segment, that is, two vertex with a edge between them. My construction would give an extra hamiltonian circuit going from W1->E1->E2->W2->W1 even if the original one didn't have one!

Can you find any other counterexample? This was the solution given in my course and it seems to be partly wrong...

This result is proved in the senior thesis The complexities of puzzles, cross sum and their another solution problems (ASP) by Takahiro Seta.

The systematic study of ASPs was initiated by Ueda and Nagao in their paper NP-completeness Results for NONOGRAM via
Parsimonious Reductions. See also Takayuki Yato's master thesis, Complexity and completeness of finding another solution and its application to puzzles.


A Question relating to a Turing Machine with a useless state OK, so here is a question from a past test in my Theory of Computation class:

  A useless state in a TM is one that is never entered on any input string.  Let $$\mathrm{USELESS}_{\mathrm{TM}} = \{\langle M, q \rangle \mid  q \text{ is a useless state in }M\}.$$
  Prove that $\mathrm{USELESS}_{\mathrm{TM}}$ is undecidable.

I think I have an answer, but I'm not sure if it is correct.   Will include it in the answer section.

This is clearly reducible from the Halting Problem. If a machine $M$ does not stop on input $x$ then any final state is "useless". Given an input $M,x$ for the Halting problem, it is easy to construct $M_x$ that halts on every input (thus its final state is not useless) if and only if $M$ halts on $x$. That way you can decide Halting Problem if you can decide $\mathrm{USELESS}_{\mathrm{TM}}$, which yields a contradiction.


Can software itself be encrypted? Imagine that I need to install my server in a remote location, so my algorithm can do something fancy (collocation of server at a financial exchange is how I thought of this question, but it applies more generally).

Imagine also I don't trust the people I am working with. They will have access to my server and I cannot be there to stop them from opening up the box and copying the disks.

Is there any way for me to hide the business logic of my algorithm from them, while maintaining that algorithm's functionality? In other words, can I encrypt my software and yet have it operate at the same time?

My feeling is no, since the software needs to speak in machine language, using the instruction set architecture, which is pretty standard. But CS is full of surprises so I thought I'd ask.

If the answer is yes, how do I do it? If the answer is no, are there any safeguards I can implement?

If you want a practical answer: with Intel SGX, the answer seems to be a qualified yes, but software development is likely to be more painful.  (Similar with a TPM, though that will be even more annoying.)  See, e.g., https://security.stackexchange.com/q/2459/971.

If you want a theoretical answer: in theory, you could use various cryptographic schemes for outsourcing computation (e.g., fully homomorphic cryptography, secure multiparty computation, SNARKs, outsourcing computation, and so on).  As a general theorem, any computation you can do in polynomial time, could also be done on the remote server in polynomial time, with ability to verify that the result it gives you back is correct in polynomial time.  However, in practice right now these schemes include an enormous performance overhead (a factor of a million slowdown or more), except for certain special tasks, so they're not at a stage where you could actually use them in practice today.


Do problems in P only reduce to NP and coNP problems? Consider the languages $B,C,D$, such that $B\le_p C$ and $B\le_p D$.
Statement: $B\in P, D\in NP, C\in coNP$.

  Is the statement true for every $B,C,D$?

I know that the answer is no and I have tried to come up with a conunter-example.
I thought about taking $D\in NPC$ or $C \in coNPC$ but that didn't yield anything good.

One short answer, take $B$ be to be any problem in $\mathsf{P}$. The reduction is then powerful enough to simply solve the problem as part of the reduction, and consequently produce a trivial yes or no instance at the other end as appropriate. Then we can take $C$ and $D$ to be anything, they don't even have to be computable.

A more interesting, but conditional answer, is to take $B$, $C$ and $D$ to be any three $\mathsf{NP}$-complete problems (they don't even need to be different ones). Every $\mathsf{NP}$-complete problem is polynomial-time many-one reducible to every other $\mathsf{NP}$-complete problem, so the two reducibility conditions hold trivially. If $\mathsf{P} \neq \mathsf{NP}$, then $B$ can't be in $\mathsf{P}$, and if $\mathsf{NP} \neq co\mathsf{NP}$, then $C$ can't be in $co\mathsf{NP}$. You can do essentially the same thing by taking them all to be $co\mathsf{NP}$-complete. Taking it further, you can do this for any class in the polynomial hierarchy, and the statement being true would imply a collapse to whatever level you chose, another thing that is viewed as unlikely to happen. You could also choose a selection of $\mathsf{PSPACE}$-complete problems, and the statement would imply $\mathsf{P} = \mathsf{PSPACE}$, which also seems unlikely to be true.


Checking disjointness between subsets of a poset If there is a poset $(P, \le)$ and two sets $X \subseteq P$ and $Y \subseteq P$, and we have a way $f : P^2 \to 2$ to efficiently compute for any $(x, y) \in P^2$ whether there exists a $z \in P$ such that $(x \le z) \wedge (y \le z)$, we want to return $\mathbf{T}$ if there exists a pair $(x, y) \in X \times Y$ such that $f(x, y) = 1$ and $\mathbf{F}$ otherwise, using the fewest possible number of calls to $f$ and $\le$.

Without further information, you can't do any better than $O(n^2)$ queries to $f$, where $n=|X|+|Y|$.  There is a simple adversary argument.

Imagine you have an algorithm that uses $o(n^2)$ queries.  Consider running it on a set $X,Y$ chosen so that $f(x,y)=0$ for all $x \in X, y \in Y$.  If the algorithm is correct, the algorithm must return F on this input.  Since the algorithm runs in $o(n^2)$ time, there must exist some pair of elements $x_0,y_0$ that was never queried.  Now run the algorithm on a pair of sets $X,Y$ chosen so that $f(x_0,y_0)=1$ but $f(x,y)=0$ for all other pairs $x,y$.  We see that $f$ always returns 0 during this execution, too, so this execution must follow exactly the same path as the first execution, and thus must also return F on this input.  However, returning F on this input is incorrect.  Therefore, there is no algorithm that takes $o(n^2)$ time and is always correct.