Is there any reason why the modulo operator is denoted as %?

The earliest known use of % for modulo was in B, which was the progenitor of C, which was the ancestor (or at least godparent) of most languages that do the same, hence the operator's ubiquity.
Why did Thompson and Richie pick %? It had to be a printable ASCII character that wouldn't conflict with B's other features. % was available, and it resembles the / division operator, making it the obvious choice.
p.s. the creator of ASCII invented \ to represent "reverse division", so it wasn't a candidate for modulo.


The most basic algorithm is probably gradient gescent which can also be used for maximization. It uses the gradient of the function to optimize and (starting from an initial point) "goes" into the most promising direction. For maximization this is the direction of the gradient. Look at the examples on Wikipedia. That should give you an idea how it works. Note that in is pure variant, it always gets stuck in local optima. I don't know if there is a Java library for this. I programmed it myself some time ago, but this code is very specific to the task.

Another thing to look at is the Nelder-Mead method. It is also susceptible to local minima and requires a smooth function. It is implemented in Flanagan's Java Scientific Library. Basically you have to extend MaximizationFunction and implement the function

public double function(double[] param)

which contains your function above. This method evaluates your function given the parameters param (in your case two values: x and y) and returns the function value.

Then you can use the whole program like this:

//Create instance of Maximisation
Maximization max = new Maximization();

// Create instace of class holding function to be maximised
YourFunction funct = new YourFunction();

// initial estimates (your initial x and y)
double[] start = {100.0, 3000.0};

// initial step sizes (take a good guess)
double[] step = new double[start.length];
Arrays.fill(step, 100);

// convergence tolerance
double ftol = 0.0001;

// maximal number of iterations
int maxIter = 5000;

// Nelder and Mead maximisation procedure
max.nelderMead(funct, start, step, ftol, maxIter);

// result of maximization
double result = max.getMaximum()

Since your variables have restrictions, you should add some constraints via the addConstraint method of Maximization.


How to find the maximum independent set of a directed graph?

You are trying to find the width of the poset defined by the given subset of integers and the divisibility relation. The width is the maximum number of anti-chains, which is the same as the maximum set of incomparable elements in the poset.

This corresponds exactly to the maximum independent set in the Comparability Graph, where each integer is a vertex and there is an edge from $u$ to $v$ if and only if $u$ divides $v$.

Finding the maximum independent set in general is a hard problem, but comparability graphs are a special case for which efficient algorithms exist.

Dilworth's Theorem characterizes the width of any poset as a partition of the poset into chains (source to sink paths in the directed comparability graph). Dilworth's Theorem is equivalent toKönig's theorem on Bipartite Matching, which, as you suggested, leads to an algorithm.
The bipartite graph you construct in order to use Konig's theorem and find the maximum independent set via a bipartite matching is described simply in the above Wikipedia link. For completeness, we include it here (in annotated form):

"Define a bipartite graph $G = (U,V,E)$ where $U = V = S$ [the set of integers] and where (u,v) is an edge in $G$ when $u < v \in S$ [integer $u$ divides integer $v$]. By König's theorem, there exists a matching $M$ in $G$, and a set of vertices $C$ in $G$, such that each edge in the graph contains at least one vertex in $C$ and such that $M$ and $C$ have the same cardinality $m$.

"Let $A$ be the set of elements of S that do not correspond to any vertex in $C$; then $A$ has at least $n - m$ elements (possibly more if $C$ contains vertices corresponding to the same element on both sides of the bipartition). Let $P$ be a family of chains formed by including $x$ and $y$ in the same chain whenever there is an edge $(x,y)$ in M$; then $P$ has $n - m$ chains. Therefore, we have constructed an antichain and a partition into chains with the same cardinality."

The set of distinct vertex labels (integers) in $A$ is the answer to your question.

Section 3 of the paper Online Algorithms for Dilworth's Chain Partition by Ikiz and Garg describes two different offline algorithms to compute the chain partition, and thus the independent set you are looking for. One of the algorithms is based on the Bipartite matching method.


Construction of a counter automaton for the complement of the palindromes

If you know that $L$ can not be recognised by a $k$-DCA for any $k$, this gives the hint that you need to use nondeterminism to do it with 1 counter.

What we can do then is guess where the mismatch characters are, in particular, what we'll do is check that $x_{i} \neq y_{n-i+1}$ by using the counter to determine first that we're at position $i$ in the input (or rather, nondeterministically guessing that some $i$ is the right index to remember), then guessing nondeterministically that we've reached position $n-i+1$, checking that the two symbols at those positions are different, then counting down to check that we actually were at the right spot (i.e. the counter will have to be back to zero exactly when we reach the end of the input).

One version of this looks like:

So $s_{0}$ counts up until the symbol just before the one we're interested in. We nondeterministically guess to stop and record what symbol we see by moving to a different state, then $s_{1}$ and $s_{2}$ basically ignore the rest of the input until we guess we've reached the $(n-i+1)^{th}$ symbol, at which point we make sure it's different to the one at $i$, then $s_{3}$ counts down for the rest of the input. If there's no input left when the counter hits zero, we can move to $s_{4}$ and accept. If we move to $s_{4}$ too early, we can't accept because there's still input to be processed (so you could take some of the nondeterminism out by putting in an explicit sink state etc.), if we guessed to early which one was the mismatched symbol, then we can't reduce the counter to zero, so we can't get to $s_{4}$.


It depends on how exactly you define "starvation freedom" and "liveness."

I believe the book is talking about starvation freedom from the perspective of the OS scheduler, which usually does not know about locks managed by user processes.  So, the book is partially right (in some context).

Your definition is more broad and is what someone working in distributed systems would think (see https://en.wikipedia.org/wiki/Liveness.  Note the important assumption "All processes are assumed to correctly use the mutex...").

However, I'd think that "liveness implies starvation freedom," but there's no justification in the book for the first statement in the answer.


The conversion in each step forms REs that describe

The previous direct edge from one state to another and
the path(s) that use(s) only the removed state as an intermediate state.

In your example, the path for $aa$ goes through $q_1$, which is not removed in this step. Thus it is not added to the RE.


Does the 3SAT problems have to have consistent operators?

3SAT is a problem of deciding satisfiability of boolean formula in 3CNF form: this means that

Each clause has either exactly 3 different literals in each clause or at most 3 literals in each clause, according to different definitions.
Only $\lor$ operators can be used inside clauses (not counting varible negations).
Only $\land$ operators can be used outside clauses.

[General] SAT problem does not have a limit on number of literals in a clause and Circuit SAT allows any boolean formula.


Finding the nodes that have degree at least 3 in an undirected graph

This problem is known as a maximum $k$- core (in your case $k = 3$) and can be solved in polytime. The idea is the one you mentioned : simply delete vertex with degree less than 3 until you don't have such vertices.

More accurate description of the algorithm:

Store your graph as adjacency list. Whenever you find a vertex with degree less than $k$ mark it as deleted and then remove it from neighbors list of its neighbors. In the end you can shift indices if you really need them to be in consecutive order.


How to choose the right input(s) to test my algorithm?

If you want to automatically explore the state space of a program, you could try a fuzzer like AFL. But usually programmers do this by running the program under a debugger and thinking a bit about how the input needs to look to take a particular path through the code.


How does one know which notation of time complexity analysis to use?

You are referring to the Landau notation. They are not different symbols for the same thing but have entirely different meanings. Which one is "preferable" depends entirely on the desired statement.

$f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$, asymptotically and up to a constant factor; think of it as a $\leq$. $f \in o(g)$ is the stricter form, i.e. $<$.

$f \in \Omega(g)$ has the symmetric meaning: $f$ grows at least as fast as $g$. $\omega$ is its stricter cousin. You can see that $f \in \Omega(g)$ is equivalent to $g \in \cal{O}(f)$.

$f \in \Theta(g)$ means that $f$ grows about as fast as $g$; formally $f \in \cal{O}(g) \cap \Omega(g)$. $f \sim g$ (asymptotic equality) is its stronger form. We often mean $\Theta$ when we use $\cal{O}$.

Note how $\cal{O}(g)$ and its siblings are function classes. It is important to be very aware of this and their precise definitions -- which can differ depending on who is talking -- when doing "arithmetics" with them.

When proving things, take care to work with your precise definition. There are many definitions for Landau symbols around (all with the same basic intuition), some of which are equivalent on some sets on functions but not on others.

Suggested reading:

What are the rules for equals signs with big-O and little-o?
Sorting functions by asymptotic growth
How do O and Ω relate to worst and best case?
Nested Big O-notation
Definition of $\Theta$ for negative functions
What is the meaning of $O(m+n)$?
Is O(mn) considered "linear" or "quadratic" growth?
Sums of Landau terms revisited
What does big O mean as a term of an approximation ratio?
Any other question about asymptotics and landau-notation as exercise.

If you are interested in using Landau notation in a rigorous and sound manner, you may be interested in recent work by Rutanen et al. [1]. They formulate necessary and sufficient criteria for asymptotic notation as we use them in algorithmics, show that the common definition fails to meet them and provide a (the, in fact) workable definition.

A general definition of the O-notation for algorithm analysis by K. Rutanen et al. (2015)


a lower bound for the maximum fraction of matchings not containing an edge

Your approach has been working well all along, only to miss the promising transformation at the last step.
Instead of
$$\frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2},$$
we can proceed as
$$\frac{|E|-k}{|E|} =1 - \frac{k}{|E|} \ge1- \frac k{k+1}=\frac1{k+1}.$$
Since $k\le n$, i.e., $\dfrac1{k+1}\ge\dfrac1{n+1}$,  we are not far from the goal $\dfrac1n$.
It takes a bit more effort to reach the goal. I will leave it to you to complete.

Here is a slightly easier proof. It shows, except possibly for graphs where all edges are separated, we can increase $1/n$ to $1/2$.
Consider whether there are incident edges in $G$.

There are incident edges. Say, edge $e_1$ and $e_2$ are incident. Every matching (of size $k$) can contain at most one of them. So either at least 1/2 of the matching of size $k$ does not contain $e_1$ or  at least 1/2 of the matching of size $k$ does not contain $e_2$. Note that $$1/2\ge 1/n.$$
There are no incident edges. Then there are at most $n$ edges. Since each matching does not contain at least one of the $|E|$ edges, we have , if $e$ is the edge that is absent from the most matchings of size $k$,$$\frac{m_{ne}}{m_k}\ge \frac{1}{|E|} \ge \frac{1}{n}.$$

$\checkmark$


Efficient serialization/deserialization of huffman tree

The usual approach is to build Canonical Huffman code from the frequencies and use it to encode the data.

Canonical Huffman code can be encoded in a pretty compact way, as was described in the ZIP APPNOTE.TXT file, look for words Shannon-Fano and Huffman.

You can find C code in any deflate/inflate implementation or Huff0.


Is $L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not accept}\ 010 \} $ Turing recognizeable?

You are presenting an argument which falls short of being a proof. In particular, it is not clear why a Turing machine recognizing $L$ should know whether $M$ loops forever or not; indeed, it is not so clear what do you mean by know in this context.

Here is one way a proof could go. Suppose that $L$ were r.e. The language of Turing machines which do accept $010$ is also r.e. By running both machines in parallel, we can decide whether a given Turing machine accepts $010$, i.e., we could solve the halting problem, which we know is undecidable. Therefore $L$ cannot be r.e.


Are $BPP^{BPP^{\oplus P}}$ and $BPP^{NP}$ contained in $BPP^{\oplus P}$?

Adelman's theorem relativizes, i.e. for every oracle $O$ we have $\mathsf{BPP^O\subseteq P/Poly^O}$. To see why you have to go over the proof of Adelman's theorem. The proof goes through showing that given a probabilistic machine with exponentially low error probability, there exists a sequence of coin tosses which produces the correct answer for all (fixed length) inputs. This remains true in the relativized world, use that coin sequence as the advice, and query the oracle whenever necessary while simulating the probabilistic machine with the coins given in the advice.

Additionally, $\mathsf{BPP^{\Sigma_i}}\subseteq \Sigma_{i+3}$. Again, you have to examine the details in the proof of $\mathsf{BPP\subseteq\Sigma_2}$. Suppose $L\in\mathsf{BPP^{\Sigma_i}}$, and $M$ is an oracle probabilistic Turing machine for $L$ with exponentially low error probability. You can use the same idea from $\mathsf{BPP\subseteq\Sigma_2}$, and claim that if $x\in L$ then the set of coin sequences who lead $M$ to accept is big, and in that case it can cover $\{0,1\}^m$ with a small number of shifts, where $m=poly(|x|)$ is the amount of coins used. Similarly, if $x\notin L$ you claim that the set of accepting coin sequences is small and cannot cover $\{0,1\}^m$ with a small number of shifts. All this remains true in the relativized world, as you only reasoned about the "BPP part" of $M$, i.e how it behaves with different coin tosses depending on whether or not the input is in $L$.

What's different is that when you find yourself in need to say "some vector $r\in\{0,1\}^m$ is obtained by shifting an accepting sequence", the part verifying that a sequence is indeed accepting will add additional $i+1$ quantifiers to the formula, after the initial two who talk about space shifting. To be more clear, your final formula has the form:

"$x\in L$ iff there exist shifts such that every vector $r\in\{0,1\}^m$ is obtained by performing one of those shifts on an accepting coin sequence for $x$", this is equivalent to:

"$x\in L$ iff there exists shifts such that every vector $r\in\{0,1\}^m$ can be shifted to generate an accepting coin sequence for $x$". Saying some vector $v$ is an accepting coin sequence requires expressing "$M$ accepts $v$" where $M$ is a poly time machine with access to a $\Sigma_i$ oracle. You can express this using a $\Sigma_{i+1}$ formula (this is analogous to $\mathsf{P^{\Sigma_i}\subseteq \Sigma_{i+1}}$).

The above shows that $\mathsf{BPP^{NP}\subseteq \Sigma_4\cap P/Poly^{NP}}$.
As for your second question, I don't know if there are complete problems for $\mathsf{BPP^{\oplus P}}$, so this might make the class $\mathsf{BPP^{BPP^{\oplus P}}}$ ill defined. One interpretation is asking whether the containment holds for every oracle in that class. I doubt this is known, but no obvious important/terrible implication comes to mind. Note that disproving this containment is out of the question, as it would immediately imply $P\neq \oplus P$.


Finding a minimum equivalent graph of a digraph

This problem (or more precisely, its decision version) lies in NP, as a small enough equivalent digraph would give an NP-certificate.
What remains is to show that this problem is NP-hard.

This paper shows that finding a minimum equivalent digraph is NP-hard even when restricted to digraphs with cycles of length at most $5$, via a reduction from SAT. This means that the problem in general is NP-hard and therefore also NP-complete.


Finding whether the language is CFL or regular

Suppose there exists a CFG whose language is $L$, and let $k$ be the pumping length. Consider the string $(0^k1)^k \in L$. Then, by pumping lemma, there exists a decomposition $(0^k1)^k = uvwxy$ where $|vwx| \leq k$, $vx \neq \varepsilon$, and for each $i \geq 0$, $uv^iwx^iy \in L$. Since $|vx| \leq |vwx| \leq k$, there are four types of values of $vx$: either $vx \in 0^+$, $vx \in 0^+1$, $vx \in 10^+$, or $vx \in 0^+10^+$. Try showing that in each of these cases, pumping $vx$ gives a string not in $L$, thus giving a contradiction and demonstrating that $L$ is not context-free.


Do Self Types make the Calculus of Inductive Constructions obsolete?

I'm not an expert in this work, but it seems to me that the major current issue is a lack of SN proof, even with restrictions. These proofs are notoriously tricky though, even when the calculus is correct, so I'd give it a little time. The work is certainly very promising.

One thing to note is that these restrictions are actually quite non-trivial to express, which is a large part of the complexity of the formulation of the inductive families in the CIC. The real selling point of an approach like this would be to concisely formulate these conditions.

It's been a somewhat longstanding open problem to have a dependently typed language which is

Consistent/Normalizing
Can express all the type families from Coq (or even Agda)
Allows for a simple expression of recursion over these families
Simple or has a small number of core constructions ($\Pi,\Sigma,\mu$).

One such attempt that I know of is the Altenkirch & al $\Pi\Sigma$ language, which similarly lacks a full meta-theoretical study (and also isn't consistent without further restrictions).


Do algorithms always have a return value?

Actually, you have asked three different questions:
1) [Does algorithm always have a return value?[sic]"

The algorithm by default is not a function/method (or to say program), but it could be. Sticking to the stringent definition of the algorithm. An algorithm is a set of instruction for accomplishing a task. Every piece of code could be called an algorithm e.g. 1) defining a variable or 2) writing a logic for a loop is also an algorithm. So, addressing to your original question "Does algorithm always have a return value?" answer is 'NO'. In similar situations like 1), and 2) an algorithm does not return a value.

2) "I learned that the algorithm written in programming langauge always have a return value, not necessarily an input value.[sic]"

If you wish to convert/write your pseudo code to a specific program in some programming language e.g. C/C++. Then every program should consist of at least one function. Programming languages like C/C++/JAVA/C# etc., provides default function call Main() in which you can call user defined function(s) (or main itself).

So, reaching the end of a function other than main is equivalent to return;. reaching the end of the main function is equivalent to return 0;. reaching the end of any other value-returning function is undefined behavior, but only if the result of the function is used in an expression.

In certain languages like C/C++ there are features which allows function to defined as 'no-return' function.

#include <stdlib.h>
#include <stdio.h>
#include <stdnoreturn.h>

noreturn void stop_now(int i)
{
    if (i > 0) exit(i);
}
int main(void)
{
     puts("Preparing to stop...");
     stop_now(2);
     puts("This code is never executed.");
}

The 'noreturn' keyword appears in a function declaration and specifies that the function does not return by executing the return statement or by reaching the end of the function body. This type of adventure could be costly and can cause undefined behaviour to your C/C++ program.

P.S. When function/method have return type as 'void' they do not return any value, or anything. Control simply returns. It is also important to learn that void doesn't mean nothing. void is a type to represent nothing. That is a subtle difference : the representation is still required, even though it represents nothing.

3) "But it we use the main function with void return value, does that algorithm have a return value?[sic]"

P.S. If you define return type of main function as 'void' then it does not have any return value. You can actually omite 'return' keyword or simply type 'return' with no expression (or even 0).


Covering a directed graph with particular requirements

This problem is solvable if you have studied computer science, know standard graph problems, can spot a relationship to one of them, and then diligently study what is known about algorithms for that sort of problem.

If this immediately makes you think that it sounds related to some standard, well-known graph algorithm problem (call it Problem X), then go read about what is known about algorithms for Problem X and variants of Problem X.  You'll soon find an existing algorithm that can be adapted for this.

If you can't spot any relationship to any graph problem you already know, then you should spend more quality time studying an algorithms textbook.  Pick a good algorithms textbook and read it through cover to cover.

Alternatively: What algorithm design paradigms do you know?  For each paradigm you know of, try to find an algorithm of that type.  You should be able to find one for this.

I'm not going to say more than this.  It's your exercise, so you should have the joy of finding the answer on your own; I don't want to take away from that.  Also, practicing problem solving on your own is the best way to strengthen your problem-solving skills.  If you just read someone else's solution, you won't learn nearly as much.


is it possible to find the maximal min cut in polynomial time?

This problem is NP-hard if 0 weight is allowed. We can reduce Not-All-Equal 3SAT to the decision version of this problem.

Given an instance of Not-All-Equal 3SAT with $n$ variables and $m$ clauses, for each variable $x_i$, we create two vertices $v_i$  and $v_i'$ with an edge between them for each variable. In addition, for each clause, for example, $x_1\vee x_2\vee \neg x_3$, we add three edges among $v_1,v_2,v_3'$ (thus they form a triangle). All edges have weight 0. Now we can see there is a minimum cut (in fact, every cut is a minimum cut) with at least $n+2m$ edges if and only if the Not-All-Equal 3SAT instance is satisfiable.


Why does the concatenation operation imply the empty string?

An $\varepsilon$ transition (called the empty transition from here on out) from $A$ to $B$ means that if you end up in $A$ after a transition you can go to $B$ for free without consuming a character from the input.

When concatenating $a$ and $b$, $a$ may have multiple end states so it is easier to add an empty transition from every end state of $a$ to the start state of $b$.

You can make the rule so when you concatenate all outgoing transitions of the start state of $b$ is copied to every end state of $a$ and if the start state of $b$ is not an end state then the end states of $a$ are not end states of the concatenated NFA.

This is a much more complicated rule than: every end state of $a$ is no longer an end state and gets a new empty transition to the start state of $b$.

Adding the empty transitions does not change the language being accepted and you can do a minimization/optimization pass after constructing the NFA to eliminate the excess empty transitions.

This is actually a common practice in compilers, the early code generation is dumb and does the obvious, easy and non-optimal but correct thing. Then optimization passes look for patterns that can be simplified or optimized. This means that the pattern can be optimized everywhere even when it wasn't generated by the construct that commonly creates it.


Variant of nim game with particular rules

The following answer solves your game under normal play when there is a single heap. You can accommodate multiple heaps using Sprague–Grundy theory. Using a very similar approach, you can also handle misère rules.

You can solve combinatorial games by calculating the winning and losing positions recursively, using the following algorithm (for your special case):

for n from 0 to infinity:
   set Win[n] to True if n ≥ 1 and Win[n-1] is False
   set Win[n] to True if n ≥ 2 and Win[n-2] is False
   set Win[n] to True if n ≥ 3 and Win[n-3] is False
   otherwise, set Win[n] to False

Here are some empirical results, starting at $n=0$:

False, True, True, True, False, True, True, True, False, True, True, True

The pattern repeats, so one can conjecture that $Win[n]$ is true iff $n$ is not a multiple of 4. It is not hard to prove this guess by induction. Clearly 0 is a losing position, and 1,2,3 are winning positions since we can remove 1,2,3 (respectively) to get to 0. Now 4 is a losing position, since whatever we remove gets us to one of the winning positions 1,2,3. As before, 5,6,7 are winning positions, since we can get down to 4. And so on.

In the same way, you can compute the Sprague–Grundy function, which is $g(n) = n \bmod 4$. This allows you to solve the multiple heap version of this game.


Is there a way to predict rendering times?

You can predict it using Machine Larning / Data Mining algorithms, provided you have prior knowledge of the data. In your case,you should know the rendering time from previous experiments.

You can use any predition models. Some of them like bayesian models gives high accuracy prediction,but are computationally complex. Statistical models are very fast,but the provide less accurate results. You can use decision tree based models for a balanced performance.
CART algorithms is a good one. Use any datamining tools like weka,Rstudio or rapidminer to make the job easy.


In order to prove that $\mathsf{SPACE}(n) \not\subseteq \mathsf{NP}$, you need to identify a language in $\mathsf{SPACE}(n)$ which is not in $\mathsf{NP}$. Not every language in $\mathsf{SPACE}(n)$ would work — for example, every regular language is in $\mathsf{SPACE}(n)$, and all of these are also in $\mathsf{NP}$.

Your argument, as I understand it, is roughly as follows:

Every machine in $\mathsf{SPACE}(n)$ runs in at most exponential time.
Hence every such machine is not in $\mathsf{NP}$.

The second conclusion is not correct, since exponential time is only an upper bound. For example, a DFA uses constant space and does run in polynomial time.

Worse, even if some machine in $\mathsf{SPACE}(n)$ does run in exponential time, it could be that there exists another machine accepting the same language that runs in polynomial time — especially if we are allowed to use nondeterminism. As an example, it is suspected that $\mathsf{SAT}$ (which is in $\mathsf{SPACE}(n)$) requires exponential time, but it does belong to $\mathsf{NP}$.

The proof outlined in your link is not too hard, given the space hierarchy theorem. This theorem gives you a language $L$ which is in $\mathsf{SPACE}(n^2)$ but not in $\mathsf{SPACE}(n)$. The padded language $L' = \{ 1^{|x|^2}0x : x \in L \}$ does lie in $\mathsf{SPACE}(n)$ (why?), and so if the latter is equal to $\mathsf{NP}$, it follows that $L' \in \mathsf{NP}$. However, $L$ polytime reduces to $L'$, and so it would follow that $L \in \mathsf{NP}$ as well, contradicting $L \notin \mathsf{SPACE}(n)$.


Can we create faster sort algorithm than O(N log N)

You got a result of $O(N\cdot \log(\sqrt N)+N\log(\sqrt N))$.

But $\log \sqrt N = (\log N)/2$, so $N⋅log(\sqrt N)+N·\log(\sqrt N) = N·\log N$. So not only is it the same complexity class, where constant factors don't matter, it is even the same function, therefore the same constant factor.

But the underlying reason for any comparison based sorting algorithm to take $O(\log N)$ comparisons is that there are N! possible permutations of the array elements, each comparison can rule out at most half the possible cases, so you absolutely need at least $\log_2 N!$ comparisons in the worst case, which is $O(N\cdot  \log N)$. That $\log_2 N!$ is not a big-O, it is an absolute number. You cannot achieve for example $0.999 \log_2 N!$ comparisons in the worst case.

So you would have to come up with an algorithm that isn't based on comparison. For example, if an image contains pixels using 24 bits each, then you can sort the $N$ pixels of an image in $O(N)$ (see "The Player of Games" for reasons why you would want to sort all the pixels in a large library).


Matching two sets when you cannot do within-set comparisons

This is the so-called "nuts and bolts" problem, and your pivoting approach can be shown (under uniform choices of pivots) to give a randomized algorithm with expected query complexity $O(n \log n)$, using the analysis of Quicksort as a template.

Fast deterministic algorithms are less obvious. The first true breakthrough paper I know of for this is that of Alon et. al., which shows one simple algorithm with query complexity  $O(n^{1.5} \sqrt{\log n})$ (basically by combining the quicksort approach you describe with a moderately expensive pivot-finding procedure), and another much more involved one with complexity $O(n\,\textrm{polylog}\,n)$ (also based on quicksort, but the identification of the pivot goes through some more hardcore expander machinery).

Subsequently, Komlós et. al. found an asymptotically optimal algorithm with $O(n \log n)$ deterministic query complexity using a different approach based on sorting nets.


You might find Greenlaw, Hoover and Ruzzo's "Limits to Parallel Computation: P-Completeness Theory" interesting. It obviously goes a lot further than the limits of this question, but most pertinently includes in Appendix A a compendium of P-complete problems in the style of Garey & Johnson. There are far too many to be worth listing here, but some key ("interesting") problems are:

The Circuit Value Problem
Linear Inequalities (this is one way to get a decision version of Linear Programming)
Maximum Flow
Context-free Grammar Membership
Point Location on a Convex Hull


Why can PDAs have infinite stack but FSMs cannot have infinite state?

One of the crucial properties of a model of computation is that each automaton has a finite description. Both FSMs and PDAs have finite description. In contrast, an "infinite state machine" won't necessarily have a finite description, unless it is constrained somehow.
Also, as mentioned in the comments, an unconstrained infinite state machine can accept any language. Indeed, we can construct a machine whose states are $\Sigma^*$. We define the transition function so that after reading the word $w$, the machine is at state $w$. Thus, by choosing the accepting states, we can obtain any language, making the model uninteresting.


Defining a predicate on the structure of a string

No, in the recursive case you need to take the first symbol out of $t$, so you need at that point to unfold the structure of $t$.

Note that, as in functional programming, the functions $head$ and $tail$ should be used with great care since they are not total: $head(\epsilon)$ and $tail(\epsilon)$ are undefined. Hence, remember to require $t\neq\epsilon$ every time you use $head(t)$ or $tail(t)$, and to handle the $\epsilon$ case elsewhere.

I would tend to use your first solution, which needs a similar fix.

$$
\begin{array}{l}
{\sf pre}(\epsilon,t):= \sf true \\
{\sf pre}(\alpha.s,\epsilon):=\sf false \\
{\sf pre}(\alpha.s,\beta.t):=(\alpha=\beta)\land {\sf pre}(s,t)
\end{array}
$$

In this way you are not assuming that the second argument is non empty. You are still assuming that it is a word, but that's needed.


Why do we need increase_key procedure in max priority queue?

In some algorithms, you'll be able to remember the index.

In others, you might need a separate data structure (e.g., a hash table) that maps from the node to its index.  When you insert a node into the priority queue, you also add it to that mapping.  When you need to know a node's index (e.g.,to call increase_key), you look it up in that mapping.


$FIRST_k$ set -- is algorithm given by Aho&Ullman correct?

In your example $F_0(A) = \varnothing$ (!) while $F_0(B) = \{b\}$. Then $F_1(A) = \{ab\}$. Voila.

By construction $F_0(A) = \{ x \in\Sigma^* \mid A\to x\alpha \text{ where } |x|=k \text{ or } \alpha = \varepsilon \}$. The only production $A\to aB$ has no terminal prefix with length two, so $F_0(A)$ must be empty.

On the other hand, also the production for $B$ is shorter than two. But here we include the string $b$ as in consists of terminals only (the $\alpha=\varepsilon$ case).

As you note, $F_{i+1}(A) = F_i(A) \cup \text{ something }$, so we have $F_0(A) \subseteq F_1(A) \subseteq F_2(A) \subseteq \dots$. The sets are increasing. The construction stops when two consecutive sets are equal (for all $A$), nothing will be added after that moment.


Is it possible that the union of two undecidable languages is decidable?

Take $L_1=\{0\cdot x:x\in \Sigma^*\}\cup \{1\cdot x: x\in A_{TM}\}$ and $L_2=\{1\cdot x:x\in \Sigma^*\}\cup \{0\cdot x: x\in A_{TM}\}$. Clearly both languages are in $RE\setminus R$.

However, their union contains $\{0\cdot x\}\cup \{1\cdot x\}=\Sigma^*\setminus\{\epsilon\}$, so their union is $\Sigma^*$, and is therefore decidable.


Writing a linear program to model balanced bin packing

Define a variable $b$ that represents the imbalance between the lengths of the parking lanes.  For instance, if $b=5$, that means that the lengths of every pair of parking lanes differs by at most 5.  Define other variables to represent the lengths of the parking lanes.

Write constraints to enforce that $b$ is set consistently with your other variables.

Minimize $b$.


Complexities in this context could be divided into dynamic and static:

Dynamic complexity is an attribute of the execution of a program with the string as an input. For example, the time or space complexity of a Turing machine to accept or reject a string.
Static complexity is an attribute of a program that receives the string as input but not its execution. As you stated, Kolmogorov complexity is a static complexity since it is the length of the shortest program that creates the given string, an attribute that implies nothing about the execution of the program.


How to make Turing machine deterministic?

If a language is decided by some nondeterministic Turing machine, then it is decided by some deterministic Turing machine. However, not every behavior of a nondeterministic Turing machine can be replicated deterministically, as your example demonstrates.


Perhaps the concept will clear up if you try to solve the recurrence:

$T(n)=T(\sqrt{n})+1$.

Let $n\gt0$ which implies $\log_2n$ exists.

Let $m=\log_2n$ which implies $2^m=n$.

By the above statement and the first statement it is true that: $T(2^m)=T(2^{m/2})+1$. This is statement $A$

Define a new function $S$, such that $T(2^{\log_2n})=S(\log_2n)$.

$\implies T(2^m)=S(m)$ [By definition of $m$]

$\implies T(2^{m/2})=S(m/2)$.

By statement $A$ and above,

$S(m)=S(m/2)+1$.

Note that $m=\log_2 n$ and now we let $m$ be a perfect power of 2. Let $m=2^k$ where $k\ge0$. Also note that by imposing this restriction, we have also made $n=2^{2^{k}}$ thus $n$ is two raised a perfect power of 2.

Expanding the recurrence,

$S(m)=S(m/2)+1\implies S(m)=S(m/4)+2 \implies ....\implies S(m)=S(m/2^k)+k\implies S(m)=S(1)+k \implies S(m)=S(1)+\log_2 m.$

Now as $S(m)=T(n)$ [By definition of $S$ and $m$], we can write the last statement of the previous as follows:

$T(n)=\log_2\log_2 n+S(1)$

Again by definition of $S$, we get $S(1)=T(2)$ [Remember $S$ is a function in $m$ and $T$ is a function in $n$, but $m$ and $n$ are not independent. Infact $m$ has been defined as $\log_2 n$].

Hence we have a solution to your original recurrence,

$T(n)=\log_2\log_2 n + T(2).$

[Note that during the proof, we had restricted the values which $n$ could take up, but putting the solution back into the recurrence tells us that this solution works even when $dom(T)=\mathbb{R}^+$]


Is there such a thing as an algorithm that runs in asymptotic time?

It is not hard to see that $O(-e^{-x} +1) = O(1)$.


If you poke around the Oregon Programming Languages Summer School web site you should find a lot of video lectures on the topic, given by the leaders in the area. For instance, see Robert Harper's "Type Theory Foundations" on the curriculum page.


You can just apply the usual procedure that converts any context-free grammar (CFG) to Chomsky normal form (CNF), since a CFG in Greibach normal form (GNF) is still a CFG.

In the case of GNF, the task is, in fact, easier. All you need is to apply the following two rules repeatedly, as described by Wikipedia, until there is no nonsolitary terminals nor more than 2 nonterminals on the right-hand sides of the production rules.

Eliminate rules with nonsolitary terminals. In the case of GNF, this is used to eliminate the first terminals in the production rules.
Eliminate right-hand sides with more than 2 nonterminals.


Why does everyone say that NFA guesses it's next state?

There are many equivalent ways to describe the operation of an NFA. One is using guesses. If you don’t like it, I suggest not using it.

Guesses come up very naturally in the union construction. Suppose we are given NFAs for two languages $A,B$. We create a new NFA with a new initial state which points to the initial states of the NFAs for $A,B$, with $\epsilon$-transitions. When considering the semantics of the new NFA, it is natural to think of the NFA as first “guessing” which of the two $\epsilon$-transitions to take initially — this amounts to guessing whether the input belongs to $A$ or to $B$.

An NFA accepts a given input word if it can work its way from the initial state to an accepting state, following the input symbols and using $\epsilon$-transitions at will. Tracing the operation of the NFA, at a given point there might be many possible transitions to take, and the NFA has to choose one of them. If the input belongs to the language of the NFA, then there must exist a set of correct choices which leads the NFA to an accepting state. We refer to the process in which the NFA chooses an accepting path by the name guessing. This is a metaphor which many people find helpful, but if you don’t, feel free not to use it.


Why is the assumption in the max heapify procedure crucial to its implementation?

Heaps support several operations. Among them is the operation of extracting the maximal element. Heaps are constructed so that all supported operations have low complexity. In particular, in order for us to maintain the property that the maximal element is at the root after extracting the maximum, we need the left and right subtrees to be max-heaps as well.

There are other data structures which handle this differently, such as self-balancing binary trees, but these tend to be more complicated, and as a result slower in practice (even though they have the same asymptotic complexity).


I think the answer is yes, there is a Nash equilibrium, and it can be attained just by letting each person in turn change his selection to the best possible alternative.

For more information, read this paper:

Weighted congestion games with separable preferences

by: Igal Milchtaich

http://www.citeulike.org/user/erelsegal-halevi/article/12205199


Is it possible to submit every March Madness bracket?

The rate-limiting factor is the cost of submitting each of those $2^{63}$ combinations.  Since submitting a combination probably requires (at minimum) opening a network connection and sending the combination to a remote server, you can generate combinations a lot faster than you can submit them.  Similarly, the cost of storing the submissions is probably negligible compared to the time it takes to submit them all.

In particular, if it takes one second to submit a proposed combination, it will take you $2^{63}$ seconds to submit all $2^{63}$ of them.  That's about 21 times the age of the universe.  If it takes you one millisecond to submit a single combination, it will take you $2^{63}/1000$ seconds to submit them all -- that's about 300 million years.  Obviously, not possible within your lifetime.

Also, note that the contest rules specified a maximum of one entry per person, as well as a maximum of 15 million submissions (not 15 million per person; 15 million total -- once there have been 15 million combinations submitted, the contest closes). Consequently, your proposed strategy simply wasn't possible.  The creators weren't dumb: presumably, they thought of that and made sure it wouldn't happen.


Find subset with minimal sum under constraints

Your problem is known as minimum-weight perfect matching, and can be solved in polynomial time using several different algorithms. One algorithm that can be used is Edmonds' Blossom algorithm. See also Cook and Rohe, who discuss how to implement Blossom.


How do I reduce subset sum to another problem in NP?

Let $S, k$ be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to $k$. So it is intuitive to set $G$ to $k$ and set the lengths of the pens to be the numbers in the given set.

However, In the subset sums problem, if you found a subset that sums to $k$ the rest will sum up to a number equal to $\sum_{a \in S} a -k$ which might be not equal to k and hence might generate a problem. An easy solution is to add one number to set, namely $\sum_{a \in S} a - 2k$. And change k onto$\sum_{a \in S} a - k$. By this changes we turned the subset some problem into the two partitioning problem, where we are looking for a subset of the given set that sums up to half the sum of the elements in the setand hence, the rest of the elements have the same sum. After this step we canset the number of rows to two and the columns to the new value of $k$. Try to prove why this reduction works.


The growths could be linear or constant depending on the relationship between $m$ and $n$ as they grow large. For example, if $n$ grows with $m$ as in $m=n+1$, then $\binom{m}{n}=\binom{n+1}{n}=n+1$.
Now, if you are interested in the maximum growth, then the binomial coefficients $\binom{m}{n}$ are largest when $n$ is half of $m$. Put $m=2n$ and use Stirling's approximation for the factorial. You get
$$\binom{2n}{n}=\frac{(2n)!}{(n!)^2}\sim \frac{(2n)^{2n}e^{-2n}\sqrt{4n\pi}}{n^{2n}e^{-2n}2n\pi}=\pi^{-1/2}2^{2n}n^{-1/2}$$


Hardness and approximation of a problem with a parameter

Yes.  To show that decision problem Q is at least as hard as decision problem P (via a many-one reduction), you need to prove that a yes-instance for P maps to a yes-instance for Q, and a no-instance for P maps to a no-instance for Q.  That's just what the definition of a (many-one) reduction is.

In your case, P = "X has a solution with parameter $k'$" and Q = "H has a solution with parameter $k$".  Therefore, the answer to your question is yes: in (1) you need to prove that $X$ has no solution with parameter $k'$.  The definition of P needs to be consistent for both kinds of instances, so it has to use the same parameter in both cases.


Using the Master theorem on a recurrence with non-constant a

This is not solvable using (only) the Master Theorem. It's not in the correct form. The Master Theorem only applies when there's a constant in front of the $T(n/b)$, and $3^n$ is definitely not a constant.

You should try calculating a bound for $\log(T(n))$ instead. Even though that won't give a tight bound it will get you on the right track.


First of all, it is a bit misleading to say that $\mathsf{P} \subseteq \mathsf{\#P}$, since $\mathsf{P}$ is a class of decision problems, while $\mathsf{\#P}$ is a class of counting problems. However, we can think of a decision problem as a counting problem in which the answer is 0 (no) or 1 (yes), and in that sense it is certainly true that $\mathsf{P} \subseteq \mathsf{\#P}$.

The problem $\mathsf{\#SAT}$ is $\mathsf{\#P}$-complete. This means that for any problem $A \in \mathsf{\#P}$ there exists a polynomial time reduction $f$ such that for any instance $x$ of $A$, we have
$$ A(x) = \mathsf{\#SAT}(f(x)), $$
where $A(x)$ is the value of the counting problem $A$ on instance $x$.

Since $\mathsf{2QCNF} \in \mathsf{P}$, there is a trivial reduction from $\mathsf{2QCNF}$ to $\mathsf{\#SAT}$: if the $\mathsf{2QSAT}$ is satisfiable, we output the formula $x$, and otherwise we output the formula $x \land \lnot x$. This reduction runs in polynomial time since $\mathsf{2QCNF} \in \mathsf{P}$.


What is the origin of the client server model?

This is a good question.

It appears that the term server was commonly used already in 1960s. For example, RFC 5, which was published in 1969, already uses the term, and it seems that it was in a common use already back then.

However, the term client in this context seems to be much more recent; the earliest references that I was able to find are from 1978. The following paper seems to be the earliest hit:

Jay E. Israel et al. (1978): Separating Data From Function in a Distributed File System.

I did not find the full text of this paper. It seems that it was published in the Proceedings of the Second International Symposium on Operating Systems Theory and Practice, which was held in October 1978. A preview is available here; I am quoting the relevant part (emphasis mine):

  The distributed file system (DFS) is so named because it is implemented on a cooperating set of server computers which together create the illusion of a single, logical system. The other computers in the network that use the DFS for creating, destroying, and randomly accessing files are called its clients (we employ the term "user" to stand only for human users; programs that access the DFS are always called clients).

This looks like a good candidate of the first paper that uses the client-server terminology. Note the way it is written: the authors clearly assume that the reader is familiar with the term "server", but they are here introducing the unfamiliar term "client"—so strange that they have to justify its use.

I checked various resources, including the digital libraries of IEEE and ACM, and I was not able to find any hits that predate 1978. However, already in 1979 there was at least one paper that is boldly using the new term "client" in its title. Unsurprisingly, it is citing Israel et al. (1978).

OED knows the term, but again the earliest use is by Isreal et al.

Edit: Here are some further comments on the term "server". Looking at various papers written in 1960s, it seems that the term "server" was primarily used in the context of queueing theory; there a "server" can be any kind of entity that provides some service.

Whenever a "server computer" was mentioned in computer science papers written in 1960s, it was typically related to the applications of queueing theory in the context of computer systems. Perhaps this is the origin of the term in our field?

I am not sure what is the first instance of a "server" used in this sense without any direct connection to queueing theory.

However, RFC 5 from 1969 that I mentioned above seems to be already using the term "server" in the context of client-server systems and computer networks, without any explicit references to queueing theory. Of course the term "client" was not introduced yet, so they used the words "server-host" and "user-host".


One rational interval function and one irrational, will they ever collide?

Could you make a theoretical device that could measure an irrational number of seconds? Maybe, but that would be impossibly hard. In the real world the computers clock, which runs the scheduler, is made out of a vibrating piece of quartz creating the ticks. This is vibrating at a few billion times per second. You will never get resolution of time between the vibrations so it provides us with an implicit limit on how accurately we can measure time.


How hard would it be to state P vs. NP in a proof assistant?

I'm going to disagree with DW. I think that it is possible (although difficult) for a P vs. NP result to be stated in a proof assistant, and moreover, I wouldn't trust any supposed proofs unless they were formalized in this way, unless they came from very reputable sources.
In particular, none of the resources DW states are based on type theory, which is a very promising direction for proof assistants. Coq has been used to formalize the proof of the 4-color theorem among others, so it's clearly capable of some heavy mathematical lifting.
To answer your specific questions:

The main reason is that theorem provers aren't widely accepted in the mathematical community. Learning them takes effort, and mathematicians are often skeptical of the underlying techniques (type theory, constructive math, etc.)
But there are some fields where leading researchers are very comfortable with making large developments formalized in a proof assistant, like category theory, programming language theory, formal logic, etc. So I think there is as much of a cultural issue as an inherent feasibility issue.
The other reason is that, so far, most of the purported "proofs" have been by cranks, who don't want to formalize their result because it will inevitably reveal the flaws.

It is not hard at all to state P vs. NP in a proof assistant. One could use Turing Machines, but it would probably be easier to model a simple Turing-complete programming language using inductive families to model small-step semantics, and define the run-time as the number of steps a program takes. You could define $P$ as the languages accepted by programs halting in a polynomial number of steps, and $NP$ as languages that can be verified in polytime with a polynomial-length certificate.
EDIT: It turns out there are existing techniques for showing that algorithms run in polynomial time in a theorem prover. So this could be used either to show a polytime algorithm for an NP-hard problem, or to derive a contradiction from the existence of such an algorithm.

There is tons of software that is capable of verifying such a proof, provided the proof was written using that software. The two candidates I'd put the most stock in are Coq and Lean. Coq in particular has been used to verify several major results in mathematics.


Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that.
A list is not a natural number, and list intersection is not a function on natural numbers.
Note: it is, of course, possible to encode lists as natural numbers, which would then make list intersection a function on natural numbers. And I have no doubt that, given you chose a suitable encoding of lists, Pure Prolog will be perfectly capable of expressing list intersection.
To put it another way: just because Pure Prolog is not capable of expressing list intersection using the particular representation of lists that was chosen for General Prolog does not mean that there does not exist a representation of lists more suitable for use with Pure Prolog such that Pure Prolog is capable of expressing intersection of those particular lists.


3SAT instance with EXACTLY 3 instances of each literal

It looks like you missed the promising reformulation of this 3SAT. The simple idea is to select a different variable for each clause.
Always satisfiable
Let the variables be $V=\{v_1, v_2, \cdots, v_n\}$ and the clauses be $C=\{c_1,c_2,\cdots, c_m\}$.

Construct a bipartite graph $G=(C,V)$, where $(c,v)$ is an edge if $v$ or $\neg v$ is a literal of $c$. The given conditions mean the degree of each clause and the degree of each variable are 3.
For a subset $W$ of $C$, let $N(W)$ denote the set of all variables adjacent to some clause in $W$. Consider the edges that have one endpoint in $W$. The number of them is exactly $3|W|$ and at most $3|N(W)|$. Hence $|W|\leq |N(W)|.$ By Hall's marriage theorem, for each clause $c$, we can select a distinct variable $m(c)$ such that $(c,m(c))$ is an edge.
For all clause $c$ do the following. If $m(c)$ is a literal of $c$, set $m(c)$ to be true. Otherwise, $\neg m(c)$ is a literal $c$ and we set $m(c)$ to be false. In either case, $c$ becomes true.
Polynomial algorithm
The proof above actually gives the outline of an algorithm. Each step of the algorithm takes polynomial time. In particular, the application of Hall's marriage theorem can be implemented in polynomial time as, for example shown here.
A generalization
Here is a natural generalization.
Exercise. Generalize to the case when each variable appears in at most $r$ clauses and each clause contains at least $r$ distinct variables, where $r\ge1$.


You cannot associate the key to a value directly, since you don't know in advance the set of keys. Hash tables implement an associative array, which is indexed by arbitrary objects. A naive implementation would have a huge array, indexed by all possible values of all possible types of objects. But this is clearly not realistic. Hash tables instead use a hash function to map a key to a numeric index, which is then used to address a conventional array.

If you knew the set of keys in advance, you could implement associative arrays as arrays indexed by the keys (like your suggestion). But it is not clear how to implement this. Suppose, for example, that the keys are all 3-regular graphs on 10 vertices. Given a 3-regular graph on 10 vertices, how do you associate it to a position in your array? It's not clear how to do this efficiently. Using a hash function, however, this becomes very easy.


Why in Flow network, there is no reversed edges?

Here is your definition of reversed edges in the case of flow network given in your comment.

  Between 2 vertices there is the normal forward edge (u,v) , and another edge (v,u) that goes backward(this is the reversed edge). regardless their capacities.

If your definition is used, flow networks may have reversed edges indeed. For example, the flow network (a) in the picture below does have reversed edges between node $v_1$ and $v_2$. The two edges are usually called anti-parallel edges.

However, anti-parallel edges can be eliminated by introducing a new node and two edges having the same capacity as one of the anti-parallel edges. For example, the flow network (a) is equivalent to the flow network (b) in the above picture. Be careful that we can't simply remove the edge from $v_2$ to $v_1$ and subtract 4 from 10 to get 6 as the new capacity for the edge from $v_1$ to $v_2$ because the resulting flow network would not allow us to use only the edge from $v_2$ to $v_1$.

Flow networks without anti-parallel edges are easier to explain and process. It is not surprising if anti-parallel edges are avoided or excluded or disallowed for the sake of simplicity in many situations.

Exercise. Consider a flow network $(V,E,s,t,c)$, and let $e, e'\in E$ be anti-parallel edges. Prove that there exists a maximum flow in which at least one of $e, e'$ has no flow through it.


Why is Computer Architecture in $2^n$ bits?

Not necessarily, for instance, look at the memory bus width in modern day GPUs, they would have values of 192, 384, 768(while 128, 256.... are common).

One could argue that 192 is a sum of powers of 2 (2^7+2^6), sure, but what number isn't?

That being said, any memory modules directly associated with a microprocessor or a microcontroller will have capacities in powers of 2. Traditionally registers will be 8,16, 32 or 64 bits long (though 10-bit and other non conventional widths exist).

A processor (or controller) with an n-bit register can address upto 2^n addresses (i.e, 0-(2^n)-1 bytes). Hence without changing the processor, one can extend the memory associated with it although exceeding the addressing space beyond what the processor can manage will be redundant.

In many DSPs, the memory associated with the processor is in 2^n multiples as many of the signal processing algorithms can be made very efficient when calculating this way.


Soft question: program result verification

I found out that this is called Verifiable computing:

  Verifiable computing (or verified computation or verified computing)
  is enabling a computer to offload the computation of some function, to
  other perhaps untrusted clients, while maintaining verifiable results.


What is cold-start penalty ? What are some ways to reduce it?

"Cold start penalty" is the penalty for starting a process that has never run. The operating system has to read the code from disk, page tables have to be set up, caches filled in as instructions are executed/data fetched, and so on. If the process has run before, some of the above will already have been set up (and perhaps not fully evicted).


What is induced matching, maximum induced matching and mim-width?

Both definitions are the same. An induced matching $M$ in $G$ consists of a set of edges such that $G|_{V(M)} = M$, that is, the subgraph of $G$ induced by the vertices of $M$ is exactly $M$. This is the first definition.

Now it is always the case that $G|_{V(M)} \supseteq M$, so $M$ is an induced matching if $G|_{V(M)}$ contains no other matching, that is, $G$ contains no edge connecting vertices in two different edges of $M$. This is exactly the second definition.

I have never heard of mim-width, so it is safe to assume that it will be defined in any paper which uses it. However, it probably refers to the size (probably number of edges) of the largest induced matching in the graph.


How to find the smallest of the maximum edges of all paths between two nodes in a graph

In biref, you can just replace addition function with max function everywhere in the typical shortest path algorithm and it will work because they 'behave' the same way and that the algorithm only ever require the weight (together with the aggregation function) to have that 'behaviour'.

More specifically about that required 'behaviour' of weight.
The algorithm only require weight to be any type $\mathbb{W}$ with 'ordered monoid' structure, i.e.,
comes associated with an addition function
$$+\colon \mathbb{W} \times \mathbb{W} \rightarrow \mathbb{W}$$
and with a unique value
$$0 \in \mathbb{W}$$
such that it is associative and unital
$$(a+b)+c = a+(b+c)$$
$$0+a = a+0 = a$$
and finally with a binary (partial or total) ordering relation on $\mathbb{W}$ satisfying
$$x ≤ y \implies z+x ≤ z+y \land x+z ≤ y+z$$
You should check that the correctness proof of the shortest path algorithm only ever utilise these properties.

For fun, you could weight the edges of graph by string, add them using concatenation, have empty string be unit of concatenation, and ordered them lexicographically. Now you can find which path between 2 given points spells out the earliest word in dictionary using shortest path algorithm!


Suppose we use fourth roots of unity, which corresponds to substituting $1,i,-1,-i$ for $x$. We also use decimation-in-time rather than decimation-in-frequency in the FFT algorithm. (We also apply a bit-reversal operation seamlessly.)

In order to compute the transform of the first polynomial, we start by writing the coefficients:
$$ 3,1,0,0. $$
The Fourier transform of the even coefficients $3,0$ is $3,3$, and of the odd coefficients $1,0$ is $1,1$. (This transform is just $a,b \mapsto a+b,a-b$.) Therefore the transform of the first polynomial is
$$ 4,3+i,2,3-i. $$
This is obtained using $X_{0,2} = E_0 \pm O_0$, $X_{1,3} = E_1 \mp i O_1$. ( From twiddle factor calculation ).

Let's do the same for the second polynomial. The coefficients are
$$2,0,2,0.$$
The even coefficients $2,2$ transform to $4,0$, and the odd coefficients $0,0$ transform to $0,0$. Therefore the transform of the second polynomial is
$$ 4,0,4,0. $$

We obtain the Fourier transform of the product polynomial by multiplying the two Fourier transforms pointwise:
$$ 16, 0, 8, 0. $$
It remains to compute the inverse Fourier transform. The even coefficients $16,8$ inverse-transform to $12,4$, and the odd coefficients $0,0$ inverse-transform to $0,0$. (The inverse transform is $x,y \mapsto (x+y)/2,(x-y)/2$.) Therefore the transform of the product polynomial is
$$6,2,6,2.$$
This is obtained using $X_{0,2} = (E_0 \pm O_0)/2$, $X_{1,3} = (E_1 \mp i O_1)/2$.
We have obtained the desired answer
$$ (3 + x)(2 + 2x^2) = 6+2x+6x^2+2x^3. $$


If you restate the problem in a slightly different (but equivalent) way, an algorithm becomes more obvious:

There are $n$ parties involved: $n-1$ persons, and one restauarant.  Let $p_i$ be the amount of money party $i$ should have after the meal is finished and paid for.  For example, if Alice has \$36 and owes \$25, Bob has \$12 and owes \$11, and Carl has \$30 and owes \$25, we say that $p_0$ is the restaurant and have:

$p = (61, 11, 1, 5)$

That is, when the meal is over the restaurant should have \$61, Alice should have \$11, Bob should have \$1 and Carl should have \$5.

Now let $b$ enumerate all of the $m$ bills involved.  For example:

$b = (1, 5, 10, 20, 1, 1, 5, 5, 10, 20)$

The denominations of the bills do not matter, but I have chosen denominations of paper US currency for this example because they are familiar.

We are seeking to minimize the number of bills that change hands, so we associate a "cost" with person $i$ leaving with bill $j$ by using a $\{0,1\}$ matrix $C$.  Entries of 0 in this matrix indicate which bills each party starts with ($C_{0,j} = 0$ for all $j$ because the restaurant starts with no bills).

Continuing our example:

$$
C = \left[ \begin{array}{cccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
\end{array}
\right]
$$

indicates that Alice started with \$1, \$5, \$10, \$20, Bob started with \$1, \$1, \$5, \$5, and Carl started with \$10 and \$20.

Again, the goal is to minimize the number of bills that change hands.  In other words:

$$
\begin{align}
\text{Minimize:} & \sum_{i=0}^{n-1}{\sum_{j=0}^{m-1}{C_{i,j} x_{i,j}}} \\
\text{subject to:} & \sum_{i=0}^{n-1}{x_{i,j}} = 1  \text{ for } 0 \le j \lt m, \\
& \sum_{j=0}^{m-1}{x_{i,j}b_j = p_i} \text{ for } 0 \le i \lt n, \\
\text{and} & x_{i,j} \ge 0
\end{align}
$$

The first constraint says that the solution can only assign a particular bill to one party, and the second ensures that everyone pays the appropriate amount.

This is the 0,1 INTEGER PROGRAMMING problem and is NP-complete (see [Karp 1972]).  The Wikipedia page about linear programming has information on different algorithms that can be used for these types of problems.

There are potentially multiple optimal solutions; by hand the first solution to the example I came up with was:

$$
x = \left[ \begin{array}{cccccccccc}
0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
\end{array}
\right]
$$

which means Alice pays exactly \$5 and \$20, Bob pays exactly \$1, \$5 and \$5, and Carl overpays \$10 and \$20 and then removes a \$5 from the table.

I also used the Mixed Integer Linear Program module of the Sage Math system which has the ability to use different solver backends (GLPK, COIN, CPLEX, or Gurobi).  The first solution it gave was

$$
x = \left[ \begin{array}{cccccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
\end{array}
\right]
$$

which is almost the same except that Carl took the "other" $5 that Bob put on the table.

Formulating the problem in this way satisfies all the properties you list (you can extrapolate which bills end up where from $C$ and the solution matrix $x$).  The exception is perhaps #4 which was discussed in the comments of the question.  It is not clear to me what you would like to do in the situation that there is no feasible solution to the set of linear equations:

Identify a subset of people that can pay the reduced total?  Or perhaps a subset of people which could still pay the entire bill, i.e. they pay for their friend.

Your final statement makes it seem like you are interested in the case that the denominations of the bills are fixed, this doesn't change the problem however.

In any case, there is also an $O(1)$ solution in which every person pays with a credit card.


Transitive reduction of rectangle containment hierarchy DAG

Dec. 14, 2018

Standard approach and a heuristic alternative

Standard approach -- use graph and distance product

We note that transitive reduction is reduceable to transitive closure and vice versa both in additional time in $O(n ^ 2)$. Then, we know that if we can solve transitive closure in $O(n ^ 2 \cdot \textrm{polylog}(n))$ time, then we can also solve lax Boolean matrix multiplication (MM) in similar time by reducing it to transitive closure (or transitive reduction), according to Fischer/Meyer 1971. Lax Boolean MM is where input values are in $\{0, 1\}$ and we have semi-ring of $(\textrm{OR}, \textrm{AND})$. We can solve lax Boolean MM by reducing to standard (plus, times) MM. This means that significantly-subcubic-time approach is currently unlikely for transitive reduction. We can reduce node-based DAG transitive reduction to rectangle-containment-based DAG transitive reduction via topological ordering and shapes that have size inversely related to distance from source. For rectangle application, we should of course not have cycles, which happen when the rectangles are identical, in which case we should remove duplicates. A more direct algorithm is for computing reduction assuming sparse graph, which takes $O(n ^ 3)$ time. These times are also ignoring that to come up with initial DAG we ought to perform $n ^ 2$ containment tests, each of which takes time in $O(d) = O(2) = O(1)$.

Heuristic alternative -- use R-tree

Alternatively, assuming we have dimension $d$ moderately low and fixed and not bound tightly by $O(n)$, we can arrive at times that appear to be subcubic in $n$. We have two options -- both use an R-tree variant with bulk-loading e.g. via sort-tile-recursive (STR) approach via Leutenegger 1997 and that is balanced and that is dynamic via bkd-tree-like occasional rebuilding (see Procopiuc 2003) to support inserts and deletes in $O(\log^2(n))$ time. See Guttman 1984 for details on standard R-tree. The main idea is that we find close descendants for each of $n$ provided rectangles via a total of $n$ close-descendant queries. We consider both options to involve heuristics because we may have many intermediate hunches for close-descendant that do not ultimately survive, even though subqueries have good guaranteed time for option one.

If we have pair-wise rectangles that do not frequently involve enclosure/containment and overlap is highly correlated with enclosure/containment, then it is conceivable that we can get better performance using R-tree via either of the two options for our approach. We note that a rectangle enclosure query asks for given a query rectangle rectangles that contain it and a rectangle containment query asks for given a query rectangle rectangles that fit in it. Close-descendant query roughly works via a heuristic approach. We find primitive rectangles contained by query rectangle and use auxiliary queries to see if returned rectangles have parents that are contained by original query rectangle. The candidate close descendants we store in a "conflict" secondary R-tree for purpose of speeding up checks in form of enclosure subquery with early-stopping that determine whether a candidate parent encloses (and disqualifies) a candidate close descendant; we maintain this conflict tree via inserts and deletes. We note that when we encounter rectangles of same shape, we may choose to keep one of them arbitrarily. We use a best-first priority queue to guide bounding box consideration order; we prefer contained bounding boxes and we tie-break by preferring larger bounding box area (because it is harder to be a middle-man for a larger contained box).

Option #1 -- use look-ahead

The first option is to use look-ahead for subqueries such as rectangle enclosure and rectangle containment in conjunction with corner transformation. Close-descendant query would then not directly use look-ahead; its subqueries do. Then, we have a coefficient of $d$ for look-ahead-using queries for edge checks. We won't go into much detail about look-ahead except that it requires roughly disjoint bounding boxes for siblings (though shared edge is allowed) and that it is related to knowing that one child out of two subtrees definitely has a match (which is made more straightforward to notice assuming we also use corner transformation) via $d$ edge checks at each node. It should be noted that without look-ahead enclosure and containment already take at least $d$ time for each node for an R-tree. We modify enclosure subquery to use early-stopping, which leads time for such a query to be $O(\log(n))$ instead of $O(\log^2(n))$. Time for each close-descendant query is in $O(k \cdot \log^2(n))$, where $k$ is number of hunch close-descendants s.t. $k$ is in $O(n)$. This means for $n$ close-descendant queries overall we take time in $O(k \cdot n \cdot \log^2(n))$ = $O(n ^ 2 \cdot \log^2(n))$. Since this is less than cubic in $n$ (though we omit a factor of $d$ assuming it is moderately low and fixed), this approach may be used to get better performance in practice. We have left out detail that for look-ahead-using enclosure/containment subqueries we may take non-constant time even if there are zero matches.

Option #2 -- do not use look-ahead

The second option is to not use look-ahead and all we can say (without further simplifying assumptions) is that for each close-descendant query we have worst case of $n$ hunches, each of which would then take $O(\log(n))$ time to find (because we don't go down a branch more than once). We note that we assume that we do not use corner transformation. As a result, we have an exceedingly loose and pessimistic time bound of $O(n \cdot \log(n))$ for attempt to disqualify a hunch close descendant via enclosure subquery with early-stopping. Time for a close-descendant query then is bounded by $O(k' \cdot n \cdot \log(n))$, where $k'$ is worst-case number of hunches (i.e. $n$). Time for $n$ close-descendant queries then is bounded by $O(k' \cdot n ^ 2 \cdot \log(n))$ = $O(n ^ 3 \cdot \log(n))$. This figure is more than cubic in $n$ (again noting that we omit a factor of $d$ as it is moderately low and fixed), but the times for the approach are considerably pessimistic and we believe there is still a chance that it can perform well in practice w.r.t. brute-force. We show that this is plausible by now making a few assumptions, which we discuss below. While the first option does not take advantage of possibility that number of hunches can be significantly lower than $n$ either, it has lower theoretical bounds because they take advantage of possibility that enclosure subquery with early-stopping for disqualifying a hunch close descendant can be guaranteed to be fast.

Option #2 -- three assumptions

Assumption "zero-overlap" says that (i) bounding boxes do not overlap with query rectangle unless we enclose query rectangle for enclosure query or we are contained by query rectangle for containment query; and (ii) bounding boxes for siblings s.t. neither sibling is contained in the other do not overlap except at a boundary. We note that part one of that assumption can only mostly be true e.g. because a real rectangle collection has a largest rectangle that cannot be enclosed and a smallest rectangle that cannot contain. We introduce $b$, which describes average false-positive-to-actual-positive ratio for believing that a child for a node is associated with a guaranteed match during disqualify attempt subquery s.t. $b$ is in $[0, 1]$. Time for second option close-descendant query is broken into two parts. The first part describes getting the hunches. The second part describes attempts to disqualify each hunch. The third part is to handle updates to conflict tree. Assume number of hunches is $k''$. The time for the first part is $O(k'' \cdot \log(n))$. The time for the second part is $O(k'' \cdot (b + 1)^{\log(n)} \cdot \log(n))$. The time for the third part is $O(k'' \cdot \log^2(n))$. The total time is loosely (assuming $b$ is one) in $O(k'' \cdot n \cdot \log^2(n))$. The time for $n$ close-descendant queries is $O(k'' \cdot n ^ 2 \cdot \log^2(n))$ = $O(n ^ 3 \cdot \log^2(n))$ if $k''$ is in $O(n)$. This does not appear to be better than brute-force. If we make "zero-overlap" assumption, $b$ is zero, which gives $n$ close-descendant query time of $O(k'' \cdot n \cdot \log^2(n))$ = $O(n ^ 2 \cdot \log^2(n))$ if $k''$ is in $O(n)$. The factor of $\log^2(n)$ (instead of $\log(n)$) comes from insert/delete for conflict tree of hunch close descendants. This assumption can be true for rectangles for a hierarchy that is highly coherent -- i.e. one with many realized enclosure/containment relationships and good separation between rectangles that are not related via enclosure/containment.

We have two other assumptions -- "uniform sparsity" and "no pruning", each of which have secondary purposes that are related to our application of quantitative association rule mining. They allow us to tune to reduce work drastically given that the second option for close-descendant query can be very time-costly. Specifically, say average number of partitions for a quantitative attribute (treating categorical attribute as possibly multiple two-partition quantitative attributes) is $p$; then, number of solid regions considered for each quantitative attribute is $p ^ 2$ -- all of which survive if we have "no pruning" assumption. As we reduce $p$, the space of all possible multi-dimensional rectangles shrinks and via "uniform sparsity" assumption for fixed $n$ we have more collisions (i.e. possibly more enclosure/contain relationships) but number of rectangles (that are made of combinations of solid regions for different attributes) shrinks faster -- this means that w.r.t. close-descendant query the amount of time required we can drastically shrink by reducing average number of partitions $p$ slightly.

Miscellaneous shared details

The only reason we believe one might wish to not use option one is slightly more implementation difficulty. We don't often see a proposed algorithm that performs reporting and that has for each match a coefficient for time that is not one. Still, the coefficient that we have of $\log(n)$ or $\log^2(n)$ is fine; $\log^q(n)$ for low $q$ is often acceptable wherever we see $O(1)$, as opposed to when we have e.g. $n$ where we see $O(1)$. In general, an R-tree is better than multi-layer segment tree for rectangle enclosure/containment/intersection queries or point domination query if $d$ is less than $\log^{max(d - 1, 1)}(n)$ for $d \geq 1$ given that for an R-tree we do not clone stored rectangles. Option one and option two with assumptions imply that we appear to be better than brute-force given that it is appropriate to omit $d$.

References

Pratyaksh - Transitive reduction of DAG - Answer (2014)
https://cs.stackexchange.com/q/29133
Wikipedia - Transitive reduction - Computing the reduction in sparse graphs
https://en.wikipedia.org/wiki/Transitive_reduction
Fischer, Meyer - Boolean matrix multiplication and transitive closure (1971)
Leutenegger et al. - STR: A simple and efficient algorithm for R-tree packing (1997)
Procopiuc et al. - Bkd-tree: A dynamic scalable kd-tree (2003)
Guttman - R-trees: A dynamic index structure for spatial searching (1984)


A graph in descriptive complexity - is $x$ already a vertex?

(First-order logic) formulae are independent of structures; you just have variables, predicates and possibly functions (in addition to the syntactical symbols). To decide whether a formula $\varphi$ is true in a given structure $S$ (consisting of a universe of individuals $U$ and an interpretation of predicates $I$), i.e. whether $S$ is a model of $\varphi$, you apply the semantic rules of first order logic.

Concerning your specific question: if you have $\varphi = \forall x: F$ where $F$ is some formula, then $x$ denotes exactly all vertices iff you defined your structure $S = (U,I)$ such that $U$ contains exactly all vertices. Note that if you do that and want access to the edges, then you'll need to define some predicate $e(x,y)$ such that $e(x,y) \Leftrightarrow \text{there is an edge between } x \text{ and } y$.

More generally: the quantifiers do not differentiate between elements of your universe, the predicates will have to do that. If you want to check $F$ only for all vertices but your universe contains elements that are not vertices, then you do what you suggested: introduce a predicate $v(x)$ and use $\varphi' = \forall x: (v(x) \rightarrow F)$


How to do binary search on a path in a binary heap

Note that a path from the root to $heap[i]$ is in the sorted order. Moreover, the path length is $O(\log n)$. You just need to do binary search on this path. For that, you need to access the $i^{th}$ ancestor of any node in the heap in $O(1)$ time. Assuming $1$ based indexing, the $1^{st}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{2} \rfloor$ location in the array. The $2^{nd}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{4} \rfloor$ location, and so on. Using it you can easily perform binary search on the path from root to $heap[i]$ in $O(\log \log n)$ time.
Pseudocode:
Assume that we have a min heap. Initialize, start = $1$ and end =  $h = \lfloor \log(i) \rfloor$
BinarySerach (start, end)

mid = (start + end)/2
index of mid = i/(2^(h- mid)) //(h-mid)^th ancestor of i

if (end-start = 1)
    if (heap[index of mid] == x) return "YES"; otherwise "NO".

if (heap[index of mid] >= x)
   return BinarySearch (start, mid)
else
   return BinarySearch (mid+1,end)


Relationship between message entropy and complexity of the best algorithm

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

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


Map overlay, any algorithm for face updating step?

Before we 'fill in' the value for the new faces at the halfedges,  we wait until the rest of the algorithm is finished, so we know which faces are still present in the end and only have to traverse every edge once. We do this by getting the halfedge that we have considered as a 'representative' and traverse the proper cycle until we return at our edge. So, our complexity is bounded by the sum of the faces and the edges, instead of their product, giving $O(n)$ instead of $O(n^2)$.

That book tends to ignore the subtleties that arise in dealing with DCELs. At first, it seems strange that updating faces would take only $O(n)$ time, since the face of the edge would get updated multiple times. Here, $n$ is 'the complexity of the subdivision', i.e. the sum of the edges and faces of the DECL.

However, since we only want to store the final face value at the end, we wait with the updating the face values of the half-edges until we have filled in everything else. We can store the new value at only one half-edge, which will be the 'representative' of that face and maintain a list of those half-edges.

Then, at the final step, we fill in the face values for the cycles of the stored representative edges, by traversing the cycle associated with the half-edge until we return to the edge where we started and remove a (different) representative if we encounter it, since this means that the face it belonged to no longer exists. By doing so for every representative in the correct order (i.e. from the last created face to the first), we avoid traversing cycles for faces that do not occur in the final DECL. So, we are able to check every face and visit all edges after that, which means we get the required complexity of $O(n)$.


Randomized Algorithms: High-Probability vs. Expectation

If you have an algorithm that is an $\alpha$-approximation in expectation, then you can construct an algorithm that is a $(1+\epsilon)\alpha$-approximation with high probability, for any $\epsilon>0$.  In particular, by Markov's inequality, if you run the algorithm, then with probability at least $1-1/(1+\epsilon)$ it will output a $(1+\epsilon)\alpha$-approximation.  So, if you run the algorithm about $(c \log n)/\epsilon$ times and keep the best output among all of those trials, with probability about $1-1/n^c$ you will find a $(1+\epsilon)\alpha$-approximation.
If you have an algorithm that is an $\alpha$-approximation with high probability, there are no guarantees about the expectation.  It's possible that with very small probability (probability $1/n^c$), it outputs an extremely bad solution (one with exponentially large approximation factor), and in all other cases it outputs an $\alpha$-approximation.  In this case, the expected value of the approximation factor will be very large, even though it has a very small probability to output such a bad solution.


You can calculate $b^k \bmod P$ efficiently for $k \geq 0$ using repeated squaring. There is no need to know the factorization of $P$. Furthermore, you can calculate $b^{-1} \bmod P$ (if it exists) efficiently using the Euclidean algorithm. This also doesn't require the factorization of $P$.


A language $A$ Turing-reduces to $\overline{A}$ since a Turing machine with an $\overline{A}$-oracle can compute $A$. On input $x$, it determines whether $x \in \overline{A}$ using the oracle, and then outputs the reverse answer.


So, the answer is arguably "yes," this is an example of dependent types. However, the problem with a lot of simple examples that people create for this is that they don't demonstrate non-trivial aspects of dependent typing.
Arguably yours is better in this respect, because the type in question depends on an arbitrary value in MemorySlabCache. However, you never use a MemorySlabCache without a statically known value. So a more interesting example would be like:
let cacheSize = readInteger(stdin)
store.caches.push(new MemorySlabCache(cacheSize))

So, you allow the user to select a cache size at runtime, but the cache size is still recorded in the type, and the type checker statically ensures that all operations make sense with respect to the size, even though the size is not statically known (which is kind of another problem with your example; nothing in it shows how the tracked size matters subsequently).
A somewhat more minor problem is that integers are too easy a structure to 'fake' dependent types for, so examples with them end up under selling what might be feasible with genuine dependent types. For instance, Haskell with some extensions can encode even something similar to my runtime-cache-size example, even though it does not really have dependent types. You can have statically known type-level integers, and create a function that gives you back an appropriate value for a statically typed value based on a runtime integer. However, languages based on dependent type theory generally let types depend on values of arbitrary types, like function types. For these (and other related features), 'faking' is not really feasible.


As already indicated in the comments, the wikipedia article about Sparse matrix, Band matrix, and Skyline matrix cover the topic of the question quite well. Also, the computational science stackexchange site might be a better fit for such questions in general.

One might perhaps add that band matrices can't handle low rank modifications directly, so that one might want to use the Sherman–Morrison–Woodbury formula in this case. For the other representations, it is normally more beneficial to incorporate low rank modifications directly into the matrix via additional rows and columns, see below.

Some information about representations of Sparse matrices

A general Sparse matrix can be represented as a bipartite graph. This representation is useful for applying combinatorial algorithms like the Dulmage-Mendelsohn decomposition during preprocessing. In this case however, it is likely that you actually have a matrix pencil $A+\epsilon B$, which is important to know for the combinatorial algorithm, because this indicates which elements are expected to be small. A quick'n dirty fix is to apply the combinatorial algorithm to a related block Toeplitz matrix like $\begin{bmatrix}A\\B&A\end{bmatrix}$ or $\begin{bmatrix}A\\B&A\\&B&A\end{bmatrix}$ instead, but this is starting to get off-topic now.

If a "fixed" mapping between rows and columns is available, it makes sense to specify the symmetry type of the matrix as "general", "symmetric", "skew-symmetric" or, "Hermitian". If the symmetry type is more specialized than "general", then the matrix can be represented by a undirected graph, otherwise a directed graph can be used.

Note that these representations also apply to block-matrices (i.e. both the row indices and the column indices are partitioned into subsets), and encoding some a-priory information into such a block-structure can be a good idea both for speed and robustness.

I could also explain here how low rank modifications fit into such a general framework, but this section is already quite long. Often one can incorporate low rank modifications by just adding the corresponding row and column vectors as additional rows and columns with a small identity matrix between them. The advantage here is that the sparsity pattern of the original matrix is preserved.


Your function is computable. Just run the input machine on the empty input for $B(10^{1000})$ steps. Note that $B(10^{1000})$ is just a constant which can be hardcoded into your code.


The notion of PAC in approximation algorithms

Approximation algorithms don't make sense here, because here the output of the algorithm is 0 or 1.  (0 represents "the input is not in $L$", 1 represents "the input is in $L$".)  Approximation algorithms are useful when the output is a continuous variable, as then we can ask for the algorithm to output something that is close to the correct answer, but the concept is not useful when talking about algorithms that output a boolean.

Also, in your proposed definition, once you have fixed an algorithm $A$ and a distribution $D$ over $L$, the condition $ERR(A,D) \le \epsilon$ is either true or false.  It's not an event that you can assign a probability to.  So, it doesn't make sense to ask it to hold with probability at least $1-\delta$.


Dynamic Programming vs Greedy - coin change problem

A dynamic approach would say that "x$ can be made out of change using, as the first coin, v1 or v2 or v3 ... or vn" and then build a table so that the second coin would be v1 or v2 or v3 ... or vn + one of the precomputed values. Here is a link talking about dynamic: http://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change

Greedy choice however uses the fact that, for many currencies, we simply can take the maximum value that still gives us less than then our amount and ignore all other possibilities. However, greedy doesn't work for all currencies.

For example:
V = {1, 3, 4} and making change for 6:
Greedy gives 4 + 1 + 1 = 3
Dynamic gives 3 + 3 = 2

Therefore, greedy algorithms are a subset of dynamic programming. Technically greedy algorithms require optimal substructure AND the greedy choice while dynamic programming only requires optimal substructure.


Any problem solved by a finite automaton is in P

Yes, it is true. In terms of complexity classes,
$$
\text{REG} \subseteq \text{P},
$$
where $\text{REG}$ is the class of regular languages (i.e., problems that can be solved by a finite automaton). More specifically,
$$
\text{REG} \subseteq \text{DTIME}(n), \tag{*}
$$
and $\text{DTIME}(n)$ is a strict subset of $\text{P}$ by the time hierarchy theorem.

The proof of (*) is as follows: for any problem in $\text{REG}$, there is a DFA which solves it. Convert that DFA to a Turing machine with the same states and transition function, which always moves to the right until it sees a blank, and then accepts or rejects. This Turing machine always halts in time exactly $n$.

It's also worth mentioning that $$
\text{REG} = \text{DSPACE}(0) = \text{DSPACE}(k)$$
for any fixed constant $k$.


Why is the language of TMs that have some quadratic time bound undecidable?

The fundamental reason for this is because your function $100n^2+200$ is $\Omega(n)$. Additionally, this result holds for any function $f\in\Omega(n)$.

Your problem is that you can't just "run $M_n$". It's possible to describe a turing machine that runs a specific machine, but to have the turing machine depend on the input requires that you actually compute the machine you're using. This is actually equivalent to the negation of what you are trying to prove, and additionally makes $M$ take longer so that it won't halt in the correct amount of time in the case that $M_n$ does even if you had an algorithm to find $M_n$.

Assuming you are using $M$ in your second attempt as a general TM rather than the one for attempt one, then the problem here is the same (except it's caused by the fact that the machine has to use some extra time to compute which step it's one rather than compute the machine it will simulate). Normally, this problem wouldn't come into play if you do $O(f(n))$ analysis because your new TM $M'$ would still run within a constant time factor of the old one, but in your problem you have to be a bit more clever.

If you know a bit of complexity theory, you can do that by using the linear speedup theorem, which basically says that given a TM which runs in at least linear time $f(n)$ you can create one with a constant factor $r>0$ as small as you'd like that runs in time $r\cdot f(n)$. The drawback is that the tape input is no longer just $0$'s and $1$'s but will also include some added symbols, but the same methods can prove this for any $f\in\Omega(n)$, so it's still a pretty neat result.


Computer science is, at its core, the study of algorithms. What can we compute, and how fast can we compute it? Its sub-fields, such as image processing, AI, Operating Systems, Programming Languages, numerical computing, etc. can be viewed as answering these questions for specific types of problems.

With that in mind, I think the most major revolution is:

Godel/Turing and Undecidability

The mathematician Hilbert posed a series of problems to the mathematical community. One was to find an algorithm for the Decision problem: that is, to look at any theorem, and state whether it was true or false.

In different ways, Godel and Turing each proved that this was impossible. This revolutionized the way we thought about computation, because for the first time, we had a definitive proof that something could not be computed. No amount of human cleverness could completely solve the problem.

Directly related to this, Turing Machines and the Church-Turing thesis were developed. This formalized what it meant to compute, turned algorithms from things humans talked about into mathematical objects that could be reasoned about, have theorems proved about them. And it established that the two extreme ways of thinking of computation, namely as functions and as transformation of an infinite memory, were equivalent.


Traversals from the root in AVL trees and Red Black Trees

For virtually all kinds of binary search trees, including AVL trees and red-black trees, you can implement insertion in what is called a bottom-up fashion.  This involves two passes through the tree: the first pass starting at the root and moving down the tree to find the right place to do the insertion, and the second pass starting at the insertion point and moving upward toward the root fixing the tree as necessary.  Frequently, these two passes are implemented as one recursive function, where the first pass is going down the recursion, and the second pass is coming back out of the recursion.

For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to the tree can fairly easily be predicted on the way down and performed during a single top-down pass, making the second pass unnecessary.  Such insertion algorithms are typically implemented with a loop rather than recursion, and often run slightly faster in practice than their two-pass counterparts.

Note that, for trees like red-black trees, where you can implement insertion either way, the two different approaches (bottom-up/two-pass vs top-down/one-pass) do not necessarily yield exactly the same tree, but will yield trees that are equivalent.  For example, the exact pattern of red and black nodes may vary slightly, but will still obey all the expected invariants of a red-black tree.


Find the central point in a metric-space point set, in less than $O(n^2)$?

No.  You can't do better than $\Theta(n^2)$ in the worst case.

Consider an arrangement of points where every pair of points are at distance $1$ from each other.  (This is a possible configuration.)  Then you can't do better than to examine every edge.  In particular, if there is any edge you have not examined, then an adversary could choose the length of that edge to be either $0.9$, $1.0$, or $1.1$; all of those choices are consistent with all of the other observations you've made and with the requirements of a metric (e.g., with the triangle inequality), so all three are possible; but they require different outputs.  Thus, if your algorithm doesn't examine that edge and then outputs something, an adversary can always choose a length for the unexamined edge that will make your algorithm's output wrong.

However, if you know that all the points live in $\mathbb{R}^d$ (even though you are not given their coordinates), then the problem can be solved by  measuring $O((d+1)n)$ distances, assuming no degeneracies (no subset of $d+1$ points are co-planar).

In particular, pick $d+1$ points randomly.  These will be anchor points.  Given their pairwise distances, you can compute coordinates for them that are consistent with their pairwise distances.  Now, for every other point $P$, compute the distance from $P$ to each of the anchor points.  Using triangulation and these distances, you can compute the location of $P$ relative to the anchor points and thus the coordinates for $P$.  Do this for every non-anchor point $P$.  Now you have coordinates for every point, and you can use those coordinates to find the central point without asking the oracle to give you any more pairwise distances.  I don't know whether this last step can be done faster than $O(n^2)$ time, but it can be done without measuring any more pairwise distances.


If a user confirmed a booking or transaction on the database system, but it failed and it falls over to the replica, what if the transaction is lost?

There is no single answer that is always used; there is a tradeoff between consistency, availability, and ability to handle failures.  Most databases ensure that the data is stored persistently on disk before reporting that the transaction is confirmed, so even if the main database fails, if it has accepted the data, then the data will be there on disk.
Of course you could avoid committing until both replicas have confirmed, but then the system would not be available if either replica cannot be reached; or you could continue as soon as the master has accepted the data, but then the secondary replica could become out of sync.  I suggest learning about the CAP theorem and fundamental tradeoffs in database systems.
There will always be some failures that we cannot or do not prevent through technical means.  So, they might be addressed by ad-hoc methods (e.g., the customer could call customer support).


Any known plaintext attack instantly reveals the key:
$$f_k(x) - x + 2^n \equiv k^2\mod 2^n$$

On top of that, even without knowing the key or the plaintext, here's a property that no random function should have:

$$f_k(x + 1) \equiv f_k(x) + 1 \mod 2^n$$


Machine has 64 bit architecture and two word long instruction

A "64 bit architecture" with 32 bit registers is a bit unusual.

Taking the numbers at face value, a 2-word instruction is 128 bit long, you need 6 bit to encode the instruction, 2x7 bits to specify two registers, leaving 108 bits for an "immediate" operand. The maximum value in the "immediate" operand is $2^{107}-1$.

That's answering the question that you asked. What your instructor actually asked, and what he intended to ask, and what he thinks he asked, and what answer he wants to hear, nobody can know that.