A Google search for "edges not in MST" leads me to this question. The answer included in the question has already been found wrong, as OP said in the last comment. For future references, here is my solution to the question.
Let $G$ be a weighted undirected (finite) graph. An edge $e$ is called superheavy if it is the unique heaviest edge in some cycle. Here is a characterization of the edges that are not in any MST.
An edge is not in any MST if and only if it is a superheavy edge
The well-known "if" part, a superheavy edge is not in any MST, is proved in the cycle property of MST.
The "only if" part, any edge $e$ that is not superheavy is in some MST, is harder to prove. Let me introduce an algorithm and a lemma first.
The delete-heaviest-edge algorithm (DHE) on $G$ removes a heaviest edge in any cycle until no cycle remains. Just to be extra clear, there might be multiple heaviest edges in one cycle. The edge removed can be chosen to be any one of them.
Lemma: DHE is an MST algorithm. That is, the final graph at the end of DHE is an MST of the original $G$.
One proof of the lemma can be developed by adapting the proof at reverse-delete algorithm.
For another proof of the lemma, reader can check my post at the delete-heaviest-edge algorithm on graphs with edges of distinct weights, where I proved the special case where all weights are distinct. For the general case of a given run of DHE where all weights of $G$ are not necessarily distinct, we can perturb the weights of all edges of $G$ so that all weights are distinct and that each edge removed is the unique heaviest edge in the corresponding cycle. We can then repeat the given run of DHE on the perturbed $G$, resulting in the same spanning tree, which is also the MST of the perturbed $G$, since this is the proven special case of distinct weights. By making the perturbation arbitrarily small, we can see the total weight of the resulting MST can be arbitrarily near to the weight of a (or any) MST of the original $G$. Once we take the limit of perturbation going to $0$, we can see that original given run of the DHE must produce a spanning tree with the minimal weight. The lemma is proved.
Now let us prove the "only if" part. Suppose edge $e$ is not a superheavy edge. Let us start a particular run of DHE. We will adjust that run whenever necessary to avoid deleting $e$. Suppose $e$, as a heaviest edge in some cycle is removed in some step. Because $e$ is not superheavy, there is another heaviest edge, say $f$, in that cycle. Let us modify that step so that it removes $f$ instead of $e$. Continue to run the algorithm, alway avoiding removing $e$ as we just did. At the end of the algorithm, we must arrive at an MST thanks to the lemma, which contains $e$. Proof of the "only if" part is done.
Since an edge not in any MST means it is superheavy, any algorithm that finds all the superheavy edges will also finds all edges that are not in any MST.
Algorithms to find all superheavy edges
Here is a naive algorithm. Iterate over all edges. For each edge $e$, pick arbitrarily one of its two vertices. Starting from this chosen vertex, make a DFS or BFS along edges with weight lower than that of $e$, checking whether we have reached the other vertex of $e$ all along. Once we have, $e$ is superheavy. Otherwise we cannot at the end of the search, implying $e$ is not superheavy.

It often happens that there is a unique MST, for example when all edge-weights are distinct. We can use various algorithms such as Kruskal's algorithm or Prim's algorithm to compute that unique MST. The superheavy edges are the edges that are not in that unique MST.

Here is the efficient algorithm to find all superheavy edges in general cases. Its time-complexity is about the time-complexity to sort the edges by weights, or $O(m\log m + n)$, where $n$ is the number of vertices and $m$ is the number of edges. Its space-complexity is about $O(m+n)$.

Sort all edges in groups of increasing weights so that we have $$E=E_1\cup E_2\cup \cdots \cup E_r$$ and $$w_1<w_2<\cdots<w_r,$$ where $E$ is the edge set of $G$ and every edge in $E_i$ has weight $w_i$.
Let $H$ be a graph that has the same vertices as $G$ but without any edges. Track the connected components of $H$ by a disjoint-set data structure.
For $i$ from 2 to $r$ do the following.

Add all edges in $E_{i-1}$ to $H$.
For each edge in $E_i$, check whether its endpoints are in the same connected component of $H$. If yes, it is a superheavy edge.


For a fixed alphabet, you can describe an NFA with $n$ states using $O(n^2)$ bits. Now, given a DFA $M$ and an integer $n$ (encoded in binary), we consider two cases:

$M$ has at most $n$ states. In this case, there exists an NFA for $L(M)$ having at most $n$ states.
$M$ has more than $n$ states. In this case, the input length is $\Omega(n)$ bits, and so we can guess an NFA with $n$ states in polynomial space.


The while loop with true condition is just to ensure this process can enter and exit its critical section repeatedly. This usage is quite common when we are discussing concurrency programming.

Take a moment to reflect. How can you create an environment to demonstrate easily the effect of two or more different concurrent processes are, for example, contending for one shared resources? If you let each process just try to enter the critical section once, it might be hard to produce the various particular situations that could happen only to concurrent running processes. It may just happen all processes enter the critical section in order once and then exit.  However, if we use a while(true) loop to run the processes long enough, it will be much more probable to observe all sorts of phenomenons.


The answer is very simple: try to construct an algorithm which doesn't sort both arrival and departure times, and see if that's possible. If so, then there is an alternative algorithm which indeed doesn't requiring both times. Otherwise, you will understand why this is necessary.

The intuitive explanation of why we sort both arrival and departure times is that we are actually sorting all events. There are two types of events, arrival and departure, and we want to process them as they happen. We don't care about matching departure times with arrival times – that is, for our algorithm to work, we don't need to know which train is involved, only that a train has arrived or has left the station.

This actually suggests a way to restate the algorithm you describe. Sort all events according to time. Now go over them in order of increasing time (we assume for simplicity that all times are distinct). Keep a counter of the number of trains in station. When processing an arrival event, increase the counter; when processing a departure event, decrease the counter. Keep track of the maximal value of the counter.

The algorithm you describe instead sorts the arrival and departure times separately, and then performs an online merge (same algorithm as in merge sort for merging two sorted lists). I don't know why they described the algorithm this way rather than the way I described it.


Why does garbage collection extend only to memory and not other resource types?

GC deals with a predictable and reserved resource. The VM has total control over it and has total control over what instances are created and when. The keywords here are "reserved" and "total control". Handles are allocated by the OS, and pointers are... well pointers to resources allocated outside the managed space. Because of that, handles and pointers are not restricted to be used inside managed code. They can be used - and often are - by managed and unmanaged code running on the same process.

A "Resource Collector" would be able to verify if a handle/pointer is being used within a managed space or not, but it by definition is unaware of what's happening outside it's memory space (and, to make things worse some handles can be used across process boundaries).

A practical example is the .NET CLR. One can use flavored C++ to write code which works with both managed and unmanaged memory spaces; handles, pointers and references can be passed around between managed and unmanaged code. The unmanaged code must use special constructs/types to allow the CLR to keep tracking of references being made to it's managed resources. But that's the best it can do. It cannot do the same with handles and pointers, and because of that said Resource Collector would not know if it's ok to release a particular handle or pointer.

edit: Regarding the .NET CLR, I'm not experienced with C++ development with the .NET platform. Maybe there are special mechanisms in place that allows the CLR to keep tracking of references to handles/pointers between managed and unmanaged code. If that's the case then the CLR could take care of the lifetime of those resources and release them when there all references to them are cleared (well, at least in some scenarios it could). Either way, best practices dictate that handles (especially those pointing to files) and pointers should be released as soon as they are not needed. A Resource Collector would be not-complying with that, that's another reason to not have one.

edit 2: It's relatively trivial on the CLR/JVM/VMs-in-general to write some code to free up a particular handle if it's used only inside the managed space. In .NET would be something like:

// This class offends many best practices, but it would do the job.
public class AutoReleaseFileHandle {
    // keeps track of how many instances of this class is in memory
    private static int _toBeReleased = 0;

    // the threshold when a garbage collection should be forced
    private const int MAX_FILES = 100;

    public AutoReleaseFileHandle(FileStream fileStream) {
       // Force garbage collection if max files are reached.
       if (_toBeReleased >= MAX_FILES) {
          GC.Collect();
       }
       // increment counter
       Interlocked.Increment(ref _toBeReleased);
       FileStream = fileStream;
    }

    public FileStream { get; private set; }

    private void ReleaseFileStream(FileStream fs) {
       // decrement counter
       Interlocked.Decrement(ref _toBeReleased);
       FileStream.Close();
       FileStream.Dispose();
       FileStream = null;
    }

    // Close and Dispose the Stream when this class is collected by the GC.
    ~AutoReleaseFileHandle() {
       ReleaseFileStream(FileStream);
    }

    // because it's .NET this class should also implement IDisposable
    // to allow the user to dispose the resources imperatively if s/he wants
    // to.
    private bool _disposed = false;
    public void Dispose() {
      if (_disposed) {
        return;
      }
      _disposed = true;
      // tells GC to not call the finalizer for this instance.
      GC.SupressFinalizer(this);

      ReleaseFileStream(FileStream);
    }
}

// use it
// for it to work, fs.Dispose() should not be called directly,
var fs = File.Open("path/to/file");
var autoRelease = new AutoReleaseFileHandle(fs);


Some things I learnt while learning to answer this type of question:

Negation isn't easy to express. There are no shortcuts. The resulting expressions may be far more complex than the expression you would get if negation was a basic operator in the expression language - in which case you could write $\neg(.^*bbc.^*)$, where $.$ is a shortcut for $(a\cup\neg a)$
Lacking $\neg$, the only way to say $\neg a$ for some symbol $a$ is to enumerate all other symbols: $\neg a = (b\cup c \cup d \cup \ldots)$. In Unix-like regular expressions, you can of course use [^a].
In compound expressions, you can use left factorization.
E.g. $\neg(bbc) = \epsilon \cup \neg b\neg(bc) = \epsilon \cup \neg b(\epsilon \cup \neg c) = \ldots$.
The key insight is that this can be made to work with Kleene star expressions, too; I suggest you invent or look up the details yourself.


What is the relation between Computer Graphics, Discrete Geometry, and Complexity Theory?

Have a look at this slide of David Eppstein in which he tries to draw connections between these subfields. In my opinion, a computational-geometric complexity result is likely to be confined to computational geometry itself without broadly affecting complexity theory in general.

Excerpt from the above slide: Some computational geometry problems have practical applications. Their theoretical hardness are all conjectured to be $NP$-hard but still have not been proven. Some have approximation schemes.


Difference between Recursion Tree & Binary Tree

A binary tree is a rooted tree where every internal node has at most two children.
A recursion tree is a rooted tree which traces the execution of a recursive procedure. It need not be binary.


Can Tug of war problem be solved by DP or greedy approach?

There is a pseudo-polynomial solution with dynamic programming which runs in $O(S n^2)$ with $S = \sum_{i=1}^n |a_i|$.

Namely for each possible sum $s$ (between $\sum_{a_i < 0} a_i$ and $\sum_{a_i > 0} a_i$) compute, if you can choose a subset of size $\lfloor n/2 \rfloor$ with sum $s$. Using this information you can directly find the optimal solution.

You can compute this information it in a similar way as you would for a 0/1 knapsack problem, just with one dimension more:

$$f(s, m, i) = f(s-a_i, m-1, i-1) ~\vee~ f(s, m, i-1)$$ if $i > 0$ and $m > 0$,
where $f(s, m, i)$ means "is it possible to choose a subset of size $m$ with sum $s$ using the first $i$ elements of the original array?".


Both - attempt 1 and 2 - are incorrect executions of the Horspool's algorithm. After the first round of trying to match the pattern in the text:

001001001001
111

There are two comparisons made of which the second one 0 == 1 fails. Now, the shift is determined by the last character in the section of the text being matched i.e. shift value of 1 which is 1. The next search round looks like:

001001001001
-111

This has only one comparison 0 == 1 which fails. The shift is now decided by the value of shift value of 0 which is 3, thus making the next round as follows:

001001001001
----111

This also has only one comparison, just like the previous one resulting in another shift of 3. The next round is also the same, with one comparison.

The total now, correctly, stands at 5.


There is no list out on the web, nor even a partial list. I spent a few days looking and found nothing. The best you can do is piece together a list on your own (and post it here! :D).


Is this time complexity quasi-polynomial?

Quasi-polynomial means different things to different people, but in many contexts it means a running time of the form $O(2^{O(\log^{O(1)} N)})$, to which your example conforms.


About the properties of the coresets in k-median clustering

The k-medians clustering objective is defined here as
sum_{p in points} weight(p) distance(p, centers)

where centers is the set of k centers and distance(p, centers) is the distance to the closest center.
The first observation amounts to observing that the objective function is additive. Letting (C1, w1) and (C2, w2) be the core-sets, we consider the core-set (C1 union C2, w1 union w2), which satisfies
sum_{p in C1 union C2} (w1 union w2)(p) distance(p, centers)
= sum_{p in C1} w1(p) distance(p, centers) + sum_{p in C2} w2(p) distance(p, centers)
<= exp(eps) sum_{p in P1} weight(p) distance(p, centers) + exp(eps) sum_{p in P2} weight(p) distance(p, centers)
= exp(eps) (sum_{p in P1 union P2} weight(p) distance(p, centers))

and similarly for the lower bound.
As for the second observation,
sum_{p in C1} w1(p) distance(p, centers)
<= exp(eps) sum_{p in C2} w2(p) distance(p, centers)
<= exp(eps) exp(delta) sum_{p in C3} w3(p) distance(p, centers)
= exp(eps + delta) sum_{p in C3} w3(p) distance(p, centers),

and similarly for the lower bound.


Algorithm for solving binary quadratic Diophantine equations (BQDE) and its CTC

Yes, such algorithms exist, i.e., if only BDQE has integer solutions, then those solutions can be found computationally, however - in exponential time. There is no polynomial time algorithm to tackle it in the general form (at least on a classical, non-quantum computer).

There's more information in Jeff Lagarias's slides for his talk Complexity of Diophantine Equations.


One good way is to use Flickr. For your project you could use available API for downloading photos with related information.

If you are using Java you could use the classes on Google Codes.


Time complexity of removing a vertex from a graph represented as collection of adjacency lists

In step 2, vertices with no neighbours have an empty adjacency list, but it still takes one time step to realise that the list is empty. So the runtime is $\sum_{i\in[n]\smallsetminus \{d\}} \max(1,e_i)=O(n+e)$.


Sorry for the late reply (4 years!)

NegaScout is a very simple algorithm. To understand we should revise iterative deepening.

Iterative deepening is a technique for a chess engine to search for depth i, then i+1, then i+2 etc. This is an example of dynamic programming. During each iteration we have our best guess of what the best move would be. Most chess engines would keep this move in a hashing table.

Imagine we are now at iteration i+1, and we have the best move from the last iteration i. Now we have 5 nodes to search, we should we do?

If we assume we have done reasonably good job during our last iteration, the best move from the last iteration (which we get from the hash table) should also be the best move for the current iteration.

If our assumption is correct, we should be able to save time by searching every move other than the best move (the four moves not in the hash table) with a null window. A null window is something like:

score := -pvs(child, depth-1, -α-1, -α, -color)

Note -α-1 and -α. They are the alpha and beta values we will give to the next recursion. Since the width of the window is only 1, the search will always fail:

If it fails below α, the move is worse than we already have, so we can ignore it
If it fails above β, the move is too good to play, so we can ignore it
Otherwise, we need to do a new search properly

Of course, we will still search the best move (the one we get from the hash table) with a proper alpha and beta window. We need to do this because we need to know exactly the value of the node, we can't just ignore it.

Everything I've said is implemented in the following pseudocode. The pseudocode specifies child is not first child but this is a way to check whether the move is also the best move int the previous iteration. Hash table is the most common implementation.

# Negasort is also termed Principal Variation Search - hence - pvs

function pvs(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color x the heuristic value of node

    for each child of node
        if child is not the first child
            # search with a null window
            score := -pvs(child, depth - 1, -α - 1, -α, -color)

            # if it failed high, do a full re-search
            if α < score < β
                score := -pvs(child, depth - 1, -β, -score, -color)
        else
            score := -pvs(child, depth - 1, -β, -α, -color)

        α := max(α, score)

        # beta cut-off
        if α >= β
            break

    return α


Nice question!

  Given a range of integers $\{a,a+1,...,b−1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.

Well, this problem can be solved in $O(n)$ time, where $n$ is the number of given integers.

(Continuity of $k$-sums). Given integers $\{a,a+1,...,a+n-1\}$, an integer $k$, $1\le k\le n$ and an integer $s$, there are $k$ integers whose sum is $s$ if and only if $ka+\dfrac{(k-1)k}2\le s\le k(a+n-1)-\dfrac{(k-1)k}2$

Here is the algorithm.

Check if $ka+\dfrac{(k-1)k}2\le s\le k(a+n-1)-\dfrac{(k-1)k}2$. If not, return none.

Let $sum = s$. Let $S$ be an empty set.
For $i$ from 0 to $n-1$ do the following.

Let $temp = sum -(b - i)$.
If  $temp\le (k-i-1)(a+n-1)-\dfrac{(k-i-2)(k-i-1)}2$,
let $sum = temp$ and insert $b-i$ into $S$. Otherwise, do nothing.
If $sum = 0$, break the loop.

Return S.

Here are a few related exercises.

Exercise 1. Prove the proposition of continuity of $k$-sums.

Exercise 2. Show the algorithm is correct.

Exercise 3. Modify the algorithm so that it will try adding the smallest number first.

Exercise 3. Modify the algorithm so that it will run in $O(k)$ time.


I think there are really three issues buried in your question.

What's Simon's Problem?
What's a plain english description of the function involved in Simon's Problem?
Why isn't this problem a cryptographic primitive?

I can't really speak to 3 as cryptography is not my area.  I can take a crack at 1 and 2 for you though.  The distinction between 1 and 2 is, I think, important.

Simon's problem is one of discovering the parameter to a function given a black-box to that function and some basic information about the function. So, an algorithm to solve this problem takes as its input a black-box to a function and gives a output a binary string.   Our goal is to reduce the number of queries to that black box.  I think people tend to miss this point and focus on the internals of the function itself.

All we know about the function $f$ is that our black-box can compute it for us in constant, $O(1)$, time, and that if $f(x) = f(y)$, then either $x=y$ or $x \oplus y = s$.  We want to know the value of $s$.   A brute force, classical computing solution might give you a better feel for the problem.  Here it is:

Feed all $n$ bit binary strings to the black-box and save each input-output pair to a table.
If no two inputs produce the same output then it must be the case that the parameter $s$ is $n$ bit $0$.  Otherwise, two inputs will produce the same output and $s$ is the result of XOR'ing those inputs together.

In the worst case, we have to query all $2^n$ inputs leading to $O(2^n)$ query complexity.

Querying the black-box is at the heart of Simon's problem.  We need not concern ourselves with how to construct the black-box, i.e. how to compute $f$, as that is not what the problem is about.  I don't believe that Simon's problem is practically useful beyond the fact that it helps establish some complexity results about Quantum Computers.  It's main significance is that it was an inspiration for Peter Shor's factoring algorithm.


Difference between Turing machine end state and halt

"End(ing) state" and "halt(ing) state" are just two (four) different ways of saying the same thing.


Brute force algorithm for "Binary Puzzle"

For $k$ fixed cells, you try all $2^{n^2-k}$ possibilities of filling the remaining $n^2-k$ cells and check for each fully filled board whether it fulfills all stated constraints.


Does the aliasing problem show up in a virtually indexed physically tagged cache?

The Aliasing problem can be solved if we select the cache size small enough. If cache size is such that the bits for indexing the cache all come from the page offset bits , multiple virtual address will point to the same index position in  the cache and aliasing will be solved.

For example consider 32-bit virtual address 0xFFFF FFFF  , this system uses a page size of 64kB suppose which make the page offset bits 16 bits. Now if we select The index bits to be 10 (number of sets 1024) and block size as 64 Bytes. Then the index bits and the block offset bits both are accommodated in the page offset bits of the virtual address. Consider another address  0xEEEE FFFF  this address looks like it will cause aliasing but despite of having different virtual address the lower order bits force it to map to the same location in the cache  and there is no aliasing. Only drawback of this approach is cache size is limited by the page size.


Given a connected graph with edges >= vertices, find an algorithm in O(n + m) that orients the edges such that every vertex has indegree of at least 1

Start with any vertex $v_s$, and do a BFS from that $v_s$ to discover the entire graph.  When you traverse an edge, you orient it away from the start node.

Now every vertex $v \in V \setminus \{v_s\}$ has $\deg_{\text{in}}(v) > 0$.

Find a path from $v_s$ to any vertex $v_t$ such that $\deg_{\text{in}}(v_t) \geq 2$.  Since the input graph is not a tree, such a vertex must exist.

Flip all edges in the path.

This graph satisfies your requirement since

every internal vertex $v_i$ in the path still has $\deg_{\text{in}}(v_i) > 0$,
$v_t$ now has $\deg_{\text{in}}(v_t) \geq 1$ (it decreased by one), and
$v_s$ has $\deg_{\text{in}}(v_s) > 0$.

Running time: $O(n + m)$.


Unfortunately there aren't many textbooks on the topic. I think the best way to learn program analysis today is to survey different courses that are available, play with a few implementations and then look at a few research papers for your specific needs. What follows is a very small sampling of what's out there. Since you specifically mentioned compiler-oriented analyses were easy to find, I will not cover such material below.

Web-based resources
These are articles that emphasise the use of static analysis outside a compilation context.

A Reverse Engineering Reddit discussion on program analysis has many useful links.
Mozilla Wiki on abstract interpretation.
Deploying Static Analysis, a Dr. Dobbs article by Flash Sheridan
A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World, Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, Dawson Engler  in Communications of the ACM.

University courses on program analysis

Anders Møller at Arhus University teaches a course that covers object-oriented and web technology.
Bor-Yuh Evan Chang at University of Colorado Boulder has a foundational course that involves an OCaml implementation and a graduate course.
Ben Hardekopf at the University of California Santa Barbara used to have a great set of assignments, but they are no longer available online. Some students who took his course seem to have made a Python implementation available.
Markus Müller-Olm has a graduate course on analysis of Android.
Reinhard Wilhelm at the University of Sarbruecken teaches a graduate course that covers static analysis applications such as timing analysis, cache behaviour prediction, and some shape analysis.
Sumit Gulwani from MSR taught a nice course on statically estimating resource consumption of programs (time/memory) at the Oregon Summer School on Programming Languages.
Koushik Sen at the University of California at Berkeley teaches a course that focuses on bug finding and whose topics cover concolic execution and software model checking.
Jeffrey Foster at the University of Maryland teaches a course that covers type systems, model checking, alias analysis and a lot of the other usual material.
Patrick Cousot spent a year at MIT and taught a comprehensive, foundational course on abstract interpretation. The assignments include an OCaml implementation which go from concrete collecting semantics to some algorithmically non-trivial ideas.
A graduate course on abstract interpretation taught by some leaders in the field is a good place to catch up on even more theory.
Patrick Cousot taught a short course on abstract interpretation at the Oregon Summer School on Programming Languages in 2009.

Tools to play with

I am not listing a lot of research tools here. There are many of those but I have tried to list a few that you can download and play with to understand the area better.

Interproc is a very educational tool to play with to learn about numerical static analysis.
The Apron Numeric Abstraction library if you are really into numeric analysis.
Slayer is a shape analysis tool from Microsoft Research.
jStar is an analyzer for Java that is based on separation logic.
Microsoft Research has numerous groups developing numerous tools, many of which are available for download or have web-demos. I cannot list everything here and suggest you play with them.

There is a lot more, but that's probably enough to keep you busy for a while.


Algorithm to recognize Strongly Regular Graph (SRG)

There is a trivial $O(kn^2)$ algorithm:

Choose a vertex $v$ and calculate its degree $k$. Then verify that all other vertices have degree $k$.
Choose some neighbor $w$ of $v$ and calculate the number of common neighbors $\lambda$. Then verify that all other pairs of adjacent vertices have $\lambda$ common neighbors.
Choose some non-neighbor $x$ of $v$ and calculate the number of common neigbors $\mu$. Then verify that all other pairs of non-adjacent vertices have $\mu$ common neighbors.

If you like linear algebra, you can also compute the square $A^2$ of the adjacency matrix $A$. Then check that:

All diagonal entries of $A^2$ are equal to some constant $k$.
All off-diagonal entries $A^2_{ij}$ such that $A_{ij} = 1$ are equal to some constant $\lambda.
All off-diagonal entries $A^2_{ij}$ such that $A_{ij} = 0$ are equal to some constant $\mu$.

This algorithm takes time $O(n^\omega)$.


Are the capabilities of programming languages the same?

The answer to the question depends on what you mean by "the same".

It is a famous result of computability theory that many reasonable models of computation all calculate the same nubmber-theoretic functions. That is, all reasonable general-purpose programming languages compute the same partial functions $\mathbb{N} \to \mathbb{N}$. So in this sense the capabilities of all programming languages are "the same". By the way, this is not the Church-Turing thesis, contrary to what you may be told.

However, a programming language can do many other things in addition to computing with numbers. For instance, it may access external devices, run parallel programs etc. While these features do not allow it to compute any extra number-theoretic functions, they may make a difference when it comes to computing other functions. For instance, a famous early example is that of the language PCF. It can simulate Turing machines, but it cannot compute the "parallel or" function, while its parallel variant PCF++ can.

When we look at higher-order functions languages differ in their capabilities. A purely functional language such as Haskell cannot compute the modulus of continuity but a functional language extended with local state can.

So it really depends on what you mean by "the same".


The total time require for a pipeline to execute

The exact time could be obtained as $\tau\sum p_i\,c_i$ where $p_i$ is the probability of taking $c_i$ cycles. Let's admit that by virtue of linearity, it ends up to be equivalent to $\tau\sum p_i\,C_i$ with two terms, $p_0=pq$,  thus $p_1=(1-pq)$. The two terms $C_0$ and $C_1$ must make the formula correct for the extreme cases $pq=1$ and $pq=0$.

The $C_0=nk$ term (the question's first case) is the number of cycles it would take to execute the $n$ instructions with each requiring $k$ cycles (because each jumps to a non-consecutive location and requires refilling the $k$ stages).

The $C_1=k+n−1$ term is the number of cycles it would take for linear code (either because there is no branch instruction, or none jumps to a non-consecutive address). The $n$ term is such that each additional instruction adds one cycle, and the other terms are such that for $n=1$, the outcome is the $k$ cycles necessary to fill the $k$ stages of pipeline.


Running an algorithm on data remotely and ensuring answer has not been tampered with

In the crypto community, this task is known as delegated computation, or verifiable delegation. You wish to let the server (the "cloud") to do the work for you, but you also want the cloud to give you some proof that it actually performed the computation (and didn't just output a random output, and ran away with your money).

A pointer, off the top of my head, is "Delegating computation: interactive proofs for muggles" (Goldwasser, Kalai, and Rothblum, J. ACM (62), 2015). Other solutions probably exist, look inside.


A language is in $\mathsf{DTIME}(f(n))$ if there is a Turing machine accepting the language and running in time at most $f(n)$ (or, in some definitions, $O(f(n))$). Therefore $f(n) \leq g(n)$ implies that $\mathsf{DTIME}(f(n)) \subseteq \mathsf{DTIME}(g(n))$. The same holds for relativized classes.


Nearest Neighbor Search in Spherical Coordinates

Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates.

I don't understand this restriction. Converting to Cartesian coordinates uses essentially the same trigonometric functions that you would need to find the distance between two points in spherical coordinates: the only fundamental difference is that working directly in spherical coordinates you can take the cosine of the difference of azimuthal angles rather than taking sine and cosine of the individual azimuthal angles.

In any case, you should be able to bound the error in converting to Cartesian coordinates and take that error bound into account to create a shortlist of candidates using k-d trees; then recalculate the distances for the points in the shortlist using the spherical coordinates directly.


Algorithm to find if there are N 1's in a matrix where no two 1's are in same row or column

This is the perfect matching problem in a bipartite graph: construct a bipartite graph with nodes $1,...,N$ on one side and nodes $-1,...,-N$ on the other side, and with an edge from $i$ to $-j$ if your matrix has a 1 in row $i$, column $j$. Then a perfect matching in this graph corresponds to a subset of ones in the matrix having the property that no two of them are in the same row or column.

Textbook algorithm

The Hopcroft-Karp algorithm solves the problem; it can determine if a perfect matching exists in time $O(\sqrt{N} M)$ where $M$ is the number of ones in your matrix (clearly, $M \le N^2$).

A simpler randomized algorithm

If you are satisfied with a randomized algorithm (with a small probability of error), there is indeed a conceptually simpler algorithm due to László Lovász. Create a new matrix $X$ in which every 1 in the original matrix is replaced by a random integer between 1 and some bound $P>100 \cdot N$; zeros in the original matrix remain zeros in $X$. Compute the determinant of $X$. If $det(X) \neq 0$, then for sure the original matrix has a perfect matching; if $det(X) = 0$, then with probability at least $1-1/100$, the original matrix does not have a perfect matching. (If you want to be sure that the value of the determinant does not overflow, you can do the computations modulo $P$ if you choose $P$ to be prime.) Computing the determinant will take time $O(N^3)$ with standard decomposition methods.

An even simpler (and slower) method

The simplest polynomial-time algorithm I know for bipartite perfect matching is due to Linial, Samorodnitsky and Wigderson and runs in time $O(N^4 \log N)$. Let $c_j$ denote the sum of the elements in column $j$. The algorithm is as follows:

  For $N^2 \log N$ iterations do:
      1. Normalize each column so that it sums to 1
      2. Normalize each row so that it sums to 1
      3. Compute $c_1,\ldots,c_N$
      4. If $\sum_{j=1}^N (c_j-1)^2 < 1/N$ return YES
   Return NO

If $N$ is tiny

If you want something even simpler (?) to implement (but much, much slower if $N$ is large), you could just enumerate all permutations over $N$ elements, and for each of these check if the corresponding set satisfies your property. That is, for each permutation $\pi: \{1,\ldots,N\} \to \{1,\ldots,N\}$, you check if cell $(i, \pi(i))$ of the matrix contains a 1, for each $i=1,\ldots,N$. The standard libraries of some programming languages have support for generating all permutations of a set; for example, itertools.permutations in Python or next_permutation in C++.
However, this approach based on enumeration will take time about $N \cdot N!$, which is more than exponential in $N$. It will probably only be acceptable if $N$ is at most around 10-12.


Proving that language, with $|\Sigma|=1$, is irregular by Myhill–Nerode theorem

Your idea is basically correct, but your argument could be written in a clearer way. You want to say that if $i \neq j$ then $0^{2^i+1},0^{2^j+1}$ are inequivalent. You propose to consider adding the word $0^{2^i-1}$ to both, obtaining $0^{2^{i+1}},0^{2^i+2^j}$. The first word is clearly in $L$, whereas the second isn't, though an argument is required (left to you). This shows that the infinite set $\{0^{2^i+1} : i \geq 0\}$ consists of pairwise inequivalent words (modulo $L$), so $L$ is not regular.

In fact, all words $0^n$ are pairwise inequivalent modulo $L$ – see if you can prove that. (The argument is very similar.)

For languages over a unary alphabet there is a simpler characterization. Let $L = \{0^n : n \in I\}$. Then $L$ is regular if and only if $I$ is eventually periodic, which means that for some $m \geq 1$, $n + m \in I$ iff $n + 2m \in I$. The set of powers of two is not eventually periodic since it has arbitrarily large "gaps". (A formal argument is similar to your proof.)


Can an NP-Complete problem be reduced to an NP problem?

An NP-complete problem is in NP, by definition. No reduction needed.


Serving $k$ customers with bounded time window

The problem can be solved in $O(n \log n)$ time where $n$ is the number of clients  (Note that in the trivial case where $k > n$, you simply serve all clients as soon as they come.)
The algorithm is well-known: Sort the intervals by startpoint, endpoint.
Then you iterate over the intervals, for each minute.
If you are at a point where more than $k$ intervals end the next minute, you cannot solve it.
Otherwise you remove the $k$ first intervals in your list, and increase the minute counter.

Note that to be truly polynomial, you might need to skip further ahead than to the next minute, but that's an exercise.  (E.g. when the input is
$$\left[(2^0, 2^1), (2^2, 2^3), (2^4, 2^5), ..., (2^{100}, 2^{101})\right]$$
or other large numbers.)


Online algorithm for finding of clique of size k

Since I don't have enough points for a comment:

This problem is not going to have a very efficient solution. Looking at the $k=3$ case should be good start. In this case one can solve this problem with $O(|E|)$ space by keeping an (online) adjacency set for each vertex and when an edge $(u,v)$ arrives comparing the adjacency sets of vertices $u$ and $v$ for a collision (in time linear in the size of the smaller set) and then adding $(u,v)$ to the sets of vertex $u$ and $v$.

The run time of this algorithm would be $\sum_v d(v)^2$, where $d(v)$ is the degree of vertex $v$ in the final graph. This is never bigger than $O(n^3)$, where $n$ is the number of vertices in the final graph.

It is unknown whether triangle detection (i.e., a clique of size 3) can be done in  less than $n^3$ time even if you had the entire graph before you. See this, for instance.


Given a set of (x,y) coordinates, give the set of edges to draw a simple polygon

A copy from the highest voted answer from SO:

    Our strategy is to make a plan where we are sure that the polygon
    includes all points, and that we can find an order to connect them
    where none of the lines intersect.

    Algorithm:

    Find the leftmost points p
    Find the rightmost point q
    Partition the points into A, the set of points below pq, and B, the set of points above pq [you can use the left turn test on (p,q,?)
    to
    determine if a point is above the line].
    Sort A by x-coordinate (increasing)
    Sort B by x-coordinate (decreasing).
    Return the polygon defined by p, the points in A, in order, q, the points of B in order.

    Runtime:

    Steps 1,2,3 take O(n) time.
    Steps 4,5 take O(nlogn) time.
    Step 6 take O(n) time.
    Total runtime is O(nlogn).

    Correctness:

    By construction, all points besides p,q are in set A or
    set B. Our output polygon from line 6 therefore outputs a polygon with
    all the points. We now need to argue that none of the line segments in
    our output polygon intersect each other.

    Consider each segment in the
    output polygon. The first edge from p to the first point in A can't
    intersect any segment (because there is no segment yet). As we proceed
    in order by x-coordinate through the points in A, from each point, the
    next segment is going to the right, and all previous segments are to
    the left. Thus, as we go from p, through all the points of A, to point
    q, we will have no intersections.

    The same is true as we go from q back
    through the points of B. These segments cannot intersect each other
    because they proceed from right to left. These segments also cannot
    intersect anything in A because all points in A are below line pq, and
    all points in B are above this line.

    Thus, no segments intersect each
    other and we have a simple polygon.

  Source: Broken link

  I understand this is really late, but it might be useful for future
  viewers.


Does using micro-operations require a higher clock rate than listed

That's not necessary, and also not how it is actually done. The way Skylake and most other microarchitectures executes multiple instructions in the same cycle is in parallel, not in sequence within a cycle.

So the registers would not be read at several different moments during a cycle, instead several reads are done simultaneously. That does not present a structural hazard: the read logic can be duplicated, as in multi-ported SRAM.
Clearly such duplication is not free, but it can be kept in check by exploiting the fact that most registers being read are "hot" (written to recently) and their value will be supplied by different mechanisms anyway (forwarded just-in-time or captured in the reservation station if applicable). Core2 for example could only read 2+1 different entries from its retirement register file (the +1 is for the special case of a register being used as the index in a SIB-encoded address), but for "hot" registers it had no particular limit (or none that I know of). From SandyBridge onward Intel has been using an alternative organization with more of a tag-indexed physical register file style and there seems to be no particular limit on reading from it (so maybe they just went with plenty of read ports there?). Anyway the TL;DR is that the multiple µops in a cycle and their register reads are not sequential and don't need a faster clock.

NetBurst (Pentium 4) actually did have a faster internal clock for its fast ALUs and AGU, but not for everything (excluding for example the register file), and the reason was not that register reads needed to be sequential (they weren't), just for raw computation speed with low latencies. There were two ALUs, so together they can execute 4 ALU operations per cycle, though the front-end cannot supply them with new operations that quickly so the peak throughput cannot be sustained and is only reached in bursts. It is more complicated than executing two operations per ALU in sequence within a "normal cycle" though. Instructions actually take 3 FLCK cycles, in the first cycle the low 16 bits of the result are computed, in the second cycle the high 16 bits are computed and a dependent instruction can already start (since it would also only compute the low 16 bits of its result in the first cycle, so for now it only needs the low 16 bits of its inputs) and in the third cycle the flags are computed.


If L is regular, so is L2 (proof using closure properties)

Here are several possible ways of proving that if $L$ is regular then so is $M$.

Method 1

Show first that the language
$K = \{ a^r : |s|_a=r \text{ for some } s \in M \}$.
You can obtain $K$ from $L$ by deleting all letters other than $a$. Then show that $M$ is regular by "undeleting" all letters other than $a$.

Method 2

Construct an NFA for $M$ directly, given an NFA for $L$. At each step, the new NFA accepts non-$a$ letters gratuitously, both in the input and in its simulation of the NFA for $L$. It also reads $a$, but then must also simulate an $a$ transition on the NFA for $L$. Finally, it accepts whenever it can get the NFA for $L$ to be at an accepting state.

Method 3

Parikh's theorem shows that $K$ (defined in Method 1) is eventually periodic. That is, for some integers $m,p$ and sets $A \subseteq \{0,\ldots,m\}$, $B \subseteq \{0,\ldots,r-1\}$ we have
$$
K = \{ a^i : i \in A \} \cup \{ a^{m+rj+i} : j \geq 0, i \in B \}.
$$
Given this, we can construct a DFA for $M$ directly (exercise).


Solving recurrence $T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$

Observe that $T_k(2^n k) = 2^n$. Furthermore, it is easy to see that either $T_k(\alpha) = T_k(\alpha-1)$ or $T_k(\alpha) = 1+T_k(\alpha-1)$. Using the previous two results, it can also be shown that $T_k(2^n k - 2^{n-1}) = T_k(2^{n-1} k)$.

Now, consider
$$\delta_k(n) = T_k(2^n k - 2^{n-1} + 1) - T_k(2^n k - 2^{n-1} )$$

It should be easy to prove by induction that for all $k, n$ it holds that $\delta_k(n) = 1$. This should be sufficient to uniquely determine the value of $T_k(n)$ for all $n$.


what algorithm is used to calculate the exponential function $e^x$?

Let $x = n \log_e(2) + x'$, then $e^x = 2^n \cdot e^{x'}$.
You can pick n so that $- 0.5\cdot \log_e(2) ≤ x' ≤ +0.5 \cdot \log_e(2)$.
$e^{x'}$ is easy to calculate because $x'$ is small, and $2^n$ can be calculated easiest by producing the bit represenation of $2^n$ as a floating point number.
That's the principle. You'll want to take care that x' is calculated with the highest possible precision, and that $e^{x'}$ is also calculated with the highest precision. And you want to take care if x and x+eps use different values n, that $e^x$ and $e^{x+eps}$ fit together nicely; you wouldn't want a sitation where $e^{x+eps} < e^x$ with eps > 0.


Are non-ordered (Slabbed) Neural Networks in wide modern use and what does Fiesler (1994) mean by Clamping Function and Ontogenic function?

I have not heard of recent work on this kind of thing, but there's a huge amount of literature and I know only a tiny slice of it.
Today much of the work on neural networks is concerned with feedforward neural networks, which don't have a cyclical structure.  The most common form is
$$z(x) = L_n(\cdots (a(L_1(x))))$$
where $f:\mathbb{R}^n \to \mathbb{N}^k$, each $L_i$ is a linear function, and each $a$ represents an activation function: i.e., $a(x_1,\dots,x_d) = (a(x_1),\dots,a(x_d))$ and $a$ is a simple nonlinear function called the activation function.  The ReLU $a(x)=\max(0,x)$ is a common choice of activation function.  There is some cleverness in the structure of the linear layers.  Finally, the output of the neural network is $f(x)=\text{softmax}(z(x))$ where
$$\text{softmax}(z_1,\dots,x_k) = ({e^{z_1} \over e^{z_1} + \dots + e^{z_k}}, \dots, {e^{k_1} \over e^{z_1} + \dots + e^{z_k}}).$$
This is not the only architecture, but it is probably the most commonly seen, and as you can see, it has a relatively clean formalization.


Maximum coverage 1/2-approximation algorithm: why does the central lemma hold?

Let $S_{O_1},\ldots,S_{O_k}$ be an optimal solution, and let $O = S_{O_1} \cup \cdots \cup S_{O_k}$.

At the $i$'th iteration, suppose that the elements covered by the sets chosen the algorithm form the set $T$. Let $S'_{O_i} = S_{O_i} \setminus T$ and $O' = O \setminus T$, that is, we have removed from the optimal solution all elements already covered. Since
$$
|O'| = |S'_{O_1} \cup \cdots \cup S'_{O_k}| \leq |S'_{O_1}| + \cdots + |S'_{O_k}| \leq k \max_{i=1}^k |S'_{O_i}|,
$$
we see that among the sets $S_{O_1},\ldots,S_{O_k}$, at least one (the one maximizing $\max_i |S'_{O_i}|$ covers at least $|O'|/k$ uncovered elements.

The greedy algorithm chooses a set covering at least as many uncovered elements. This allows us to obtain a lower bound on its approximation ratio, as follows. Let $T_i$ be the union of the sets chosen in the first $i$ steps of the greedy algorithm. The starting point is $T_0 = \emptyset$. At step $i$, the argument above shows that we cover at least $|O'|/k$ new elements. Since $|O'| = |O \setminus T_{i-1}| \geq |O| - |T_{i-1}|$, this shows that
$$
|T_i| \geq |T_{i-1}| + (|O| - |T_{i-1}|)/k = \left(1 - \frac{1}{k}\right) |T_{i-1}| + \frac{|O|}{k}.
$$
In particular,
$$
\begin{align}
&|T_1| \geq \frac{|O|}{k} \\
&|T_2| \geq \frac{|O|}{k} + \left(1 - \frac{1}{k}\right) \frac{|O|}{k} \\
&|T_3| \geq \frac{|O|}{k} + \left(1 - \frac{1}{k}\right) \frac{|O|}{k} + \left(1 - \frac{1}{k}\right)^2 \frac{|O|}{k}
\end{align}
$$
and so on. At the end of the algorithm we get a set $T_k$ satisfying
$$
\begin{align}
|T_k| &\geq \frac{|O|}{k} \left[1 + \left(1 - \frac{1}{k}\right) + \cdots + \left(1 - \frac{1}{k}\right)^{k-1}\right] \\ &=
\frac{|O|}{k} \frac{1 - \left(1 - \frac{1}{k}\right)^k}{1 - \left(1 - \frac{1}{k}\right)} \\ &=
\left(1 - \left(1 - \frac{1}{k}\right)^k\right) |O|.
\end{align}
$$
Now it's time for some calculus:
$$
\ln \left(1 - \frac{1}{k}\right) = - \frac{1}{k} - \frac{1}{2k^2} - \cdots \leq -\frac{1}{k},
$$
and so
$$
\left(1 - \frac{1}{k}\right)^k = \exp\left[k\ln \left(1 - \frac{1}{k}\right)\right] \leq \exp (-1) = 1/e,
$$
implying that
$$
|T_k| \geq \left(1 - \frac{1}{e}\right) |O|.
$$
In other words, the greedy algorithm gives a $(1-1/e)$-approximation (this is better than your claimed $1/2$). It turns out that $1-1/e$ is tight for the greedy algorithm, and moreover, then $1-1/e$ cannot be improved by a polynomial time algorithm unless $\mathsf{P} = \mathsf{NP}$ (and unconditionally in the value oracle model).


Why don't we use quick sort on a linked list?

The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result.
At the same time the merge sort is external, it requires additional array to return ordered result. In array it means additional space overhead, in the case if linked list, it is possible to pull value out and start merging nodes. The access is more sequential in nature.

Because of this, the quicksort is not natural choice for linked list while merge sort takes great advantage.

The Landau notation might (more or less, because Quicksort is still $\mathcal O(n^2)$) agree, but the constant is far higher.

In the average case both algorithms are in $\mathcal O(n\log n)$ so the asymptotic case is the same, but preference is strictly due to hidden constant and sometimes the stability is the issue (quicksort is inherently unstable, mergsort is stable).


Finding perfect matchings with as few database queries as possible

A $O(n \log n)$ solution works as follows:

For each man $M$, we find the matching woman in $O(\log n)$ queries. We start by dividing the women into two sets of size $n/2$. Using one query, we can find out which of the two halves contains $M$'s match. We recurse on that half.


Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1)

Here is a proof sketch from Robins and Salowe, On the Maximum Degree of Minimum Spanning Trees. Let $x$ be some vertex in the MST. We want to show that its degree $d$ is small.

Let $y_1,\ldots,y_d$ be its neighbors. Draw a small circle of radius $\epsilon$ around $x$, and "project" each $y_i$ to a point $z_i$ on the circle: the point $z_i$ is just the intersection of the line $\overline{x y_i}$ and the circle. The idea is to show that all of these projections are far from each other.

Indeed, consider any pair of points $y_i,y_j$, and suppose without loss of generality that $\|x-y_i\| \leq \|x-y_j\|$. Repeat the same process as before, but with a circle of radius $\|x-y_i\|$. The projections are $w_i = y_i$ and $w_j$. The triangle $\Delta xz_iz_j$ and $\Delta xy_iw_j$ are similar, and so $\|z_i-z_j\|/\epsilon = \|y_i-w_j\|/\|x-y_i\|$.

On the other hand, consider the circle $\Delta xy_iy_j$. Two of the edges are in the minimum spanning tree, so the remaining edge must be a heaviest edge. Since we assumed that $\|x-y_i\| \leq \|x-y_j\|$, this means that $\|y_i-y_j\| \geq \|x-y_j\|$. Therefore
$\|x-y_j\| \leq \|y_i-y_j\| \leq \|y_i-w_j\| + \|w_j-y_j\|$.
Since $w_j$ is on the line from $x$ to $y_j$, we have $\|x-y_j\| = \|x-w_j\| + \|w_j-y_j\|$, and so $\|x-w_j\| \leq \|y_i-w_j\|$. Since $w_j$ is on the circle of radius $\|x-y_i\|$ centered at $x$, this shows that $\|x-y_i\| \leq \|y_i-w_j\|$.

Combining the formula $\|z_i-z_j\|/\epsilon = \|y_i-w_j\|/\|x-y_i\|$ with the inequality $\|x-y_i\| \leq \|y_i-w_j\|$, we deduce that $\|z_i - z_j\| \geq \epsilon$. Summarizing, $z_1,\ldots,z_d$ are points on a circle of radius $\epsilon$ which are at distance at least $\epsilon$ from each other. This forces $d \leq 6$.

Perhaps the following diagram will be useful:

Suppose that the inner circle has radius $\epsilon$. We want to show that $\|z_i-z_j\| \geq \epsilon$. Due to the MST property, we know that $\|y_i-y_j\| \geq \|x-y_j\|$. Thus necessarily $\|y_i-w_j\| \geq \|x-w_j\|$. This implies $\|z_i-z_j\| \geq \|x-z_j\|$ due to similarity of triangles.

Robins and Salowe note that when $d = 6$, the points are packed tightly. It turns out that there is always an MST in which there is always some jiggle room, and so some MST has maximum degree at most $5$.

The same argument works in $D$ dimensions and in any metric, as long as there is a bound on the number of points on a unit ball which are at least a unit distance away from each other. This property holds in all $L_p$ metrics (for finite $p$!) in any dimension.


Determining the number of walks between two vertices in a graph

The following answer assumes that by walk you mean path. If you really mean walk, then if $v_1$ and $v_2$ are connected, there are always infinitely many walks between $v_1$ and $v_2$. (A path is a walk without repeated vertices.)

Run DFS from $v_1$, and consider the resulting DFS tree. We can assume that $v_2$ appears in the tree, since otherwise there is no path between $v_1$ and $v_2$. There is always one path from $v_1$ to $v_2$, namely along the tree edges. When is this path unique?

Let us show that the path is unique iff there are no back edges whose target is between $v_1$ (inclusive) and $v_2$ (exclusive). (The target of a back edge is the vertex closer to $v_1$.)

Suppose first that there is a back edge from $y$ to $x$. The following is another path from $v_1$ to $v_2$:
$$ v_1 \leadsto x \to y \leadsto v_2, $$
where $\leadsto$ is a path along the tree edges, $x \to y$ is the back edge. (There are really three different cases here: $y$ above $v_2$, below $v_2$, and equal to $v_2$.)

In the other direction, suppose that $p$ is a path from $v_1$ to $v_2$ which is not solely along tree edges. The first edge in $p$ which is not a tree edge must be a back edge. A short case analysis (considering the direction in which the back edge is taken) shows that the target of the back edge must be between $v_1$ (inclusive) and $v_2$ (exclusive).


Correctness proof for finding weighted maximum independent set for a tree

Here is an easier-to-understand dynamic programming approach. I think if you can prove this, then you can prove yours.

Let $\textsf{I}(u)$ be the weight of the weighted largest independent set of subtree rooted at $u$.

The goal is to compute $\textsf{I}(r)$, where $r$ is the root of the tree.

The recurrence relation for dynamic programming is:

$$\textsf{I}(u) = \max \{ w(u) + \sum_{v: \text{ grandchild of } u} I(v), \sum_{v: \text{ child of } u} I(v) \}$$

Can you prove (or disprove) it?

Hint: Do a simple case-by-case analysis.


In how many steps Euclidean Algorithm will find the GCD for two integers

It can be observed that the product $ab$ drops by a factor of at least two for each iteration.

Prior to each iteration, we have the pair $(a, b)$ such that $a < b$, which is replaced by the pair $(r, a)$ at the end of each iteration in preperation for the next, where $r = b \bmod a$. We then have $r < a$ and $a + r ≤ b$. Hence, $b ≥ a + r > 2r$. So, $ar < \frac{1}{2}ab$.

Supposing it takes N steps to compute $gcd(a, b)$ using the Euclidean algorithm, we then have $ar ≤ \frac{ab}{2^N}$ after N steps. It follows that $ab ≥ 2^N$.

Hence, $N ≤ \log_2 ab = \log_2 a + \log_2 b$.

Therefore, the number of steps it takes to compute $gcd(a, b)$ using the Euclidean algorithm is at most $\log_2 a + \log_2 b$.

Furthermore, on Wikipedia, you can observe that the worst case is $N ≤ 5 \log_{10} a$, i.e. five times the number of (base-10) digits of $min(a, b) = a$, where $(a, b)$ is a pair of consecutive Fibonacci numbers. This relationship is useful because $gcd(F_{n+1}, F_{n+2}) = 1$ (i.e. all consecutive Fibonacci numbers are coprime).

Given these upper-bounds, the asymptotic computational complexity of the Euclidean algorithm can be expressed using Big-O notation as $\mathcal{O}(\log b)$.

Since,

$$\mathcal{O}(\log b) = \mathcal{O}(\log_2 a + \log_2 b) = \mathcal{O}(5\log_{10} a)$$

where $b ≥ a$.


Is there a name for X when X bitwise OR Y is Y?

I would say that $X$ is a subset of $Y$, in terms of bits set.


Construct a DFA which accepts a string of length 5 with at least 2 0's

The question asks HOW TO DESIGN, you don't have to write the whole DFA, but you can if you want to. Just describe how you would design.

There are 32 strings of length 5. Some of them do not contain at least two 0s, some do. Those that do not contain at least two 0s should lead to the DEAD state (from which there is no return). But those that do have at least two 0s should lead to a state that checks another block of 5 symbols.

Try to draw a binary tree of depth 5, with 0 as the left child and 1 as the right child for each node. Does it help design the DFA? For simplicity first try to design for blocks of 3 symbols not 5.


This can be calculated using dynamic programming: for each $0 \leq T \leq D$ and $0 \leq \ell \leq n$, calculate $C(T,\ell)$, which is the number of solutions over $\{1,\ldots,m\}$ of $\sum_{i=1}^\ell a_i = T$. The base case is $C(0,0) = 1$ and $C(T,0) = 0$ if $T > \ell$. For $\ell > 0$, we have the formula $C(T,\ell) = \sum_{S=\max(T-m,0)}^{T-1} C(S,\ell-1)$. The answer is $C(D,n)$. This algorithm runs in time $O(mnD)$.

Equivalently, you are looking for the coefficient of $x^T$ in the generating function $(x+\cdots+x^m)^n = x^n\left(\frac{1-x^m}{1-x}\right)^n$. This expression can be massaged to give an explicit formula involving a double summation with alternating signs.


How to solve recurrence $T(n) \le 2T(n/3) + c\log_3 n$ using substitution method


Is dependency analysis required in order to type a program?

Any use of a type anywhere may place constraints on that type. So, in the absence of explicit type signatures (i.e. when doing type inference) it is necessary to perform inference in a way that doesn't allow specific usages of a type in a particular form to "infect" the most general type it may have. This involves a dependency analysis. Consider

id = \x -> x
foo = id 1

Now if we type foo first, we would unify the first argument of id with Int and thus conclude id had type Int -> Int. So therefore we must first type id and then generalize its signature to the polymorphic type forall a. a -> a, and then instantiate that at type Int when we apply it and attempt to unify the argument type with Int.

Hence, dependencies and topological sort!


Using 4-SUM to improve Subset Sum $O(2^{n/2})$ runtime

Work through the math; you are off by a factor of two.  Also, you might be confusing yourself by using the same letter $n$ for two different things.

Suppose we have a list of $N$ numbers.  You are proposing to split that into four chunks, where each chunk has $N/4$ numbers.  Enumerating all of the subsets of a single chunk takes $O(2^{N/4})$ time.  Now, you have a 4-sum problem where you are working 4 lists each containing $M=2^{N/4}$ items.  This 4-sum problem can be solved in $O(M^{k/2}) = O(M^{4/2}) = O(M^2)$, and $M^2 = 2^{N/2}$, so your proposed algorithm runs in $O(2^{N/2})$ time.

There is an algorithm for subset-sum that runs in time $O(2^{N/2})$ and space $O(2^{N/4})$.  The algorithm is due to Schroeppel and Shamir.  However, it's running time is still $O(2^{N/2})$, not $O(2^{N/4})$.

I don't think there is any known subset-sum algorithm whose running time is non-trivially better than $O(2^{N/2})$.  Blum, Kalai, and Wasserman have solved a related problem in subexponential time, but it's a different problem.


What happens at the decode phase of the instruction cycle?

The name "decoding" is actually a bit misleading because more things take place in this stage. You can view it as a translation from the external, programmer-visible representation of the instruction, to the CPU's internal interpretation.

All CPU architecture have an encoding of instructions, usually involving the specification of a number of op-codes specifying the "action" of the instruction (as opposed to the arguments, which might be registers, memory locations etc.). Note that the op-code is just a number, often just a byte. For instance, the addition instruction might have byte value 0x01, the subtraction might be 0x02 and so on. However, note that the numbering is somewhat arbitrary. It doesn't in itself say what the instruction does - this is something you would have to look up in the instruction manual.

What the decoding stage does is to map these numbers to the actual action of the instruction. This often involves looking up the OP-code in a data-structure, for instance a ROM. You could compare the decode stage to you looking up the op-code in a manual, to see what the instruction actually is. Now, your instruction manual is written in a human-readable language. What is the computer's manual written in? One method used in many implementations is that the ROM maps the op-code to a value which specifies the control signals that must be sent further into the execution pipeline to cause the action that is to be executed. For instance, if the instruction involves looking up the values of registers, adding them, and storing the result in another register, the ROM will contain values for the control signals that commands the register banks into read mode and the ALU into addition mode. The details of what the control signals are, are of course implementation dependent, depending on how the CPU internally functions and what control signals its various internal units accepts. However, the point is that the decode stage maps the representation of the instruction (in the form of op-code) to the actual action, in the form of these control signals. Note that on many architectures, one instruction might actually be decoded into several such "micro-instructions" with each micro-instruction essentially being a long word of all these control signals. This allows the architecture to provide the application programmer with complex instructions with short encoding. This generating and sequencing of micro-instructions might also take place in the decode stage.

Now you could ask, why not just let the instruction op-code contain all these control signals? In that case, the decode stage might not be necessary. Only problem is, that execution of an instruction often involves a lot of control signals, meaning instructions would be very long, just got the op-code. Also, it would expose the internal workings of the CPU since the external representation of instructions would now be deeply tied to the internal workings.

By the way, some architecture have very complicated encoding scheme so here the decoding involves a lot more work than just a lookup in a ROM, but in fact rather complicated logic just to determine the length and the prefixes etc. of the instruction. Also, various tricks might be necessary to keep the ROM at an acceptable size and also to allow fast look-up. On superscalar instructions, it is even possible to do this for several instructions in parallel even for encodings with variable length instructions! So as you can see, decoders can be pretty busy!


Shifting deletion algorithm for linear-probing hash table

There are two main approaches to cover the "wraparound" case:

"Triple condition", e. g. see java.util.IdentityHashMap source, or with more clarifying comments here
Second approach is based on counting the distance to the empty slot and comparing it with the distance between the slot where the "candidate for shift" is observed and where it should have been inserted if the hash table is empty, which could be obtained (covering the wraparound case) by substracting the index of the slot where the key should have been isnerted from the index of the current slot in the table, modulo table size (binary & (tableSize - 1) if the table size is a power of two). Example imlementation of this approach could be found here.


Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?

(i) Where do the heuristic values for shortest distance come from? There is mention of "straight roads" but I don't understand this. I know "heuristic" is "informed guess" but why not values 1237, 978, 516, ... etc. or any other arbitrary, descending values for the heuristic distance "still to go" ?

When you decide to use A* to solve a problem, you need to design an appropriate heuristic. Designing a heuristic is a creative act, so one can't really give advice on how to do it. Ideally, though, the heuristic should give a good estimate of the true cost.

The purpose of the heuristic is to guide the search and a search that receives accurate guidance will terminate faster than one that receives poor guidance.  There is, however, a trade-off. If your heuristic is perfect, then it will guide the search so well that the optimal route is the first one it examines. But, of course, if you could compute this perfect heuristic, you wouldn't need to be using search in the first place! Having a better heuristic means you spend less time searching, but you need to balance that against the fact that you'll probably spend more time computing this better heuristic.

  (ii) What is the significance and meaning of "the heuristic must never make an over-estimate"? How do we know that, and why is it important?

You know it because you figured it out and you designed the heuristic to achieve that. The classic example is using straight-line distance as a heuristic for navigation. You know that the straight-line distance is the shortest possible distance between two points, so it cannot overestimate the distance you'd have to travel on the road network.

I wrote an answer a while ago about why it's important that you don't overestimate. Essentially, if you say "every route via X is long", the algorithm will first look at routes via other places, and potentially find one. When it finds an answer, it will stop. But it never considered routes via X so, if it turns out that the shortest route was via X, you missed it because your heuristic overestimated.

  Surely all the intermediate distances before the completion of the A* algorithm are "over-estimates".

No. A*'s use of the heuristic means that, any time you expand a node in the search, you've found the shortest possible path to that node. So, every time you expand a node, you've found the optimal path to that node, plus an underestimating heuristic to the goal: all your intermediate states that get expanded are underestimates. There might be over-estimates in the frontier (i.e., suboptimal routes to intermediate goals) but they'll never get expanded.


show that NP is a subset of decidable languages

Every language that is in NP is by definition decidable. Becase if a language L is in NP, than there is a nondeterministic Turing Machine that decides it in polynomial time, and thus L is decidable.


What is the consequence of $\oplus P\neq PP$?

Turns out, you are immediately able to separate $\mathrm{P}$ from $\mathrm{PP}$.

Assuming that $\oplus\mathrm{P\neq PP}$ but also assume to the contradiction that $\mathrm{P=PP}$, then $\mathrm{P^{PP}=P}$. But $\oplus\mathrm{P\subseteq P^{\#P[1]}=P^{PP}=P}$. So, $\oplus\mathrm{P=P=PP}$ violating our assumption and concluding our proof by contradiction.


Dijkstra works as follows:

Take the first node from OPEN. Let $n$ denote such node. OPEN contains all nodes generated in ascending order of $g(n)$, where $g(n)$ is defined as $\sum\limits_{i=1}^{n-1} c(v_i, v_{i+1})$, and $c(v_i, v_{i+1})$ is the cost of the edge from $v_i$ to $v_{i+1}$. In other words, $g(n)$ is the sum of the edge costs in the path from the start state to node $n$.
If $n$ is the goal state, then halt. The optimal solution is the path from $s$ to $n$.
If $n$ is not the goal state, then verify whether it has been expanded before or not. Another list, called CLOSED contains those nodes already expanded. If $n$ is found in CLOSED, then go to 1. Otherwise, expand $n$ generating its successors. Evaluate $g(n')$ for each descendant $n'$ and add them to OPEN.
Remember you expanded $n$, so add it to another list called CLOSED. Go to 1.

Initially, OPEN=$\{s\}$ where $s$ is the start state and CLOSED=$\varnothing$ as you have expanded no node yet.

From your execution trace, it seems to me that you overlooked step 2, ie., Dijkstra stops when it is about to expand the goal state, and not when it is generated. As a matter of fact, you may generate the goal state an arbitrary number of times, but condition 2 is met only once.

Hence, in your specific case, Dijkstra works as follows:

Iteration #1
OPEN=$\{A\}$ and CLOSED=$\varnothing$

Take the first node from OPEN, $n=A$
It is not the goal state $A\neq B$
It does not appear in CLOSED, ie., it has not been expanded before. So that its descendants are generated: $C$ with a cost equal to 1 and $B$ with a cost equal to 2. They are now added to OPEN in ascending order of $g(n)$ so that OPEN=$\{C, B\}$
Add $A$ to CLOSED as it has been expanded, CLOSED=$\{A\}$

Iteration #2

Take the first node from OPEN, $n=C$
It is not the goal state, $C\neq B$
It does not appear in CLOSED, ie., it has not been expanded before. So that its descendants are generated: $B$ (its parent $A$ is easily removed as it is clearly its parent, but you can try to generate it as well and you'll see Dijkstra works smoothly the same). $B$ has now a $g$-value equal to 4 as it has been generated through the path $\langle A, C, B\rangle$. Hence, OPEN contains now $B$ twice: OPEN=$\{B, B\}$, the first one with a value equal to 2 (generated in the first iteration) and the second with a value equal to 4 (generated in this iteration).
Add $C$ to CLOSED as it has been expanded, CLOSED=$\{A, C\}$

Iteration 3

Take the first node from OPEN, $n=B$ (with a cost equal to 2).
It is the goal state. Halt with the path $\langle A, B\rangle$

Hope this helps,


Finding bicliques in a bipartite graph of minimum size

Here is an algorithm with $O(n^{2+\lg k})$ running time.  It's not polynomial in $k$ and $n$, but for fixed $n$ it is polynomial in $k$, and for fixed $k$ it is polynomial in $n$.  Here is the algorithm:

Let $\gamma = \lg k$.
Find all bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$.  Output $k$ of them (stop early once you have found $k$ of them).

In step 2, it's easy to find all bicliques such that $|U'| \le \gamma$, $|V'| \ge \delta$ in $O(n^{2+\gamma})$ time: just enumerate all possibilities for $U'$.  By the definition of $\gamma$, this takes $O(n^{2+\lg k})$ time, since there are only ${|U| \choose 0 } + \dots + {|U| \choose \gamma} = O(|U|^{\gamma}) = O(n^{\gamma}) = O(n^{\lg k})$ possible subsets $U'$ of size $\le \gamma$.

But will step 2 find enough bicliques?  You might worry that it will find fewer than $k$ bicliques, even when there are at least $k$ in the graph.  Not to worry; that can't happen.  In particular, I'll show that if there is a biclique that is too large to be found in step 2, then there are at least $k$ bicliques that are small enough to be found in step 2, so step 2 will find enough to output $k$.  The only way that step 2 can fail to output $k$ bicliques is if the graph does not contain $k$ bicliques.

Let's prove that claim.  If step 2 outputs fewer than $k$ bicliques and there exists a biclique that the algorithm didn't output, that means there exists a biclique with $|U'| \ge \gamma+1$ and $|V'| \ge \delta$.  What are the consequences of this?  Well, there are two cases, depending on the size of $U'$:

Case 1. Suppose $\gamma+1 \le |U'| \le 2\gamma$.  Then you can find at least $2^{\gamma}$ more such that $|U'| \le \gamma$ and $|V'| \ge \delta$.  Why?  Well, take any subset of $U'$ of size at most $\gamma$, and keep $V'$ unchanged.  Then this will give a new biclique, and it will meet all the conditions of the original problem.  The number of such subsets is ${|U'| \choose 0} + {|U'| \choose 1} + \dots + {|U'| \choose \gamma}$, which is at least $2^{U'}/2$ (since $\gamma \ge |U'|/2$).  Now $2^{U'}/2 \ge 2^{\gamma+1}/2 \ge 2^{\gamma} \ge k$, so this gives us $k$ more bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$.  Thus in this case there exist enough bicliques that step 2 can find $k$ of them.
Case 2. Suppose $|U'| \ge 2\gamma$.  Then you can find at least $2^{\gamma}$ more bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$.  Why?  Again, take any subset of $U'$ of size at most $\gamma$; that will lead to another biclique that can be found in step 2.  How many such subsets are there?  There are at least ${|U'| \choose \gamma}$ of them, and  ${|U'| \choose \gamma} \ge (|U'|/\gamma)^{\gamma}$ more (see the first bound here).  By assumption, $|U'|/\gamma \ge 2$, so this means there are at least $2^{\gamma}$ more such subsets, i.e., at least $2^{\gamma}$ more bicliques that can be found in step 2.  Thus in this case there exist enough bicliques that step 2 can find $k$ of them.

In either case, if the graph has at least $k$ bicliques, this algorithm will output at least $k$ of them.


Why are Oracle Separations Counted as Evidence toward Unconditional Separation?

At best, the evidence given is only heuristic and informal, but it is still important. Oracles in the examples you gave do address the general question: how does quantum computing compare to nondeterminism and randomness, in power? The oracles definitely do not answer the original unrelativized questions, rather they provide a different (related) black-box model where the question provably has a negative answer. Since unconditional lower bounds are very difficult to come by, oracles can be useful information, but again it's only heuristic.


Knapsack dynamic programming complexity issue for $W=1$, is it $O(n)$?

The running time is $O(nW)$ if all weights are integers. This is because the dynamic programming table is indexed by possible weights of subsets. If all weights are integers, then since we are only interested in subsets whose sum of weights is at most $W$, there are only $W+1$ weights of subsets that could possibly interest us. This is where the $W$ factor in the running time is coming from.

Dividing all weights by $W$ accomplishes exactly nothing. You haven't changed the problem, so the required time for solving it is remains exactly the same.


Misunderstanding of proof with transitivity of logspace reduction

$L_f$, by definition, gives you the output of $f(x)$ for a single bit $j$. Note that we do not have to copy $x$, so we're only storing $bin(j)$ and the $j$-th bit of  $f(x)$, which is in logarithmic space. Since $M_f$ computes $L_f$ with logarithmic space, we can simply get the $j$-th bit. This means that $M_h$ can work in logspace in total, as it only asks and stores a single bit of input from $M_f$ every time.


if a graph G(V,E) is connected $|E|\geq|V|-1$

Imagine a process in which you start with the empty graph, and add the edges one by one. Keep track of the number of connected components. In the beginning, there are $|V|$ connected components. Each edge you add either belongs inside a connected component, or merges two connected components, and in any case, the number of connected components decreases by at most 1. Hence after adding $|E|$ edges, the number of connected components is at least $|V| - |E|$. If the graph is connected, $|V| - |E| \leq 1$, and so $|E| \geq |V| - 1$.


Time complexity to sort 100 elements by using selection sort?

That's because you only have a constant number of elements, in this case 100. In other words, $100^2 = O(1)$, i.e., you do a constant amount of work. Usually it is more interesting to analyze the scalability of an algorithm with a growing input size $n$.


On the time complexity of finding independent sets in hypergraphs

The ubiquitous principle is that a generalized problem is at least as hard to the original problem. This rather trivial principle is applied as truism in most if not all papers.

Here is a specific version of that principle for the case of time-complexity.

Lemma. Let $A,B, C$ be three languages such that $A= B\cap C$ and $A\not=C$. ($C$ is considered as a generalization of $A$.) It takes polynomial time to determine whether $x\in B$. Then deciding $C$ is as least as hard as deciding $A$ modulo polynomial time. If $A$ is NP-complete and $C$ is in NP, then $C$ is NP-complete.

Proof. Let $\beta$ be a polynomial-time algorithm that decides $B$. Suppose we have an algorithm $\gamma$ that decides $C$. Let $\alpha$ be the following algorithm:

Given input string $x$, run $\beta$ to determine if $x\in B$. If not, return no. If yes, run $\gamma$ to determine if $x\in C$. If not, return no. Return yes otherwise.

It is routine to check that $\alpha$ return yes if and only if the input is in $A$, i.e., $\alpha$ decides $A$. Since $\beta$ takes polynomial time, deciding $C$ is at least as hard as deciding $A$ modulo polynomial time.

It follows immediately that if $A$ is NP-complete and $C$ is in NP, then $C$ is NP-complete.

Let

$A=\{\langle G,s\rangle \mid \text{ there is an independent set of size }s\text{ in an ordinary graph G}\}$. (I use the phrase "ordinary graph" or simply "graph" to contrast with "hypergraph". "General graph" sounds more like hypergraph. Indeed, hypergraph is a generalization of an ordinary graph.)
Let $B=\{\langle G\rangle\mid G \text{ is an ordinary graph}\}$.
Let $C=\{\langle G, s\rangle \mid \text{ there is an independent set of size }s\text{ in a hypergraph G}\}$.

The lemma tells us that deciding $C$ is at least as hard as deciding $A$.

Exercise 1. Explain that deciding whether a graph is 3-colorable is at least as hard as deciding whether a given planar-graph is 3-colorable. (In fact, both problems are NP-complete.)

Exercise 2. Prove that it is NP-complete to determine whether there is independent set of given size in a given triangle hypergraph. A triangle hypergraph is defined as a hypergraph where each edge is a set of 3 vertices.


Are there search algorithms that perform better on a Rope than a String?

Rooted trees, balanced or not, can be traversed in linear time via depth-first search. Actual implementations of balanced trees usually provide a way to iterate through it, taking amortized $O(1)$ for each step. So any algorithm will work without $O(\log n)$ overhead if it makes only a single pass through the string (or if it only requires a small bounded sliding window).


Generate ordered stream of $n$ random integers in a given range using $O(1)$ space (reference request)

It can be done in $O(1)$ space and $O(n^2)$ time.  Let $X_1,\dots,X_n$ denote the numbers in the stream, in sorted order.  You can calculate

$$\Pr[X_i = x_i | X_1=x_1,\dots,X_{i-1}=x_{i-1}]$$

and then use that to generate the numbers $X_1,\dots,X_n$ one by one.

Here is the derivation.  We have

$$\begin{align*}
\Pr[X_1=x_1,\dots,X_{i-1}=x_{i-1}] &= {{\text{max}-x_{i-1} \choose n-i+1} \over
{\text{max}-\text{min}+1 \choose n}}\\
\Pr[X_1=x_1,\dots,X_{i-1}=x_i] &= {{\text{max}-x_i \choose n-i} \over
{\text{max}-\text{min}+1 \choose n}}
\end{align*}$$

so it follows that

$$\Pr[X_i = x_i | X_1=x_1,\dots,X_{i-1}=x_{i-1}] = {{\text{max}-x_i \choose n-i} \over {\text{max}-x_{i-1} \choose n-i+1}}= \Pr[X_i = x_i | X_{i-1}=x_{i-1}].$$

Here the domain of possible values for $X_i$ is $x_{i-1}+1,\dots,\text{max}$; the probability is zero for other values of $X_i$ outside that domain.

Notice that this probability depends only on $x_{i-1},x_i$, so you only need a constant amount of space: you don't need to remember the entire past history.

Thus, the algorithm becomes:

Pick $x_1$ from the distribution $\Pr[X_1=x_1] = {{\text{max}-x_1 \choose n-1} \over {\text{max}-\text{min}+1 \choose n}}$.
For each $i=2,3,\dots,n$, pick $x_i$ from the distribution for $\Pr[X_i = x_i | X_{i-1}=x_{i-1}]$ given above.

This algorithm requires only $O(1)$ space.  The running time might be $O(n^2)$ (since it might take $O(n)$ time to draw from a  distribution with $n$ possible values).  Perhaps further analysis could reduce the running  time by finding a more efficient way to draw from  these distributions.  For instance, if you could find a way to compute the cdf (cumulative distribution function) for these distributions and evaluate it at an arbitrary $x_i$ in $O(1)$ time, then you could reduce the total running time to $O(n \log n)$ by using binary search at each step to draw from the distribution.  I don't see how to do that myself, but perhaps someone else will.

This might get a lot easier  if you are willing to draw streams of non-decreasing integers rather than a stream of  increasing integers (i.e., allow an integer to be repeated), since the formulas for probability for  drawing with replacement tend to be a lot simpler than those for drawing without replacement.


Why doesn't Knuth's linear-time multiplication algorithm "count"?

While the algorithm you mention appears in Knuth's TAOCP, it is certainly not due to Knuth, and is more widely known as the Schönhage–Strassen algorithm; Knuth even attributes this algorithm to them in the text. This algorithm indeed runs in linear time in the so-called RAM machine, in which variables are allowed to hold integers of size $O(\log n)$, where $n$ is the size of the input. The bit complexity is, however, $O(n\log n\log\log n)$, and for this model, Fürer's algorithm is faster.

The quest for fast integer multiplication algorithms in the literature has concentrated on bit complexity as the complexity measure; this is like allowing your registers to hold only one bit (or only $C$ bits for some arbitrary constant $C$). It is expected that integer multiplication takes $\Omega(n\log n)$, though it's not clear whether this should be tight, and no non-trivial lower bounds are known (so this $\Omega(n\log n)$ is just a conjecture).

For a discussion of the "correct" model for practical multiplication of large integers, check Fürer's recent paper. His conclusion is in favor of the "practical" Schönhage–Strassen algorithm (there are two of them, and the other one has better bit complexity but performs worse in practice; Fürer addresses this issue in the paper).


NP-Complete reductionTrue/False question explanation

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

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

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

Q.E.D.


Reasons for decreasing the number of threads in a parallel implementation

Some other benefits from a security point of view for running the 4 threads implementation would be :

Obfuscation of the actual processors being used by the algorithm, in case an attacker is looking to interfere with the execution.
If you have 8 processors you can run simultaneously the same algorithm twice using the same input to check the integrity of your results.


kth nearest vertex in a unweighted graph

Letting $G = (V,E)$, and $|V| = N$, your problem essentially boils down to computing a portion of the shortest path tree for every vertex in $G \setminus S$, where the shortest path tree is truncated after the $k$th "special vertex."

You mention the Floyd-Warshall algorithm; however, that algorithm seems inappropriate here, since it's designed for weighted graphs, and only returns the lengths of the shortest paths between every pair of vertices.

A more natural approach might be to run BFS on every vertex in $G \setminus S$, halting when you reach the $k$th "special vertex." Since you'd be running BFS on every vertex in $G \setminus S$, your worst-case runtime would be $O(N' \cdot |E|)$, where $N' = N - |S|$. (I'm assuming you only want the $k$th nearest special vertex for the non-special vertices.)

You would be able to improve the performance slightly by caching the portions of the shortest-path trees you compute on each call of BFS, but those changes wouldn't shift the worst-case performance. I believe any known shortest-path algorithm will have complexity dependent on $|E|$, so I'm not sure that you could solve this problem in $O(NlogN).$


Counterexample to greedy solution for set cover problem

Usually the set cover problem is formulated such that the quantity to be minimized is the number of sets one picks rather than the sum of the numbers of elements of the sets picked.
Unfortunately, this means that your example does not prove that the given greedy algorithm fails to find optimal solutions as the cover it produces consists of 3 sets, which is minimal for your instance.
A valid (and perhaps minimal?) counterexample would be $\mathcal U = \{1, 2, 3, 4, 5, 6\}$ with $\mathcal S =\{\{1, 2, 3\}, \{4, 5, 6\}, \{2, 3, 4, 5\}\}$, which works similarly to the one you found.
The minimal cover consists only of the first two sets (these two must be in every cover since there is no other way to account for $1$ and $6$ otherwise) whereas the greedy algorithm will choose the last set first (since it covers 4 rather than 3 elements) and hence picks all sets, leading to a cover of size 3 which is not optimal.


Can top SAT-solvers factor easy numbers?

There are other much simpler instances which we provably know that the current algorithms cannot solve in sub-exponential time. These algorithms are incapable of counting (almost all of them are improvements of DPLL which correspond to Resolution propositional proof system).
Unfortunately such examples are unsatisfiable instances. The question about finding  natural satisfiable hard instances for these algorithms is an interesting research problem (Russell Impagliazzo mentioned this during the proof complexity workshop last year at Banff). There are satisfiable instances that we provably know the algorithms fail badly if there is any such instance, but they are not very natural (they are based on formulas expressing the soundness of algorithms).
Regarding factoring, if the size of numbers are small (e.g. logarithmic as in your case, i.e. the numbers are given in unary), then theoretically there is no result that says there cannot be solved by current algorithms, and in fact we can write simple polynomial time algorithms that factor these numbers. So whether a particular SAT solver program can solve them might depend on the particular algorithm.


After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work.

This problem reduces to finding all chordless cycles in a planar graph.

This was one of my first thoughts early on, but this doesn't work when you consider the following:

      5-------f-------6
     /               /|
    /               / |
   e               g  |
  /               /   h
 /               /    |
1-------a-------2     7
|               |    /
|               |   /
d               b  i
|               | /
|               |/
4-------c-------3

Given three sides, the answers should be: 1 2 3 4 1, 1 5 6 2 1, and 2 6 7 3 2.  Unfortunately, 1 4 3 7 6 5 1 is considered chordless and is not a correct answer.

If you have vertices and edges - connect them. Adjacent edges will constitute a face.

Unfortunately, without weighting or accounting for spatial information you'll end up running into the edge cases described below.

Edge Cases

The highlighted "face" in the following two examples should not be in the solution.  These highlighted faces are referred to as "internal faces" (yes, even the highlighted face on the right is considered an internal face in graphics terminology).

Then there are other issues like objects with distinct subgraphs, holes, and ambiguous face loops.

The Solution

While researching I found the paper: A new algorithm for finding faces in wireframes by Peter A. C. Varley and Pedro P. Company (full text here).  The algorithm attempts to solve the problem for both 2D and 3D input.  The solution is non-trivial: the setup alone is polynomial time.

Basic Description

Start by creating a set of directed edges from all edges of the graph (so the initial set is of size 2e were e is the number of edges).  These sets of directed edges are stored as the vertices that comprise them and are referred to by the paper as "strings".  Each string must be given a priority according to the geometry around it (e.g. there will be a different priority assigned depending upon if it touches a triangle or quadrilateral).

You then exhaustively attempt to merge the strings by finding ones that start were another one ends.  You do this by picking the highest priority strings first.

When merging strings you remove the original strings from the set and add the merged version back in.  When the merge is preformed a new priority must be calculated using the existing priorities and spatial information about the strings themselves (the spatial calculation differs depending upon if your running the algorithm against 2D or 3D input).

Strings are removed from the set if their first and last vertex match (that means a loop was found).  You continue repeating the algorithm until the set is empty.

Complete Algorithm

Here is the complete algorithm copied directly from the paper.  Hopefully the description I gave above helps a bit.  The paper is very well written and its a good read for anyone interested in the topic.

Some steps in the algorithm come down to guesswork and assumptions about the input.  For example, step #3 says to "choose a trihedral vertex", but if there is no trihedral vertices (e.g. octahedron or icosahedron) then the paper suggests breaking the symmetry by assuming that an arbitrary triangular loop of edges is a face.

(Top level of algorithm)
Create initial master string list, two entries per edge
Assign priorities to all strings in the list
Choose a trihedral vertex, and concatenate two strings at this vertex
While there are strings remaining in the master list
Examine the master list for the presence of forced concatenations
    If there are forced concatenations, perform them
    Otherwise, examine the master list for the presence of voluntary mergers
    If there are voluntary mergers, perform them
    Otherwise, examine hypotheses (see subroutine below)
(Subroutine: Examine Hypotheses)
Take a working copy of the master string list
Repeat
Take the highest-priority string S in the working string list
Find the string T which has the best mating value with S
Concatenate S and T, and reduce the priority of the resulting string
Repeat
Examine the working string list for the presence of a forced concatenation
If there is a forced concatenation, perform it
    If the forced concatenation created a new face, update the master list accordingly and exit this subroutine
If there is no forced concatenation
    If there is a voluntary merger available, create the face, update the master list accordingly and exit this subroutine
    Otherwise exit this inner loop

Other Solutions

According to the paper, the current face-finding algorithms generally fall into four categories: exhaustive search approaches, pseudo-random approaches,
shortest-path approaches, and heavily mathematical approaches.  It does a good job citing other possible solutions along with their advantages and disadvantages.

Keep in mind that this algorithm acknowledges that it still produces incorrect output for certain input.  However, this is still an improvement over the previous best solution which fails for even more input.


Is it true that NEXP = EXP when the input binary strings have size O(n)?

"When the input has size $O(n)$." Unless otherwise stated, $n$ is defined to be the length of the input. So, generally speaking, the input length is just $n$, and your question is just

  Is EXP equal to NEXP?

We don't know, but we suspect not.  Nondeterminism seems to add extra power that we don't know how to simulate deterministically without requiring exponential time.

  If an language is in NEXP, then we can list all input possible input strings and then use exponential time to check each one

That doesn't make sense. In a computational decision problem, you are given an input and you must determine whether the answer is "yes" or "no" for that specific input. Enumerating other possible inputs doesn't seem helpful: if you're asked a question, your job is to answer that question, not list off all the other questions you could have been asked instead.


Given a bitonic sequence $a_1, a_2, \ldots, a_n$ , calculate the median in $O(\log n)$

First you use an algorithm to find the bitonic point, that is the point where the sequence swaps from being non-increasing to non-decreasing. This is possible with this algorithm in $O(\log(n))$. Now you split the sequence apart at this point (virtually, you don't really make any copies since that would cost $O(n)$). You can now use this algorithm to find the median of two sorted sequences in $O(\log(\min(u,v)))$. $u+v = n$ in our case since we split the original sequence.
Beware that you need to adjust the given algorithms since the first one uses the opposite definition of bitonic (first increasing the decreasing) and the second one assumes that both arrays are sorted in the same direction (in our case one is in reverse).


Why k- Vertex Cover is not in PTIME when it can be expressed in FO-logic

Your argument shows that for each fixed $k$, the problem $k$-VC can be solved in polynomial time (indeed, the algorithm enumerates all sets of size $k$ and checks whether they are vertex covers, all of which can be accomplished in $O(n^{k+1})$ or so). However, the vertex cover problem is different – it accepts $k$ as an input. This version of the vertex cover problem cannot be expressed in first-order logic.


Prerequisites for studying parametrized complexity

This shouldn't come as a surprise, but you should definitely be familiar with algorithms and datastructures as well as complexity theory.
Two fundamental text books are downloadable for free, and you can probably find the answer to your question there:

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi, Kernelization. Theory of Parameterized Preprocessing, Cambridge University Press, 2019.

But to give my own short answer:
I think knowing some recursion theory (computation theory) is of benefit, since some of the levels in the parameterized hierarchies are based directly on Turing machine theory.
Most crucial is it that you have a good understanding of the complexity classes P and NP, and how to prove that algorithms are running in polynomial time, and how to prove that some problems are NP-complete.
Parameterized complexity is a fun area, enjoy your journey!


Encoding of graphs as an input to neural nets

So I ask myself this question:

  Suppose 2 encoding contains the same amount of information, that is,
  all the information about the graph. What factor would make one
  encoding better than the other in terms of performance of neural nets
  (trained with the same number of iterations, etc)

The my personal answer to that is:

Trained neural net (in its simplest version) is just a linear function of its input. So, do you suspect that the function you want to learn can be expressed as a linear function of the input? And this is where the choice of encoding makes a difference.

My stance on these kind of algorithm is that. Ultimately, if you want it to perform well, you need to have a good hypothesis on what kind of function your answer should actually be.


An enumerator has no input. It works as follows:

Generate the next computation history.
Check if the computation history is valid.
If the computation history is valid, print the corresponding string.
Go to Step 1.

I'm unclear how your $\mathrm{TM}^E$ works. I can image the following possibilities:

On input $w$, $\mathrm{TM}^E$ enumerates all computation histories and see if $w$ matches some computation history. In this sense, there is no contradiction. $\mathrm{TM}^E$ has to endlessly enumerate computation histories if $w$ matches no computation history (i.e. $w\notin L$), so it may loop.
On input $w$, $\mathrm{TM}^E$ firstly constructs the computation history corresponding to $w$... but wait, how do you construct such a computation history while it may not even exist (i.e. $w\notin L$)?
On input $w$, $\mathrm{TM}^E$ checks whether $w$ is a valid computation history, and accepts if it is valid. In this sense, $\mathrm{TM}^E$ does not accept $L$. Instead, it accepts the language of valid computation histories. This language is different from $L$.


Why complement of most negative number in octal does not turn out to be itself

First of all, if you are considering the $n$th digit of the number as being a sign digit, you can think of it as being either 0 or 1, no matter the value of $r$. In other words, it is always a bit (a  binary digit), and that's how you would represent it in hardware, should that be the case.

  $[1]73_{\text{8's comp}} = -5$

  $[1]73_{\text{8's comp}} + [0]06_{\text{8's comp}} = [0]01_{\text{8's comp}}$

The complement of a negative number represented in $r$'s complement will obviously produce the positive version of that same number. The most negative number doesn't have a positive of the same magnitude that fits into the given number of digits (a weakness of this form of representation).

The number is still there, though, only unsigned:

  $[1]00_{\text{8's comp}} = -64_{10}$

  $100_8 = 64_{10}$


Quick note, sizeof(char) is defined to be 1. So you can just simplify to malloc(1).

The real answer however is quite boring. Your program has what's so called undefined behavior. In C (and C++), if you make an error like this the result is undefined. This could mean that your program will crash right as you trigger the bug. But it doesn't necessarily crash. It might do what you expect. It might format your hard drive and kill your cat. Whatever happens is fair game according to the C standard. Because you triggered undefined behavior.