Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

I would suggest using the A* algorithm.  The state is where each player is currently seating and the number of pieces you've played so far.  Each edge represents a way that you can update the seating.  Also, when you're in a state where, for the next piece to be played, everyone is sitting next to their partner on that piece, you can increment the number of pieces played at 0 cost.   The start state has 0 pieces played, and the goal state is any state where you've played all the pieces.   Then, A* will find the lowest-cost sequence of movements to complete the concern.

You'll need an admissible heuristic to estimate the cost to finish the concert, starting from a particular intermediate state.   One very simple heuristic is: count the number of players who will have some future piece to play, where they're not currently sitting next to their partner on that piece, and divide by two.  Perhaps a slightly better heuristic is to count, for each player, the number of future partners (for any piece not yet played) who they are not currently sitting next to, and divide by four.  Assuming each switch costs one and there is no other way to update the seating, this is admissible, as each switch can only decrease this count by at most four.


The gibbs phase rule is simply a way of determining whether the system of equations which describes the system will be overdetermined.
As we are talking about (usually) solids, this system of equations looks like $K=A^nB^m...$
If we take the log of both sides, this can be simplified to $\log{k}=n\log{A}+m\log{B}...$.
If we substitute $a=\log{A}, b=\log{B}$ then this becomes a system of linear equations $\log{k}=n*a+m*b...$
Now we can represent this system of linear of equations as a coefficient matrix and then use the Rouche Cappeli Theorem to determine whether the system is overdetermined. Since each species each unique in your system, you simply need to determine if there are any rank deficiencies in your coefficient matrix.
In the first example: {[0, 1, 2], [0, 2], [1, 2]} can be represented as the matrix
$$\begin{bmatrix}
1 & 1 & 1\\
1 & 0 & 1\\
0 & 1 & 1\\
0 & 1 & 0
\end{bmatrix}$$
Which has a rank deficiency, therefore is overdetermined.


Closure properties of Alternating Circuit 1 level

Denote your language by $L$. Let the input be $x_1,\ldots,x_n$. Let $f(i,j,\ell)$ be true if $x_1,\ldots,x_j \in L^\ell$. The output will be
$$
\bigvee_{\ell=1}^n f(1,n,\ell).
$$
When $\ell = 1$, there is an $\mathsf{AC^1}$ circuits for $f(i,j,\ell)$. When $\ell > 1$, we use the formula
$$
f(i,j,\ell) = \bigvee_{k=i}^{j-1} (f(i,k,\lfloor \ell/2 \rfloor) \land f(k+1,j,\lceil\ell/2\rceil)).
$$
The resulting circuit is still $\mathsf{AC^1}$, since there are only $O(\log n)$ levels of recursion.
A different way of looking at this construction is to notice that for inputs of length $L$, we can replace $L^*$ with $L \cup \cdots \cup L^n$; and that $L^m$ can be computed in $O(\log m)$ steps using repeated squaring.


What is "rank" in a binary search tree and how can it be useful?

According to this book (Chapter 3.2), a node in a BST has rank $k$ if precisely $k$ other keys in the BST are smaller. So, if you order all the BST nodes according to their keys, then each node with rank $k$ will take $k$-th place.


Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Fancy answer

We need to show that the set
$$R = \{x \in \{0,1\}^* \mid C(x) < |x|\}$$
is c.e. (allow me to use the new terminology). The defining condition for $R$ is equivalent to
$$\exists n, m \in \mathbb{N} \,.\, T(n,0,m) \land U(m) = x \land |n| < |x| \tag{1}$$
where $T$ is Kleene's predicate and $U$ the associated output function.
In words, the formula means: there exists a code $n$ such that the $n$-th machine computes $x$ (on input $0$) and the length of $n$ is less than the length of $x$. We are done because (1) is a $\Sigma^0_1$-formula, therefore it defines a c.e. predicate.

Scholium: a $\Sigma^0_1$ formula is a formula of the form
$$\exists n \in \mathbb{N} \,.\, \phi(n, x)$$
where $\phi(n,x)$ is a decidable formula. Such a formula determines a c.e. predicate: to semidecide whether it holds for $x$, just run a loop $n = 0, 1, 2, \ldots$ and test for each $n$ whether $\phi(n,x)$ holds. If and when such an $n$ is found, terminate.

Non-fancy answer

In paralell, run all machines described by codes of length less than $|x|$ (there are around $2^{|x|}$ such machines, which is a finite number). If and when one of them stops and produces output $x$, terminate.


What does $k$ mean in regular expressions?

$k$ means that if $w \in R^{k}_{ij}$ then on reading $w$, FA starting from the state $i$ enters the state $j$ and never enters a state $t$ where $t > k$ while reading input $w$. In the book, you learn from, $R^{k}_{ij}$ is defined as the set of all strings that transition the automaton $M$ from $q_i$ to $q_j$ without passing through any state higher than $q_k$.


difference between propagation speed and bandwidth in digital communication

They are unrelated.

The bandwidth is, as you correctly said, the number of bits per second. The propagation speed is the time until the first bit arrives (this is also called the latency).

Imagine you have an army of snails that can carry SD cards along a straight line. Their propagation speed is very slow, so it takes a long time until a snail arrives after you send it. However, you can send a snail every second, so that after the initial delay your snails deliver one SD card of data every second. That's high bandwidth.


How to Solve the following Recurrence Equation?

Regarding the master method, I don't quite understand why you got stuck. You had to show that the function $f(n) = 2^n$ satisfies $f(n/2) \leq (1-\epsilon) f(n)$ for some $\epsilon > 0$ and large enough $n$. You showed this using some complicated calculation. So the condition is satisfied, and the method applies, giving the answer $T(2^m) = \Theta(f(m)) = \Theta(2^m)$. A more elementary way to check the condition is to notice that when $n \geq 2$,
$$
2^{n/2} \leq 2^{n-1} = \frac{1}{2} \cdot 2^n.
$$

Regarding substitution, clearly $f(n) \geq n + c$. In the other direction, when $n \geq M$ we have $\sqrt{n} \leq n/\sqrt{n} \leq n/\sqrt{M}$, $\sqrt[4]{n} \leq \sqrt{n}/\sqrt{M} \leq n/M$, and so on. Therefore when $n^{1/2^{k+1}} \geq M$,
$$
\begin{align*}
f(n) &= n + c + \sqrt{n} + c + \cdots + n^{1/2^k} + c + f(n^{1/2^{k+1}}) \\ &\leq n + \frac{n}{\sqrt{M}} + \cdots + \frac{n}{\sqrt{M}^k} + (k+1) c + f(n^{1/2^{k+1}}) \\ &\leq
n \sum_{t=0}^\infty \frac{1}{\sqrt{M}^t} + (k+1)c + f(n^{1/2^{k+1}}) \\ &=
\frac{1}{1-1/\sqrt{M}} n + (k+1)c + f(n^{1/2^{k+1}}).
\end{align*}
$$
Choosing $k$ so that $n^{1/2^{k+1}} \approx M$, we deduce that
$$
f(n) \leq \frac{1}{1-1/\sqrt{M}} n + O(c\log\log n),
$$
where the hidden constant depends on $M$. Choosing an arbitrary $M$, we get $f(n) = O(n)$. This implies that
$$
f(n) = n + c + f(\sqrt{n}) = n + O(\sqrt{n}).
$$
Combining this with the lower bound, we have
$$
n + c \leq f(n) \leq n + O(\sqrt{n}).
$$
This is a much better estimate than the one we got using the master theorem.


How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?

The left associativity of applications is only relevant when you have a sequence of applications. If it were correct to interpret y λx.x y as y (λx.x) y, then the left associativity rule would disambiguate it to (y (λx.x)) y. But that interpretation violates the rule that abstractions extend as far right as possible.
Normally one never writes y λx.x y unparenthesized, so I think it's best for parsers to reject it, but if I saw it I would guess that it means y (λx.x y).


Best design of a software controlled page table: to echo the TLB?

Page table structure (and especially page table structure for software managed page tables) was a hot area of research in the mid 1990s.  At its root this is just the problem of creating a data structure to represent a map from one set of integers (the keys (virtual addresses)) to another set of integers (physical addresses).  So you should expect the answer to have something to do with hash tables or search trees or both.  The "best" choice depends on:

how large your virtual address space is (e.g., 32 vs. 64 bit)
how large your physical address space is
how sparse or dense your mapping is (what fraction of the virtual address space you expect an individual process to use)
how clustered your mapping is (you may only be using 1/10th of 1% of the address space, but all the virtual addresses cluster into one of a few dense regions/segments (the code segment, the stack segment, ...)
the "natural" page sizes supported by your tlb
whether you have address space identifiers (ASIDs), and how big they are (thus dictating how frequently they need to be reused.)
whether you need to be able to use a shared memory abstraction to share data between different processes
whether you have multiple tlbs that need to be kept coherent with some kind of tlb shootdown
whether you have a single process and just need to virtualize that single process's address space over a backing store, or whether you are using paging to provide protection between multiple processes
where and how you are going to store information about pages that have been moved to backing store
(and more, like how you want to choose pages to replace)

Here are some good things to read:

  Huck, Jerry; Hays, Jim: Architectural Support for Translation Table Management in Large Address Space Machines, Int'l Symp Comp Arch (ISCA-20):39-50, 1993.  doi:10.1145/165123.165128.

For machines with virtual address spaces that are much larger than the physical address space the inverted page table is the traditional solution.  The inverted page table has exactly as many entries as there are physical pages.  The entry records the virtual address mapped to that physical address, and also includes a link pointer.  You look up a virtual address by hashing it to find a starting entry in the inverted table, then searching the linked list starting at that entry until you either find the virtual address in question, or find the end of the list.

There are a number of problems with inverted page tables.  They don't handle having multiple virtual addresses mapped to the same physical address, it is expensive to find all of the physical pages that have been mapped for a particular process (you need to walk the entire table looking for entries with that process's ASID), and you need a different data structure to record information about virtual pages that have been moved to backing store.  From a performance perspective the inverted page table does poorly at leveraging spatial locality because adjacent pages hash to disparate locations in the inverted page table.  The Huck and Hays paper suggests variations on the inverted page table to address some of the inverted page table's shortcomings.

  Talluri, Madhusudhan; Hill, Mark D; Khalidi, Yousef A: A new page table for 64-bit address spaces, ACM Symposium on Operating Systems Principles (SOSP-15):184-200, 1995. doi:10.1145/224056.224071.

This paper suggests a different approach to dealing with the locality problems of the inverted page table.  Essentially the inverted page table is used for super-blocks made up of some number (16 in the paper) of normal pages.  Thus you get the nice behavior of the inverted page table (proportional to the size of physical memory) but get some locality benefits because subsequent tlb misses tend to be for other pages in the same super-block.

  Bala, Kavita; Kaashoek, M Frans; Weihl, William E: Software Prefetching and Caching for Translation Lookaside Buffers, USENIX confernce on Operating Systems Design and Implementation (OSDI-1):18, 1994.

This paper suggests that no matter what structure you use for the page table, you should augment the hardware TLB with a large, direct-mapped, software tlb.  The hardware tlb usually needs to be quite small so suffers from capacity misses.  You try to cover a large percentage of the capacity misses by finding the appropriate entry in the direct-mapped software tlb.  The hope is that the software tlb is relatively quick and covers most accesses, and then you can use a more complicated structure (like a forward-mapped page table) for the few remaining misses.

So there are lots of choices, and there are lots of variables to consider.  The best data structure choice really depends on the characteristics of your particular machine and your particular workload.  You are trying to optimize for a sparse, but chunky, mapping function, trying to make sure you can handle operations beyond just lookup efficiently, and trying to leverage the spatial locality in the address stream to minimize cache misses while accessing the page table.


Which is the equivalent processing of human brain in terms of computer processing?

Here is what we know for sure. The largest neuronal network simulation to date was achieved using the K Japanese supercomputer (see the Top500) during summer 2013, a few months ago.

Using the open-source software NEST, the scientists simulated a network consisting of 1.73 billion nerve cells connected by 10.4 trillion synapses. To realize this feat, the program recruited 82,944 processors of the K Computer and used 1 petabyte of memory. The process took 40 minutes, to complete the simulation of 1 second of neuronal network activity in real, biological, time.
Although the simulated network is huge, it only represents 1% of the neuronal network in the brain.

K is a peta-scale supercomputer, so, we need an exa-scale machine to completely simulate the whole human brain. These machines will be (probably) available between 2017-2020.


Figuring out when one algorithm will be slower than another algorithm

Algorithm A contains an instruction that is executed $size * 10000$ times.
Algorithm B contains an instruction that is executed $size * size$ times.

It is obvious that the comparison between A and B depends on the variable size.
You can see that if $size < 10000$ then B performs better, and if $size > 10000$ then A performs better.
If $size = 10000$ then A and B can be considered equally fast.

It is easy to calculate the result for $sum$ when $size = 10000$.

I am not sure if it makes sense to answer with big O notation here because the algorithms are different. A computes $size * 10000$ and B computes $size^2$, which are two different algorithms; it does not make sense to compare them with big O notation in my opinion. Usually big O analysis helps in comparing algorithms that solve the same problem, which is not the case here.


Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem

First of all, it is not true that $M$ halts on every input iff $L(M)$ is decidable. Indeed, $L(M)$ can be decidable even if $M$ doesn't halt on every input. Consider for example the machine which never halts on any input—the empty language is certainly decidable.

Rice's theorem considers properties of partial functions. The partial function is the one computed by the Turing machine, with $\bot$ representing the case that the Turing machine doesn't halt on a specific input. If a machine $M$ always halts then the corresponding function is total—never attains the value $\bot$. This is a property of partial functions, and fits within the framework of Rice's theorem.

If you're not sure about this, have a look at the proof that the language of total Turing machines (ones that halt on all inputs) is not decidable.


Is following observation on Ladner's theorem correct?

I'm annoyed at both ["any" being used as a quantifier] and [the placement of quantifiers making things even more ambiguous], so I'll start with the two interpretations of your initial block-quote.

  Suppose there is a function $\hspace{.04 in}f$ in $\omega(1)$ such that  NP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ .

  Does it follow that  P = NP ?

It's not known to, since    ($n\mapsto 2^{\hspace{.02 in}n}\hspace{-0.03 in}$)  $\in$  $\omega(1)$    and  NP $\subseteq$ EXP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}(2^{\hspace{.02 in}n})}\hspace{-0.04 in}\right]$  are both known.

  Suppose that for all functions $\hspace{.04 in}f$ in $\omega(1)$,  NP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ .

  Does it follow that  P = NP ?

Yes, since as described in this answer, there exists

a function $\hspace{.04 in}f$ in $\omega(1)$ such that  DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ = P .

The truth of your "That is ... fixed $c\geq 1$." sentence has nothing to do with Ladner's Theorem

- The empty language and full language, for example, are such NP problems.

For the sentence after that, the g given by  g(n) = c  is such a g, and functions f cannot simultaneously be in $\omega(1)$ and satisfy  f(n) << c ,  so where's the violation of Ladner's theorem?

By the function g I just mentioned, the part of your

"And so if ..." sentence before that sentence's "and" is true.

For the rest of that sentence, see this answer's two block-quotes and its responses to those.

This answer's response to its "there is" block-quote would still apply.

I believe this answer's response to its "for all" block-quote

would also still apply, by a similar argument.


How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

If the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?

This depends on how technically precise you want to be.

The most correct answer is "No". Consider an optimisation problem $OP$ for which the encoded length of the output is superpolynomial in the encoded length of the input. Clearly no algorithm can produce the output in time polynomial in the encoded length of the input, so $OP \not\in \mathcal{P}$. However, the decision version $DP$ takes as input both the input of $OP$ and the guessed answer, so it is allowed time polynomial in the sum of the two, and in particular does not need to execute in time polynomial in the length of the problem per se.

However, if you're guaranteed that the output of $OP$ has (asymtoptically) an encoded length which is polynomial in the encoded length of the input (say $O(n^a)$ for input length $n$ and unknown $a$), then you can do a binary search, starting at any reasonable guess, doubling unless you get high enough, and then searching back down. The number of calls of the decision problem is $O(n^a)$, each call of the decision problem takes time polynomial in $n$, and the product of two polynomials is a polynomial.


How to write an if then logical constraint given part of the input related to a decision variable?

If you have two binary variables X, Y and you want to express the constraint X implies Y via a linear inequality you can use the logical equivalent statement (not X) or Y, which in linear programming translates to:
$$(1-X) + Y \geq 1$$
In Gurobi-Code this would be: model.addConstr((1-X) + Y >= 1, name="implication").


Is graph search of shortest (optimal) path an instance of optimisation?

Although I'm not sure what you're calling 'optimisation', I can tell you that both Dijkstra's algorithm and BFS are not some form of searching a solution space. If they were, they would start with an initial solution, i.e. some path from A to B, and eventually find the shortest path  between A and B after considering multiple such paths. But this is not the case, as these algorithms both construct partial solutions before eventually getting a complete solution.

On other hand, it is true that locally, the distance to some node is at first estimated by some path and possibly later improved, so there is some similarity here. However, the incremental approach to a solution is an important aspect in these algorithms, which doesn't occur in gradient-based optimisation, as these cases usually don't even have a concept of a partial solution which can be extended into a full solution.


Here's a nice, and accessible, blog on why we need the type to have that form.

http://cdsmith.wordpress.com/2012/04/18/why-do-monads-matter/

Also, this blog motivates why we want them this why and how they naturally arise in our daily workings :)

Enjoy!


Definition of extensional and propositional equality in Martin-Lof extensional type theory

what does it mean by becoming extensional in the first place?

The axiom of extensionality relates to what it means for two functions to be equal. Specifically, extensionality says:

$f = g \iff \forall x \ldotp f(x) = g(x)$

That is, functions are equal if they map equal inputs to equal outputs. By this definition, quicksort and mergesort are equal, even if they don't have the same implementations, because they behave the same as functions.

  How does it become extensional

What's missing is the rule of definitional equality for functions. It usually looks like this:

$\frac{\Gamma, (x : U) \vdash (f x) = (g x):V}{\Gamma \vdash f = g: (x : U) \to V}\text{(Fun-DefEq)}$

That is, two functions are definitionally equal when they produce equal results when applied to an abstract variable. This is similar in spirit to the way we typecheck polymorphic functions: you make sure it holds for all values by making sure it holds for an abstract value.

We get extensionality when we combine the two: if two functions always produce the same result, we should be able to find some equality proof $P$ such that $\Gamma,(x: U) \vdash P:Id_V(f x, g x)$ i.e. the proof that the two functions always produce the same result. But, if we combine this with the rule $\text{(Id-DefEq)}$, then any time two functions are extensionally equal (i.e. we can find the proof term $P$, then they are also definitionally equal.

This is in stark contrast to an intensional system, where two functions are equal if and only if their bodies are syntactically identical. So mergesort and quicksort are intensionally different, but extensionally the same.

The $\text{(Id-DefEq)}$ means that extensional equality is baked into the type system: if you have a type constructor $T : ((x : U) \to V) \to \mathsf{Set}$, then you can use a value of type $T\ f$ in a context expecting $T\ g$ if $f$ and $g$ map equal inputs to equal outputs. Again this is not true in an intensional system, where $f$ and $g$ might be incompatible if they're syntactically different.

  Does the above mean that we purposefully drop the proof that M and N are equal and just consider them to be equal definitionally (like a presumption)?

It's even a bit stronger than that. It's saying that $M$ and $N$ are definitionally equal any time there exists some proof that they are propositionally equal. So on the one hand, if you have a propositional proof that two values are equal, you can forget that proof and say that they are definitionally equal. But on the other hand, if you are trying to prove that two values are definitionally equal (as a dependent type checking algorithm would), then you cannot say that they are not equal unless you are certain that no proof $P$ exists. This is why it is undecidable.


What is a name for ?

There may be a name for that recursion, but then I would have
forgotten it. It does not really matter. Call it central recursion or
middle recursion if you will. And you can even define it simply :

  A recursive rule (or non-terminal) is said to be middle recursive iff it is recursive, but neither left recursive nor right recursive.

If I have to write a paper, and cannot find the accepted name for
something, and there may be none, then I make one up and give a proper
definition for it so that people can read my paper.

The point is that not everything needs to have a specific name. You
give names only to entities and concepts that play a specific role in
the kind of work you are doing. You example seems to be just a general
case of recursion, which happens to be neither left nor right.

Left recursion is important as it plays a significant role when you
study left-to-right recursive descent parsers. Hence it was given a
name.

Regarding your second question, I would agree. This may even happen in
the absence of recursion, with a grammar generating a finite language.
$\qquad  A \to 0 0 \mid 0 1$
But there are other grammars for that language. This grammar is not LL(1), but the language is.


How does the midpoint line drawing algorithm work?

This is not a self-contained answer, but you can find all the details and pictures in the link below. However, I'll give a summary of the idea behind this algorithm.

Take $F(x,y) = (x-x_1)dy - (y-y_1)dx$ as the line function. Let $p=(x_p,y_p)$ be the last pixel we turned on, then $m=(x_p+1,y_p+0.5)$ is the point exactly between the right and the right-top neighbouring pixels. This is the middle point as the title suggests.

Now, if $F(x_m,y_m) > 0$ then the line is above $m$ and if $F(x_m,y_m) < 0$ then it is below $m$, otherwise the line passes through $m$. In the first case we turn on the pixel above the midpoint (i.e. top-right of $p$), and the pixel bellow $m$ (right of $p$) for the second case, and an arbitrary one for the third case.

$d$ initially is the value of $2.F(x,y)$ for the first midpoint (the reason for doubling it to get an integer and avoid floating point calculations), so $d$ is guiding us which direction (N or NE) we should go next. At each iteration instead of recalculating $d$, depending on our last choice of direction we just need to add $\Delta_{NE}$ or $\Delta_E$ to get the new value for $d$.

http://www.dgp.toronto.edu/~karan/courses/csc418/fall_2002/notes/lines.html

I hope it helps.


I assume you mean "Turing machine" by "function", otherwise it is meaningless to say a function halts on some input.

Suppose $\mathrm{HALT}$ exists, then we construct a Turing machine $H$ as follows:

On input $\langle M, w\rangle$ where $M$ is an (encoding of) Turing machine:

Construct a Turing machine $N_{\langle M, w\rangle}$ with input $x$ as follows: run $M$ on $x$ and return what $M$ returns.
Run $\mathrm{HALT}$ on $\langle N_{\langle M, w\rangle}, 0\rangle$ and return what $\mathrm{HALT}$ returns.

Note the result of running $N_{\langle M, w\rangle}$ has nothing to do with its input $x$. If $M$ halts on $w$, $N_{\langle M, w\rangle}$ halts on all inputs, thus $\mathrm{HALT}( N_{\langle M, w\rangle}, 0)$ returns true. otherwise $N_{\langle M, w\rangle}$ halts on no input, thus $\mathrm{HALT}( N_{\langle M, w\rangle}, 0)$ returns false.

Now we can see $M$ halts on $w$ if and only if $H$ accepts $\langle M, w\rangle$. Since $H$ always halts, $H$ is a decider for the normal halting problem, a contradiction!

So $\mathrm{HALT}$ does not exist.


What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?

Whether or not Coppersmith-Winograd is the "best" algorithm depends on your circumstances, of course. CW and algorithms like it are usually considered impractical due to high constant factors. Strassen's algorithm is more common in practice.

But since computational complexity is what you are interested in, CW was beaten quite recently.

Virginia Vassilevska Williams (2014), Multiplying matrices in $O(n^{2.373})$ time, Stanford University.

As far as we know, calculating the determinant of a matrix, or eigenvalue estimation, or anything else that could be used to determine if a matrix is singular or not are at least as complex as matrix multiplication.


Store a n-bit string using only O(log n) space

There are $2^n$ many $n$-bit strings, but only polynomially many strings of length $O(\log n)$.


What is the most efficient constant-space sorting algorithm?

Consider cocktail shaker sort, which is a bidirectional version of bubble sort.  You bubblesort from low to high, and then (this is the added part) you bubblesort from high to low, repeat until done.  This is still $O(n^2)$, but it makes significantly fewer passes on average, because small elements near the high end of the array will be moved to their final position in a single pass rather than N passes.  Also, you can keep track of the lowest and highest positions where a swap occurred; subsequent passes need not scan beyond those points.


Language of decimal encodings of cubes is not regular

Denote your language by $L$.
Suppose that the pumping length is $p$. Consider
$$
N = (10^{p+1} + 1)^3 = 10^{3p+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1,
$$
whose decimal encoding is
$$
w = 1 0^p 3 0^p 3 0^p 1 \in L.
$$
According to the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xz \in L$. Since $|xy| \leq p$, the part $xy$ lies within the prefix $10^{p-1}$. If $y$ contains $1$ then $xz$ has a leading zero, which is impossible (if you allow leading zeroes, consider $L \cap (1+9)(0+9)^*$ instead), so $y$ consists only of zeroes. Hence
$$
xz = 10^q 30^p 30^p 1,
$$
for some $q < p$,
which encodes the number
$$
n = 10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1.
$$
If $xz \in L$ then $n$ is a cube. Since $n$ ends with $1$, necessarily $n = 10m + 1$ (you can check this directly by considering $0^3,1^3,\dots,9^3$), and so
$$
10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1 =
1000 m^3 + 300 m^2 + 30m + 1,
$$
which implies that
$$
(10^{p+q+2} + 3 \cdot 10^{p+1} + 3) 10^p =
(100 m^2 + 30 m + 3) m.
$$
Clearly $100m^2 + 30m + 3$ is divisible by neither $2$ nor $5$ (its units digit is $3$), and so $10^p$ must divide $m$. In particular, $m \geq m_0 := 10^p$. However, this is impossible, since $N = (10m_0 + 1)^3$, and $n < N$.


Is 0-1 integer linear programming with only equality constraints NP-Hard?

Consider the Maximum Independent Set problem ($\mathcal{NP}$-hard): given a graph $G=(V,E)$, find the maximum independent set in $G$, i.e., the subset of vertices $I \subseteq V$ such that every two vertices in $I$ are not adjacent $\forall v_1,v_2 \in I, (v_1,v_2) \notin E$.

This problem has a well known Integer programming formulation:
let $x_i$ be a binary variable for every $i \in V$ and equal one if $i \in I$.
\begin{align}
\max & \sum\limits_{i=1}^n x_i \\
\text{subject to} & \\
& x_i + x_j \leq 1 \text{ for all } (i,j) \in E \\
& x_i \in \{0,1\} \text{ for all } i \in V
\end{align}

If $|V| = n$, this problem has $n$ variables and $O(n^2)$ constraints.

To transform it to equality form (a.k.a. standard form) one might introduce slack variables for every constraint. Generally, if you have $Ax <= b$ you can write $Ax + x_s = b$ where $x_s \geq 0$ and $x_s$ are called slack variables.

It appears that for Independent Set slack variables are actually binary!
Thus, you have the formulation
\begin{align}
\max & \sum\limits_{i=1}^n x_i \\
\text{subject to} & \\
& x_i + x_j +y_{ij} = 1 \text{ for all } (i,j) \in E \\
& x_i \in \{0,1\} \text{ for all } i \in V \\
& y_{ij} \in \{0,1\} \text{ for all } i,j \in V
\end{align}

This formulation exactly satisfies yours

  0-1 integer linear programming with only equality constraints (ILPEQ)

Now, you have a basic reduction argument. Suppose, you can solve ILPEQ fast, that means you can solve independent set fast, but it is known to be $\mathcal{NP}$-hard, so ILPEQ is also $\mathcal{NP}$-hard. The formal argument as well as checking that this is in fact a polynomial reduction I leave to the reader.


Many widely used codes for binary data are concatenated codes, which are composed by using two error-correcting codes. The inner code is over a binary alphabet, and the outer code is over an alphabet whose symbols correspond to the codewords of the inner code. This allows you to use the superior power of larger alphabet sizes to encode binary messages without "cheating".

The standard definition of minimum distance is a natural one to use when considering concatenated codes, as well as in the theory of codes over large alphabet sizes. It would only be "cheating" if you used these numbers to compare a binary code with a large-alphabet code that encodes binary input without using an inner code as well; coding theorists are clever enough not to do this (and I believe that since concatenated codes were invented, large-alphabet codes have often been used along with an inner code, but large-alphabet codes are also very good for correcting error in bursty channels such as CDs, since a large number of consecutive bit errors will only affect a few "symbols").


What data is stored in the symbol table for a number token?

Typical lexers will return a sequence of pairs, where the pair consists of the token type and an optional value. For a token such as 12345, the token type will be something like "number" and the value will be 12345.  If the lexer only emitted the information that there was a numeric constant in the input, then the following phases of the parser would have no way to know which number it was, and that is obviously important.

I don't understand why you started talking about the symbol table in the end of your question, and I think you may be confused.  The quotation you gave says nothing at all about the symbol table, which usually belongs to a later phase of compilation. A symbol table maps symbols (that is, names) to values.  The quotation in your question is about tokens, not symbols.  Tokens are not usually stored in a symbol table, and there is no reason to store numbers in a symbol table.  Typically a parser will have a stack, and will push whole tokens onto the stack, and pop them off again as needed.


What is a sort in programming language semantics?

It depends on what semantics we would take for types and sorts. -- However a brief - little informal - definitions could be - Sorts are classes of ASTs and types are classes of values.


As you probably know, $A^i_{st}$ is the total weight of walks of length $i$ from $s$ to $t$. Since
$$
\sum_{i=0}^k (xA)^i = \sum_{i=0}^k A^i x^i,
$$
the $s,t$ coefficient of $A_{G'}$ is
$$
\sum_{i=0}^k A^i_{st} x^i.
$$
This is a polynomial in which for $0 \leq i \leq k$, the coefficient of $x^i$ is the total weight of walks of length $i$ from $s$ to $t$.


Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices

Yes, there is such a theorem, more or less. It basically states that the k-dimensional Weisfeiler-Lehman procedure subsumes (i.e. dominates) all known combinatorial approaches to graph isomorphism testing. (Your concrete proposal should be subsumed by the 2-dimensional Weisfeiler-Lehman procedure, if I am not mistaken.) For each fixed k, there is a class of counterexamples to the k-dimensional Weisfeiler-Lehman procedure known as the Cai-Fürer-Immmerman construction.

I first learned the basics of the Weisfeiler-Lehman procedure and the Cai-Fürer-Immmerman construction from

  http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

There is much more to learn about the Weisfeiler-Lehman procedure than described there, but at least the treatment of the Cai-Fürer-Immmerman construction is complete and sufficient for your purpose. "The Weisfeiler-Lehman Procedure", by Vikraman Arvind is a recent brief essay meant as an invitation to the topic.

Perhaps the crucial point to take away from my answer is that if you would find a purely combinatorial isomorphism testing method (like the one describe in your question), which is not subsumed (i.e. dominated) by the k-dimensional Weisfeiler-Lehman procedure, then this would be a breakthrough by itself, independent of whether the method would be actually useful.


Dynamic programming and multiple optimal solutions

Assume you already computed the dynamic programming table DP[SIZE][LENGTH] where DP[s][l] stands for maximum profit that can be obtained by using cuts up to size s on a rod of length l. You want to find all decomposition to get the value DP[SIZE][LENGTH], to do this notice that at every step DP[s][l] we have two options, use the cut of size s or don't use it (possibly using both values we get optimal answer). The pseudo code will look like this:

PROFIT[s] = value of using a cut of size `s`.

def find_answers(s, l, partial_answer):
    """ Populate in `partial_answer` possible ways to
        partition a rod of length `l` using cuts of
        size up to `s` and report them.

        `partial_answer` is a multiset that will contain all cuts
        done so far.
    """

    # Base case when length is `0`.
    if l == 0:
        report partial_answer

    best = DP[s][l]

    # If not using the cut of size `s` gets a profit as good
    # as best expected profit, find solutions.
    if DP[s - 1][l] == best:
        find_answers(s - 1, l, partial_answer)

    # Try to find an answer that uses current cut size if `s` is
    # less than current length, and profit using this cut is as good
    # as best expected profit.
    if s <= l and DP[s][l - s] + PROFIT[s] == best:
        find_answers(s, l - s, partial_answer + {s})

Call this function like find_answers(SIZE, LENGTH, {}) with an empty multi-set as partial_answer. Since it is doing backtracking it is possible to get to the same state (s, l) several times with different partial_answers. This function will call report partial_answer exactly once per valid decomposition, also notice that the number of optimal decomposition can be exponentially large.


In complexity theory, does polynomial time refer to the big-O notation?

Very rarely we measure the exact running times, and when we do, it's specified quite clearly.

Then, there is the big-O notation and its friends, which give information about the asymptotic behavior of the algorithm.

But different big-O sets (being pedant here, O(n) is actually a set of functions) can be grouped into classes. There are linear algorithms, which run in O(n). Then, there are sublinear algorithms (faster than O(n), such as O(logn)). Polynomial algorithms are quite important, and represent the algorithms with running times bounded by a polynom (e.g. O(n^k)). There are expone ntial algorithms, such as O(k^n), nonpolynomial algorithms, which grow faster than polynomial and include exponential, and so on.

All of these are simply a coarse categorization of the running time, which can be made by looking at the asymptotic behavior of the algorithm.


Try proving directly that with high probability, no set of size at most $n/2$ has a small edge neighborhood. See for example Ellis's writeup for the complete details.

Another possibility is to try and use a more sophisticated large deviation bound to analyze $|E(S,S')|$. For example, there are versions of Chernoff's bound for negatively dependent random variables, and there is Azuma's bound, which is a martingale version of Chernoff's bound. The classical example is concentration of the chromatic number, appearing in Chapter 7 of Alon & Spencer as well as many other places, such as Bukh's write-up.


Clustering a set of point by affine transform

I would suggest you try using RANSAC.  Randomly pick a triplet of $a$ points and $b$ points, find an affine transformation that maps the former to the latter, find all other points that it maps well, and create that as a candidate cluster those.  Repeat many times, and keep the best cluster.  Remove the points in that cluster, and then repeat.
This might perform better than your $O(n^3)$ time solution if you expect to have a few large clusters (but probably it is not better if you expect to have many small clusters).


Applying the Master Theorem on Merge sort

You can't use $n/2$ since this bound just isn't always true. Suppose that $n = 5$. It is not the case that you can split an array of length 5 into two arrays of length 2.5. It's not even true that you can split it into two arrays of length at most 2.5. But you are able to split it into two arrays of length at most $\lceil 2.5 \rceil = 3$.

Note that the textbook estimates the time it takes to sort an array with at most $n$ elements (rather than the time it takes to sort an array with exactly $n$ elements).


Analysis and classification based on data points

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

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

See also:

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


Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?

The difference between $\mathcal{U}$ and $M_x$ is that $\mathcal{U}$ can be hardcoded while $x$ is an input to the machine.

In other words, when Arora and Barak write "run $\mathcal{U}$ to simulate $M_x$", what they mean is to switch to a part of the Turing machine which behaves like $\mathcal{U}$ (you can think of it as a function), and afterwards switch to some other part of the machine. The states of $\mathcal{U}$ do the work of simulating $M_x$.

You are not simulating $\mathcal{U}$. You incorporate its code as part of your Turing machine. (In programming languages, this is sometimes known as inlining.)


what is the relationship between entropy and variance?

They measure different things.  Given the variance, you can solve for $p$ and compute the entropy, and vice versa, but they have different interpretations and different applications.  You can learn a bit about the meaning and applications of these notions in the corresponding Wikipedia articles: https://en.wikipedia.org/wiki/Entropy_(information_theory), https://en.wikipedia.org/wiki/Variance.
Analogy: if we have a sphere, I could measure its radius, or I could measure its volume.  They both reflect the size of the sphere, so you could as, what is the advantage of radius, or of volume?  Answer: they measure different things, so depending on what you want to do, one or the other might be more useful.


What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?

No, an oracle is a black box that solves a problem in a single step. The problem that it solves can be any problem, it doesn't need to be the halting problem.

What Scott is saying is that there is some black box that a BQP machine with it can do more than what a BPP machine can do with it. However, it doesn't mean that without that black box BQP is more powerful than BPP.

A simpler case is P vs. NP. By Baker, Gill, and Solovay's result there is a black box that P with that black box is not equal to NP with that black box. But it doesn't tell us much about what should be the answer to P vs. NP.


Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language

Your language is known as $L^+$.

It is a very standard property of regular languages that if $L$ is regular then so is $L^*$; this can be proved in several ways, and you can find proofs in textbooks and online sources. Since $L^+$ is either equal to $L^*$ or obtained from it by removing $\epsilon$ (the empty string), then $L^+$ is also regular.


Permutation on matrix to fill main diagonal with non-zero values

You can use bipartite matching for that.

Nodes corresponding to rows in one set, nodes corresponding to columns in the other set. A row has an edge to every column in which it has a 1. If the maximum matching has size n, every row is matched up with a corresponding column and the matching gives the order. The index of the column that a row is matched up with will be its new position.


Because a problem is in NP if, and only if, "yes" instances have succinct certificates. Informally, this means that the solution to any instance is at most polynomially large in the size of the instance, and if you're given an instance and something that is claimed to be a solution to it, you can check in polynomial time that it really is a solution.

More formally, a language $L\subseteq\Sigma^*$ is in NP if, and only if, there is a relation $R\subseteq \Sigma^*\times\Sigma^*$ such that:

there is a polynomial $p$ such that, for all $(x,y)\in R$, $|y|\leq p(|x|)$;
the problem of determining whether $(x,y)\in R$ is in P;
$L = \{x\mid \exists y\,(x,y)\in R\}$.

For example, consider graph 3-colourability.  You can describe a graph on $n$ vertices just by writing out its adjacency matrix, which requires $n^2$ bits.  If a graph is 3-colourable, you can describe a colouring in $2n$ bits: just list the colour of each vertex in turn (say, $00$ for red, $01$ for green, $10$ for blue).  So, if a string $x$ describes a graph, and that graph is 3-colourable, each 3-colouring can be described in a string $y$ with length $2\sqrt{|x|}\leq 2|x|$.  Furthermore, if I give you a decription of a graph and a description of a 3-colouring, you can easily check in polynomial time that it really is a 3-colouring: just check that adjacent vertices always have different colours. So, the relation
$$\{(x,y)\mid x\text{ describes a graph $G$ and $y$ describes a 3-colouring of }G\}$$
proves that 3-colourability is in NP.

So, to show that Masyu is in NP, we just need to construct the corresponding relation $R$.  We can describe an $n\times n$ instance of Masyu in $2n^2$ bits: for each square in turn, write $00$ if it's blank, $01$ if it contains a black circle and $10$ if it's a white circle.  We can describe a solution in $3n^2$ bits: for each square in turn, write $000$ if the square isn't on the solution path, and $100$, $101$, $110$ and $111$ if it's on the path and the next square is the one to the right, left, up and down, respectively. It's easy to check in polynomial time that a claimed solution really is a solution: just find a square that's on the path, follow the path and check it satisfies the criteria.


Closure properties between 2 languages of different types

You have to prove that the intersection of a context-free language and a regular language is always context-free. The simplest proof might go through push-down automata. Given a push-down automaton for a context-free language $L_1$, it is not too hard to augment it so that the state of a DFA for the regular language $L_2$ is maintained, and given this, you can construct a push-down automaton for $L_1\cap L_2$. Other proofs are also possible.

Each such question should be considered on its own. There are no general tricks. You can't just rely on the diagram. The problem with relying on the diagram in this case is that the intersection of two context-free languages need not be context-free; so the fact that regular languages are context-free isn't enough to show that the intersection of a context-free language and a regular language is again context-free.


How to find whether a point is in a line or not

Any finite line is described by two points. assuming we are talking 2D here, then your graph can be described as a set of points, having X and Y coordinations, and a set of edges $E$, which describe which pair of points are connected with a line. Elementary geometry tell us the function expressing the points on these lines is $Y=(X-X_0)\frac{Y_1-Y_0}{X_1-X_0}+Y_0$ ($(X_0,Y_0), (X_1,Y_1)$ denote the two point's coordinations)

To check whether a point belongs to this line, insert the point's coordinates to the equation and see if the equation holds. since the line is not infinite, we should also check if the point is between the two points defining the line. If the equation holds, it is sufficient to check if one of the point's coordinates (say $X$) is between the two point's defining the line ($X_0$ and $X_1$).

So, for any line in the graph, perform the check explained above, if the above criteria holds, the line contains P.

Checking if P is on a specific line takes constant amount of computational effort, so the running time of this procedure is $O(E)$.


Find a MST such that it's mostly red (original graph's edges are colored red and blue)

Hint: Add $\epsilon>0$ to the weight of all blue edges. (This is equivalent to the suggestion Raphael made in his comment.)


Are Kernel Codes (which are written in C) compiled during boot time?

Usually, everything is compiled in advance: the kernel and userland applications.

Roughly, the kernel is written in a special place on the disk (or other permanent memory), which the hardware will access at boot time, copy in RAM, and execute.

The kernel includes the disk driver and the filesystem driver, and will look for specific files on the disk, using them to load the first OS process (e.g. /bin/init, in unix-like OSs). This will in turn ask the OS to spawn new OS services/daemons, load new drivers, and finally start the user interface.

There is no need to have a compiler around during this. All the code which is loaded is machine code (already compiled).

The compiler is also not needed at installation time, since whoever produced the installation media (or network repository) wrote binary packages in it, containing compiled code.


Solving Hidoku problem using reduction to Hamilton path

For any NP-complete problem where the question is, "Can you complete this partial solution?" you can extract a solution from the decision problem just by filling in components of the solution one at a time and asking if there's still a solution.
Is there a solution with $1$ in the top-left corner? No. With $2$ in the top-left? No. With $3$? Yes. OK, let's fix the top-left to be $3$: we know this can be extended to a solution. Is there a solution with $3$ in the top-left corner and $1$ in the square next to it? And so on.  (In fact, you can be a bit more efficient by using the fact that two of the neighbours of the square labeled $i$ must be $i-1$ and $i+1$.)
This is a specific case of the concept of "self-reducibility": a problem is self-reducible if you can find the answer given an oracle for smaller instances of the decision problem. (In the case of Hidoku, the instances the oracle is called on are smaller in the sense that they have fewer blank squares.)  Some other examples of self-reducible problems are:

SAT. Suppose you want to know whether a formula in variables $X_1, \dots, X_n$ is satisfiable. If it's satisfiable, then either there's a satisfying assignment with $X_n=t$, or there's one with $X_n=f$, or both. So replace $X_n$ with $t$ and ask if the resulting formula in $n-1$ variables is satisfiable.  If so, recurse; if not, set $X_n=f$ and recurse.

$3$-colourability. Suppose you want to know whether a graph $G$ is $3$-colourable. If it is $3$-colourable and it has more than three vertices, then two of the vertices must receive the same colour. So, pick two non-adjacent vertices $x$ and $y$ and merge them (delete $y$ and make every vertex that was adjacent to it be adjacent to $x$). If the resulting graph is $3$-colourable, then $G$ has a $3$-colouring in which $x$ and $y$ have the same colour, so recurse. If they don't, then any $3$-colouring must assign different colours to $x$ and $y$, so we can add an edge between them and try a different pair of non-adjacent vertices.
If this process ever gives a graph that contains a $4$-clique –which we can test in polynomial time – then $G$ is not $3$-colourable. Otherwise, we eventually reduce the graph down to a $3$-clique, which is $3$-colourable. We can recover the $3$-colouring by tracking which vertices got merged into the different vertices of the $3$-clique.

Independent set. Suppose we wish to know if a graph $G$ has an independent set of size at least $k$. Pick a vertex $v$ and ask if $G-v$ contains a $k$-independent set. If so, $G$ has a $k$-independent set that doesn't include $v$, so recurse on $G-v$ to find out what it does contain. Otherwise, any $k$-independent set must contain $v$, so it can't contain any of $v$'s neighbours. So ask if $G-v-\Gamma(v)$ contains a $(k-1)$-independent set. If it does, recurse. If it doesn't, $G$ has no $k$-independent set.


Use the median instead of the mean. The median can only be bad if more than half the samples are bad.

The problem with the mean is that the mean could be bad from a lot of the samples being a little bit bad, or from a few of the samples being really bad. However, in general, you don't know the probabilities of different degrees of sample badness; just the probability of bad-versus-good.


How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

Here I assume $0\in \mathbb N$. If you disagree start with $105$.

Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order.
Apart from $1$ each number added is of the form $3\cdot x$, $5\cdot y$ or $7\cdot z$ where $x,y,z$ are previous numbers in the sequence. We can generate $S$ by shifting $x,y,z$ along the sequence.

So, first put $1$ into $S$, and set $x,y,z$ equal to $1$.

Now repeat: Take the minimum value $m$ of $3\cdot x$, $5\cdot y$ and $7\cdot z$, and add $m$ to the sequence $S$. The $x,y,z$ for which the minimum was taken are shifted to the next element of $S$. This might be more than one, or even all three.

$\newcommand{\ul}[1]{\underline{#1}}$
$\begin{array}{r|rr|rr|rr} S & x & {}*3 & y & {}*5 & z & {}*7 & \\\hline
1 & 1 & \ul{3} & 1 & 5 & 1 & 7 \\
3 & 3 & 9 &   & \ul{5} &   & 7 \\
5 &   & 9 & 3 & 15 &   & \ul{7} \\
7 &   & \ul{9} &   & 15 & 3 & 21 \\
9 & 5 & \ul{15} &   & \ul{15} &  & 21 \\
15 & 7 & \ul{21} & 5 & 25 &   & \ul{21} \\
21 & 9 & 27 &   & \ul{25} & 5 & 35 \\
25 &   & \ul{27} & 7 & 35 &   & 35 \\
27 & 15 & 45 &   & \ul{35} &   & \ul{35} \\
35 &    & \ul{45} & 9 & \ul{45} & 7 & 49 \\
45 & 21 & 63 & 15 & 75 &   & 49
\end{array}$

Works in linear time, as we need to take the minimum of three numbers in each step.


Testing two distributions, both accept null hypothesis

Hypothesis tests don't accept the null hypothesis.  Instead, they fail to reject the null hypothesis.  That's not the same thing.  For instance, if your sample size is small enough, it's certainly possible to fail to reject both null hypotheses.  All that the tests are saying is that the hypotheses "this data came from a standard normal" and "this data came from a uniform distribution" both seem plausibly consistent with the data, and that's not impossible.


$\mathsf{CircuitSat\in DTIME(2^n)}$ does not imply $\mathsf{NP\subseteq DTIME(2^n)}$ since the reduction might increase the input's size. Suppose for example that $L\in NP$ and the reduction from $L$ to $\mathsf{CircuitSat}$ maps strings of length $n$ to strings of length $n^c$ (for all $n\in\mathbb{N}$), then applying the reduction and using a naive exponential time algorithm for circuit sat yields a $2^{n^c}$ time algorithm for $L$.

If however you can place an NP-complete problem in a subexponential time class, e.g. $n^{\log n}$, then $NP\neq EXP$, since $n^{O(\log n)}$ is closed under polynomial transformations, i.e. $n\mapsto n^c$.


Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$

Assuming an appropriate base case, you can prove that $T(n) \leq \frac{3}{2} n^2$. (If this doesn't work for the base case, just increase $3/2$ to a large enough constant.)

Indeed, assuming this holds for $m < n$, we have
$$
\begin{align*}
T(n) &= n^2 + T(\tfrac{n}{2}) + T(\tfrac{n}{4}) + \cdots + T(\tfrac{n}{2^k}) \\ &\leq
n^2 + \frac{3}{2} \frac{n^2}{4} + \frac{3}{2} \frac{n^2}{4^2} + \cdots + \frac{3}{2} \frac{n^2}{4^k} \\ &=
n^2 \left(1 + \frac{3}{2} \left(\frac{1}{4} + \frac{1}{4^2} + \cdots + \cdots + \frac{1}{4^k}\right)\right) \\ &<
n^2 \left(1 + \frac{3}{2} \cdot \frac{1}{3}\right) \\ &= \frac{3}{2} n^2.
\end{align*}
$$


Check array in linear time with a constant space complexity

The problem does not have any $O(n)$ time algorithm. Note that it is easy to check in linear time if all the elements in the array are the same or not. However, to check if all the elements are district, the problem is known as Element distinctness problem. And, this problem has an $\Omega(n \log n)$ lower bound complexity. More technically, your problem can be reduced to element distinctness problem in linear time.
Therefore, the best possible solution here is $O(n \log n)$ time algorithm. For that, you can employ merge sort algorithm using a linked list. It also has an $O(1)$ space complexity.


How is type safety handled differently between reference and value types?

There usually is metadata about the runtime class of an object contained within the object itself, regardless of what language you're working in. This metadata is essential in languages like C# that have automatic memory management. In order to clean up an object that is no longer referred to by any other objects, you need to clean up all of its members too, which means deciphering exactly what class it is.

Just how that metadata is stored is up to the individual language implementation. Some languages make classes themselves into objects, and the metadata will consist of a pointer to the class. For example, this approach is used in some Common Lisp implementations (for reasons that we don't need to get into).

Other languages are a little more subtle about it. For example, in many object-oriented languages, an object stores a reference to a virtual function table or vtable. The vtable is a struct consisting of pointers to all of the implementations of that class's methods; the language runtime is responsible for setting up all of the vtables. Every instance of a class will store a reference to the same copy of that class's vtable, so you can figure out what class an object belongs to by asking which vtable it points to. This is exactly how object-oriented programming was mimicked in plain old C (see this article) and how it works under the hood in C++.

These kinds of complications are necessary because of inheritance. If I have an object x and I know it's of class A, x could really be an instance of any subclass B of A, and the language runtime needs to ascertain what the real class is in order to do method dispatch or garbage collection properly. In C#, struct types don't have inheritance at all, unlike class types. So a struct might have no metadata -- if the type of x is S and S is a struct type, it can't possibly be anything else.

I hope this at least addresses your narrow question about metadata. As for the much broader issue of type safety, have a look at Pierce's Types and Programming Languages, especially the chapters on subtyping.


What's the real difference between throughput and capacity of a network cable?

"Capacity", similar to many other terms, is a an overloaded word. In the example you bring, it seems that the meaning is equivalent to "throughput", i.e., the maximal "amount" of information a channel/network/etc. can transfer per time unit.

However, while these terms can be used interchangeably, to my ears "capacity" has the feel of a theoretical limit, while "throughput" has a feel of a practical limit. As in: "the capacity of a fiber channel is 1Gb/sec, which (due to coding, errors, and technical limitation)  leads to a maximal throughput of 986KB/sec (=of YOUR data)".

A different explanation which may be used in other settings is a one in which the capacity of a link is measured in relative terms, that is, it will be a ratio between 0 and 1, to be multiplied with a predefined  maximal rate of information transfer. This notation is useful when computing flows over the network.


You only have a limited number of states to worry about:

Let note them $Q_{i,j}$ where $i \in \{0,1,2,3,4\}$ is the number of 0 and $j \in \{0,1,2,3,4\}$ is the number of 1; each up to a max of 4 $\implies$ only 25 states.

Then the transition is
$\delta(Q_{i,j}, 0) = Q_{i+1,j}$ if $i<4$
$\delta(Q_{4,j}, 0) = Q_{4,j}$
$\delta(Q_{i,j}, 1) =Q_{i,j+1}$ if $j<4$
$\delta(Q_{i,4}, 1) =Q_{i,4}$

Then the starting state is $Q_{0,0}$ and the accepting states are all $Q_{i,j}$ with $i=0 \oplus j = 1$ (where $\oplus$ is the xor operator).


Leftist Heap doesn't support DecreaseKey operation?

Indeed, the right solution of DecreaseKey for leftist trees seems to be hidden on the internet. (My book by Weiss has a solution, but in the chapter on amortized analysis, and I do not quickly understand the argumentation.)

First, we cannot treat DecreaseKey as in binary heaps. There one repeatedly swaps the node with its parent until a parent is found which is actually smaller than the new value. This operation works in leftist trees, but may take linear time. In leftist trees there is no bound on the length of paths to the left, and indeed such a tree can be just one long linear leftmost tree.

The solution is to cut the node $q$ that is decreased (with its subtree), to change the value of $q$ to the new value, and merge it with the remainder $T$ of the original tree. Before we can do that we should bring $T$ back into leftist form, and restore the null-path-length values that are changed by cutting the subtree. As we cut $q$ from the tree, only the nodes from the parent $p$ upwards to the root have to be checked. (Unfortunately this may be a linear number of nodes, as we have seen.)

The solution is that the new null-path-length values we asign upwards in the tree are always one larger than the value at the previous level. This process stops when we are in a left child which has new value $\ell$ and its right sibling has value $r$ with $\ell \ge r$. Then the parent already had value $r+1 = \min\{\ell,r\}+1$ and we are done.

We know (from the basic property that makes leftist trees efficient) that a null-path-length value of $\ell$ means that there are $2^\ell-1$ nodes in that subtree, making the operation logarithmic.

The fact that the values upwards in the new tree are always one larger is essential here, that was not (necessarily) true along the path in the original tree.


Use a spreadsheet and calculate $e^{-100}$ both ways. It will become totally obvious what is going on. "We avoid subtraction" is not the problem. The problem is that you are adding the sum or difference of large numbers, and each large number has a large rounding error. For one method, the rounding error is not large compared to the result. For the other matter, the rounding errors are huge compared to the result.


Context-free grammar for $\{ a^n b^m a^{n+m} \}$

First, rewrite $a^nb^ma^{n+m}$ as $a^nb^ma^ma^n$. Now, from the outside in, you need rules to (1) add an $a$ to the front and back of your strings, and (2) to add $b$ to the front and $a$ to the back. It's also helpful to imagine building strings from the inside out... you can either add a $b$ to the front and an $a$ to the back, or an $a$ to both ends.

The first, working from the outside, rule is straightforward:

S := aSa

Notice that once you start adding $b$, you cannot go back to adding only $a$... so we need a new nonterminal:

S := B
B := bBa

Since the empty string is in your language, add another production to allow $B$ to generate the empty string. So we get:

S := aSa | B
B := bBa | -


Asymptotic complexity of Combination sum problem vs Coin change problem

The solution to the coin counting problem uses memoization as a way to decrease the exponential nature into just polynomial time.

The trick here, is that the amount, is always decreasing and can be computed from all of the smaller leftover amounts. this ensures that we need to compute up to amount values, that every next value is easy to compute from the ones before it.

Now for the main question: you are right in that getting the subsets themselves is what makes the difference - now the amount of 'values' you need to compute is the number you can calculate from the coin problem (for example, calculating there are 150 possible ways to distribute the coins, means you need to actually find all of the 150 solutions).
this number is not as small as amount and can be exponentially big in it

Shortly: calculating the number of solutions can be easily bounded by poly time, but calculating every solution means doing at least O(number of solutions) operations

I hope that helped! im new here :p


How to prove that DFAs from NFAs can have exponential number of states?

One operation that transforms an NFA into another NFA but does not do so for a DFA is reversal (point all the arrows the other way round, and swap initial states with accepting states). The language recognized by the transformed automaton is the reversed language $L^R = \{u_{n-1}\ldots u_0 \mid u_0\ldots u_{n-1} \in L\}$.

Thus one idea is to look for a language that has an asymmetric construction. Going forward, this language should be recognized by inspecting the first $n$ symbols, requiring only $n + O(1)$ states. Going backwards, it should be necessary to keep a memory of the last $n$ states, which requires $A^n + O(1)$ states where $A$ is the alphabet size.

We're looking for a language of the form $M_n S M'$ where $M_n$ consists of words of length $n$, $S$ is a nontrivial subset of the alphabet, and $M'$ doesn't provide any further constraint. We might as well pick the simplest alphabet $\mathscr{A} = \{a,b\}$ (a singleton alphabet won't do, you don't get smaller NFAs there) and $M' = \mathscr{A}^*$. A nontrivial $S$ means $S = \{a\}$. As for $M_n$, we require that it does not correlate with $S$ (so that the DFA for the reversed language will need to keep the memory of $S$): take $M_n = \mathscr{A}^n$.

Thus let $L_n = (a|b)^n a (a|b)^*$. It is recognized by a simple DFA with $n+2$ states.

Reversing it yields an NFA that recognizes $L_n^R = (a|b)^* a(a|b)^n$.

The minimal DFA that recognizes
$L_n^R$ has at least $2^{n+1}$ states. This is because all the words of length $2^{n+1}$ must reach distinct states in the DFA. (In other words, they belong to distinct Myhill-Nerode equivalence classes.) To prove this, take two distinct words $u,v \in \mathscr{A}^{n+1}$ and let $k$ be a position where they differ ($u_k \ne v_k$). Without loss of generality, let's assume $u_k = a$ and $v_k = b$. Then $u b^k \in L_n^R$ and $v b^k \notin L_n^R$ ($b^k$ is a distinguishing extension for $u$ and $v$). If $u$ and $v$ led to the same state in a DFA recognizing $L_n^R$ then so would $u b^k$ and $v b^k$, which is impossible since one leads to an accepting state and the other one doesn't.

Acknowledgement: this example was cited in Wikipedia without explanations. The article gives a reference to an article that I haven't read which gives a tighter bound:
Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata", Theoretical Computer Science 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9.


For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?

Since this is a homework question, I'll just give a hint.

Hint: Let $L_2$ be the set of supersequences of words in $L_1$, i.e.,

$$L_2 = \{x \in \Sigma^* : \exists y \in L_1 . \text{$y$ is a subsequence of $x$}\}.$$

If $L_1$ is regular, what can you say about $L_2$?  Is it regular?  If you have a NFA for $L_1$, can you construct a NFA that would recognize $L_2$?

If you are not sure, try some examples of regular languages $L_1$, and work out $L_2$ looks like for each example.


The professor is asking you to find the lowest r such that the equation is true. At $r=1$, $2^1<17+1$,
$r=2$, $2^2=4<17+2=19$...
$r=4$, $2^4=16<17+4=21$
 and finally $r=5$, $2^5=32\geq17+5=22$.


Does Kernighan-Lin algorithm guarantee its partitions to be a connected graph?

The Kernighan-Lin algorithm tries to find a partition.  As far as I can tell, the partition it finds might or might not be connected; I don't see any guarantee that it will output a connected partition.  There is also no guarantee that it finds the optimal partition.  Even if the optimal partition is connected, I don't think there is any guarantee that the Kernighan-Lin algorithm will output a connected partition.


Natural Language Parser that can handle syntactic and lexical errors

I assume you already know about dynamic programming parsing, aka chart
parsing. This is usually defined for Context-Free grammars (CFG), but
can be extended to other grammatical formalisms, where it can make
more or less sense, depending on the structural complexity of these
algorithms. There are various papers describing chart parsing for
specific formalisms, particularly in the computational linguistic
literature. One general view of the underlying structure common to all
these algorithms is described in a 1995 paper by Lang, and to be found
in the Grune-Jacobs book, relies on a very simple view of parsing as
an intersection of two languages: the first is the singleton regular
language containing the sentence $w$ to be parsed, and the second being
the language $L$ for which we are given a grammar $G$. The idea is
that a single sentence $w$ can always be read as a FSA (or a regular
grammar) as in the following example for the sentence $abac$
$$q_0 \stackrel{a}\longrightarrow q_1 \stackrel{b}\longrightarrow q_2
\stackrel{a}\longrightarrow q_3 \stackrel{c}\longrightarrow q_f$$

Using this FSA $A_w$ and the grammar $G$ of the language $L$ (assume
first $L$ to be a CF language, and $G$ a CFG), the old cross-product
construction due to Bar-Hillel, Perles and Shamir (1961) to prove
closure of CFL with regulr sets can be used with $A_w$ and $G$, and
yield a new CF grammar $G_w$, which naturally generates only $w$ when
$w\in L$, or the empty language $\emptyset$ when $w\notin L$. The
important point is that, when $w\in L$, the grammar $G_w$ generates
$w$ with exactly the same parse trees as the original grammar $G$, up
to a renaming of non-terminal, though the correspondence between
non-terminals is kept (let us ignore details). In other words, we just
described a parser that yield a parse forest $G_w$ from which all the
parse trees for $w$ can be extracted, simply by using the grammar
$G_w$ as a generator.

As it turns out, the dynamic programming chart parsers are just
optimized variants of this very basic construction called parsing as
intersection.

The nice point about it is that it lends itself to many variations.
Closure under intersection with regular languages is a very common
property, so that this is a guide for producing parsers for a great
variety of formalisms, though it makes effective sense only for those
that have a simple generating structure (loosely). Typically it works
very well for tree adjoining grammars (TAG) an other mildly context
sensitive languages.

Another point is that, rather than parse only strings, one can parse
complete regular sets, keeping only the sentences that are also in the
context-free language. And it is largely compatibles with the many
"optimization" techniques commonly found in chart parsing

This is very important in natural language processing (NLP), and
particularly in speech processing, since the result of the first pass
of speech processor to identify the spoken words is usually not a
single string of words, but what is usually called a word lattice
(see Ambiguity and sharing in Natural Language Parsing, which is
actually the title of an answer to a question).

The interesting point is that a word lattice (see diagram in previous
reference) may be seen as a FSA that recognizes all the candidate
sentences (after noise processing) that could be the sentence to be
parsed. But chart parsing can be applied as well, as can the
intersection construction.

Now, it may well be that the word lattice contains spurious words to
be eliminated, or completely garbled sequences corresponding to
arbitrary number of missing words, or misunderstood words. That can be
modeled as a General Sequential Mapping (GSM) that does some editing
on the input sentence, adding, removing or substituting words,
possibly in a (finite) contextual way. Both regular and context free
languages are preserved by GSM mapping. Typically, the editing GSM can
be applied to the word lattice, yielding a new regual language and its
FSA (possibly even with cycles).  Then the parsing process is applied
to that new FSA.  This part is, I think, what you mainly wanted to
describe in the question.

The next point is that not all proposed sentences, or not all
corrections have the same likelyhood. Actually, word lattices may be
weighted structures that give weights to the corresponding sentences
in proportion to some likelyhood they they are correct.

Then the editing GSM can also have weighted transition corresponding
to some standard likelyhood that such error may have occurred.

Finally, the (CF) grammar of the language itself may be weighted.

The dynamic programming construction can use these weight (possibly
probabilities) to determine what are the most likely parses of the
given input according to the grammar used.

Note that I have been skipping the morphological analysis that
recognizes words, and uses similar techniques to end up with the word
lattice.

I am also skipping the use of attributes or feature structures, that
can combine with the process, provided they meet some algebraic
constraints.

The algebraic constraints (that concern also the numerical weights)
are related to the algebraic structures of the grammars themselves.
Typically, a CF derivation backbone (that is more than CF languages)
relies on semiring structures.

A CF rule such as $X\to VXW | aV$ may be read as an equation of the
 form $X = V\cdot X\cdot W \cup \{a\}\cdot W$ where the wariables take
 their values in sets of sentences (i.e. in languages). The domain of
 languages is a semi-ring under the two operations: Union "$\cup$" and
 concatenation "$\cdot$". And a context-free grammar is a specific kind of equation in that domain.

You should find more on this use of semirings in Goodman's "Parsing Inside-Out 1998.

There are some other references in my answer to the question "Is there a favoured data structure for storing ambiguous parse trees
in Natural Language Processing?"


Turing machine - definition of program - naive question

The Turing machine itself is the program.
You can see this in universal Turing machines. A universal Turing machine accepts a description $\langle M \rangle$ of a Turing machine $M$ and an input $x$, and runs $M$ on $x$. Thus $M$ (or rather, $\langle M \rangle$) is the code or program, and $x$ is the input or data.


How to estimate the average time complexity of greatest common divisor?

Since $n\geq x$ in your sum, $O(\log\min(x,n))$ simplifies to $O(\log x)$. Being very careless with constants here, but $$\frac{1}{n}\sum\limits_{x=1}^n f(x)=\frac{1}{n}\left(n\cdot O(\log n)\right)=O(\log n)$$

I'm not sure what this is calculating though; average runtime of all input sizes less than $n$?


In order to prove your result, you don't need to give an algorithm that gets a description of $A$ and $B$ and outputs a description of $f$, a polytime shortening reduction from $A$ to $B$. It's enough to show that for each $A$ and $B$, such an $f$ exists. If a language $B$ is different from $\emptyset$ and $\Sigma^*$ then there is some word $x \in B$ and some other word $y \notin B$, and these are enough to carry out your construction (you don't actually need them to be the shortest word).


Need Help Reducing Subset Sum to Show a Problem is NP-Complete

Here are some hints:

Focus on the case $d = 1$.
Given a target $T$ in SUBSET-SUM, we can change it to a target $T'$ by adding the number $T' - T$; this should work if $T'$ is sufficiently large.
Given a SUBSET-SUM without constraints on the size of the subset, we can get an equivalent problem with such a constraint by adding a suitable number of zeroes to the (multi)set.

If we insist on a set, we need to do more cunning in 3.


Compressing a bit string when I know how many 1s and 0s there are

The operation of translating between combinatorial objects and their indices in some enumeration is known as ranking/unranking (ranking is to convert an object to a number, unranking is the opposite). In your case, you are interesting in ranking/unranking subsets.
Suppose that you are given a subset $S$ of $\{1,\ldots,n\}$ of size $k$, and want to convert it to an integer in $0,\ldots,\binom{n}{k}-1$. If $k = 0$ or $k = n$ then you can just output $0$. Otherwise, we want to put the $\binom{n-1}{k}$ subsets not containing $n$ before the $\binom{n-1}{k-1}$ subsets containing $n$. Therefore:

If $S$ doesn't contain $n$ then you just output the rank of $S$ as a subset of $\{1,\ldots,n-1\}$ of size $k$.
If $S$ does contain $n$, you compute the rank of $S \setminus \{n\}$ as a subset of $\{1,\ldots,n-1\}$ of size $k-1$, and add to it $\binom{n-1}{k}$.

The decoding procedure is very similar. If $k = 0$ you output $\emptyset$, if $k = n$ you output $\{1,\ldots,n\}$, and otherwise:

If the index is less than $\binom{n-1}{k}$, decode it as encoding a subset of $\{1,\ldots,n-1\}$ of size $k$.
Otherwise, subtract $\binom{n-1}{k}$ from the index, decode it as encoding a subset of $\{1,\ldots,n-1\}$ of size $k-1$, and add the element $n$ to the resulting subset.

You can precompute all relevant binomial coefficients to speed things up. In your case, the index is more than 64-bit long, so you will have to work with 128-bit arithmetic somehow, but the resulting algorithm should be reasonably fast.


A dynamic programming problema on containers and product

Here is one approach, I could think of.

$T(x, y) = $ The maximum number of products which could be put into containers if we start at position $x$ in container line, whereas position $y$ in the product line.

If $size(C_x) >= size(P_y)$ we can either choose or skip the container. Else if the size of container is smaller, since we cannot skip the product, we would have to skip the container.

Hence, the recursion would be:
\begin{equation}
  T[x, y]=\begin{cases}
    max(1 + T[x+1,\hspace{1mm} y+1], \hspace{2mm} T[x+1,\hspace{1mm} y]), & \text{if $size(C_x) >= size(P_y)$}.\\
    T[x+1,\hspace{1mm}y], & \text{otherwise}.
  \end{cases}
\end{equation}

Starting from the end of both the arrays, $$max(T[1,i]) \hspace{2mm}: \hspace{2mm} 1<=i<=n$$ should have the required result.

http://ideone.com/3dsrZu


All finite languages can be decribed using a regular expression?

Suppose that a finite language consists of words $w_1, w_2, \dots, w_n$.

Then what do you think the regular expression ^(w1 | w2 | ... | wn)$ matches?


Optimal coverage of a $D$-dimensional grid with small blocks

One unsophisticated approach is to factor $M$, then exhaustively explore all possible decompositions of $M$ into a product of $D$ integers, and see which is best according to your criteria.  I suspect this will prove to be an entirely reasonable solution for your example parameter ranges.

The number of possible decompositions is exponentially large, in general.
If $M=\prod_i p_i^{e_i}$, then there are $\prod_i {D+e_i-1 \choose e_i}$ possible decompositions, which (depending upon $M$) could be rather a lot.

However, for your particular parameter values, the number of possible decompositions will probably still be manageable, so the unsophisticated algorithm should work fine.  If $D=3$ and $M$ is 32 times a random number from 1 to 32, then the number of possible decompositions will range from a minimum of 21 possibilities (for $M=32\times 1$) to a maximum of 252 possibilities (for $M=32\times 30$).  That's small enough that you can easily enumerate all possibilities and see which is best.

If you increase $D$ to $D=7$, then the number of possible decompositions will vary from a minimum of 462 (for $M=32\times 1$) to a maximum of 45276 possibilties (for $M=32\times 30$).  That's still small enough that you can enumerate all possibilities and use the unsophisticated algorithm I mention above.

If you run into some other parameter choices where there are too many decompositions, a simple variant would be to randomly pick a bunch of different decompositions and see which of those is the best.  It's not the fanciest algorithm around, but it's a reasonable thing to try.

Anyway, this should solve your problem for the parameter sizes you mention.


Schedule each entree so that all entrees are completed in the shortest amount of time

The link suggested by @D.W. above put into words exactly what I was looking for, an "exchange lemma" that proves the optimality of the greedy strategy. Here it is:

Suppose we cook in the order $1,2,\ldots, n$. Let $i \in \{1,2,\ldots,n-1\}$ be the smallest integer such that $d_i<d_{i+1}$. We claim that altering the order of the cooking of dishes $i$ and $i+1$, and changing nothing else, results in an equally good or better finishing time. Let us denote $ft(k)$ as the time when dish $k$ is finished under the original ordering (and all dishes are finished at time $\max\limits_{1\leq k\leq n} ft(k)$). We also denote by $ft'(k)$ the time when dish $k$ is finished under the altered ordering.

In general, we have
$$
ft(k) = \sum\limits_{j=1}^k c_j + d_k
$$ since we need to finish cooking dish $k$, which happens after $1,2,\ldots, k-1$, and then finally we dress it.

For the altered ordering we have
\begin{align*}
ft'(i+1) &= \sum\limits_{j=1}^{i-1} c_j + c_{i+1} + d_{i+1}\\
ft'(i) &= \sum\limits_{j=1}^{i-1} c_j + c_{i+1} +c_i + d_{i}
\end{align*}
(the funny ordering is just to emphasize the order in which the dishes are cooked).

The following three facts are easy to prove:

$ft(k)=ft'(k)$ for all $k \neq i, i+1$
$ft'(i)\leq ft(i+1)$
$ft'(i+1)\leq ft(i+1)$

These three together imply that $\max\{ft'(i),ft'(i+1) \} \leq \max\{ ft(i),ft(i+1)\}$ and hence $\max ft'(k) \leq \max ft(k)$ which proves the greedy strategy.


How to prove that a problem is undecidable by using the Halting problem?

When you reduce problem A to problem B, you show that B is at least as hard as A. (It's sort of like a proof by contradiction: if B were any easier, then A would become just as easy.) And undecidability is about as hard as you can get, in computer science.

So what you want to do here is:

Assume you have an oracle for the "fifth state problem"
Show that you can solve the Halting Problem with this oracle

It doesn't matter how long it takes or how many times you call the oracle, for this problem (since all you care about is decidability)

The Halting Problem is undecidable
Therefore, the "fifth state problem" is also undecidable

Here are a few hints to get you started:

You can reorder the states in a Turing machine without really changing anything important
If a TM has less than five states, you can add new "dummy" states that are never used, without really changing anything important
A TM never needs more than one halting state
The question "does this TM halt on empty input?" is a variant of the Halting Problem that is also undecidable


I'd propose this idea:

Let the algorithm run almost naturally, but if it encounters a shortest column that has no options left, do not backtrack immediately. Instead, ignore that column and pick another one. Do this up to four times per iteration. Once more than 4 columns have no options, do backtrack as you normally would.

This will eventually run until a solution is found, in which 4 cells will be left unassigned.

By allowing 4 option-less columns, you place no required knowledge on which columns (cells) should be left unoccupied. The matrix is kept small and tidy as before.

Performance: The search tree probably does not grow too vast, as most of the "stupid" piece placements will trigger the limit within 1 or 2 iterations. Accordingly, the tree should only be about one order of magnitude larger than usual.


This is NP-hard even for weighted complete graphs. For an easy algorithm, you can compute a maximum-weight spanning tree: negate the edge weights and run Kruskal's algorithm. This gives you a performance ratio of 1/3 (a spanning tree has $n-1$ edges, and as you note, a maximum planar subgraph can contain at most $3n-6$ edges). As far as I know, the algorithm in [1] which has a performance ratio at least 25/72 and at most 5/12 has not been considerably improved upon (but see what newer papers reference it).

For complete graphs whose edge weights obey the triangle inequality, the performance ratio of the algorithm in [1] is at least 3/8. The algorithm, I think, is rather involved and can be made to run in $O(m^{3/2}n \log^6 n)$ time on general graphs. There are some simpler variants the authors present as well with different performance ratios, and possibly better runtimes.

[1] Calinescu, G., Fernandes, C. G., Karloff, H., & Zelikovsky, A. (2003). A new approximation algorithm for finding heavy planar subgraphs. Algorithmica, 36(2), 179-205.


Reinforcement Learning: An Introduction, A Gambler's Problem, Exercise 4.7 Solution

The question, as written, certainly suggests that it's a "good policy" to bet a=50 for s=50 , while not "betting it all" with a=49 for s=51.  However, in an e-mail discussion surrounding this (here), Daniel Loeb asks a similar question and notes, "in particular, the simple policy of always making the largest allowed bet is optimal", which would suggest that betting 49 at s=51 would be fine. Andy Barto replies and seems to endorse this conclusion.

Perhaps, if we forget that by construction you can't bet a=51 when s=51, then you could interpret "betting it all" to be betting a=51 when s=51, which is clearly sub-optimal, because your goal is only to reach 100, not to exceed it, and there's no reason to risk complete ruin (loss of the entire stake). So in that sense, it makes sense to "bet it all" when s=50 but obviously not when s>50.  But this is just speculation.


Predicate Logic Notation: What does a "dot" mean?

The dot just means "such that"; it's often omitted.

The difference between the two formulas is the difference between "everybody has a mother" and "there is somebody who is everybody's mother."


Conversion from assembly program to low-level machine language

The first pass can't resolve any forward jumps.  For example:

    cmp r1, 0
    bne label
    add r2, r3, r4

label:
    add r3, r4, r5

On the first pass, when the assembler gets to the bne label instruction, it doesn't know how far the branch needs to jump because it hasn't seen label yet.  On the second pass, it knows where all the branch targets are located and therefore it can go ahead and generate the proper branch/jump instructions at that time.


How does KMV (k minimum value) perform set intersection better than hyperloglog?

There is no sketching algorithm that is able to estimate the intersection cardinalities without accuracy loss. What is meant by the paper is that it is easy to construct KMV sketches that represent the intersection. However, given two $k$-minimum value sketches, you usually cannot construct a $k$-minimum value sketch for the intersection. You rather end up with a $k'$-minimum value sketch with $k'$ smaller than $k$. Since the number of hashes kept within the KMV sketch determines the estimation accuracy, calculating the intersection also comes with accuracy loss.

For HyperLogLog sketches there is no natural way to construct a HyperLogLog that represents the intersection which makes it more difficult to estimate the intersection cardinality. Since HyperLogLogs can be easily merged, a popular way is to use the inclusion-exclusion principle $|A\cap B| = |A| + |B| - |A\cup B|$ to calculate the intersection cardinality. As investigated by the paper, the accuracy loss of this approach is usually much worse than calculating the intersection cardinality for KMV sketches. However, there also exists another (much more complex) technique for HyperLogLogs which uses the maximum-likelihood method and gives better estimates
than the inclusion-exclusion principle, see https://arxiv.org/abs/1702.01284.


What are the justifications and historical reasons regarding the choice between the words 'calculus' and 'algebra'?

What is in a name? Calculus is called analysis in some  languages
other than English, while the word calculus itself means computation.

The name π-calculus was most likely chosen by Milner because it has
to do with computation, and is intended to be for parallel computation
similar to what $\lambda$-calculus is for classical sequential computation.
Computation is actually the original meaning of calculus,
referring to pebbles used as counters in ancient time.

The word algorithm, as everyone knows, comes from the name
al-Khwarizmi (the man from Khiva, a city formerly called Khwarezm), given to the 9th century Persian
mathematician Abū Ja‘far Muhammad ibn Mūsa. Algebra comes from the
name of the treatise Hisab al-jabr wa'l muqabala, that he wrote about
the resolution of equations.

Al-Khwarizmi systematized the study of equations (algebra), and gave
procedural techniques to solve them (algorithms), which implies some form of computation (calculus). Could this be seen
as a kind of Curry-Howard situation, where the mathematics for proving
go in hand with the corresponding algorithms to actually compute ?

Names may be chosen for strange reasons, and their meaning evolves
along with the objects they initially denote. The internationalization of sciences also leads to different interpretations of words, as the same word (or its local variant) may have a different meaning in different country (and that is also true is other areas of language, possibly creating some awkward situations).

This issue has already been discussed on math.SE.

Further remarks

Actually, according to wikipedia, Analysis is used in all languages,
English included, with the same meaning. English appears to use the
word Calculus which refers only to elementary concepts of Mathematical
Analysis, differential and integral calculus. If you look for the
English Calculus in wikipedia, you find out that translation is
missing for many languages (no equivalent entry in German or French
for example), and when an entry is proposed for another language it
may corresponds to a different meaning (Cálculo in Spanish is for
calculation or computation, as it is in some other languages).

However, Cálculo in Portuguese has the same meaning as in English and
covers the same topics. They actually explain, for Portuguese, the
origin of this use of the word, and the explanation is likely to be
the same in English. Calculus is very simply an abbreviation for
"differential and integral calculus". And indeed, it corresponds to
computations expressed with algorithms, and is, in this sense, close
to Algebra.

I was mislead, in understanding the question and writing the first
part of my answer, because I took Calculus to mean the whole of
Mathematical Analysis, as there is no single word in my own language
to cover specifically differential and integral calculus. Comments
show that I am not the only non-american user to be thus mislead.

Hence there is no linguistic inconsistency. The name λ-calculus
denotes a formalisation of algorithms and computation, and the use of
the word calculus is adequate. From it was derived the name π-calculus
for parallel computations.

Note that initially, calculus just means computation (calculation has
a connotation as pertaining to numbers). When applied to a specific
domain, it is qualified so that the domain is explicit (integral
calculus, π-calculus, ...). The problem comes from the fact that it
has a common use in some languages, including English and Portuguese,
where it is domain specific without making the domain explicit, while also retaining its more general use.


How does derandomization of 3SAT work via conditional expectations?

If you choose an assignment at random, each particular clause is satisfied with probability $7/8$. Using linearity of expectation, this shows that if you choose an assignment at random, then the number of satisfied clauses is at least $(7/8)n$. The idea is to have an indicator variable $X_i$ for clause $i$, which states that the clause is satisfied. Since $\mathbb{E}[X_i] = \Pr[X_i] = 7/8$, by linearity of expectation we have $\mathbb{E}[\sum_{i=1}^m X_i] = (7/8)m$. In particular, some assignment satisfies at least $(7/8)m$ clauses.

Let now $X$ be the number of unsatisfied clauses under a random assignment. Then $\mathbb{E}[X] = (1/8)m$, and so Markov's inequality shows that
$$ \Pr[X \geq (C/8)m] \leq 1/C. $$
By choosing an appropriate $C$ you get your first bullet (try it out!).

Regarding the method of conditional expectations, there are many online resources, for example this one (the first hit on a popular search engine). There are many others.

Finally, if $\mathcal{D}$ is a 3-wise independent sample space – this just means that if $(v_1,\ldots,v_n) \sim \mathcal{D}$, then for any $i<j<k$, the joint distribution of $(v_i,v_j,v_k)$ is uniform over all eight possibilities – then it is still the case that each clause is satisfied with probability exactly $7/8$ (why?). Therefore if we choose a random assignment according to $\mathcal{D}$, the expected number of satisfied assignments is exactly $(7/8)m$. In particular, some assignment in the support of $\mathcal{D}$ – that is, an assignment which is generated by $\mathcal{D}$ with some probability – satisfies at least $(7/8)m$ clauses.

Why is this helpful? There are 3-wise independent samples spaces of polynomial size. We can derandomize the random 3SAT algorithm by taking such a sample space and trying out all assignments in its support. One of them will satisfy at least $(7/8)m$ clauses.


An LBA is limited to working only on the space defined by the input. That means it won't ever move right on reading a blank space (if your model doesn't allow writing blank, only a fake blank, that is). That is easy to check by looking at the transitions of the TM.
To check if the language is accepted by an LBA is undecidable by Rice's theorem.


Algorithm for constructing BST from post-order traversal

You are in the right track. But the algorithm is incomplete. You missed the case inserting element on the left sub tree and back.

Here is the modified algorithm: (Changes marked in bold)

  Let $n$ represent the next element to be inserted.

  Let $P(y)$ represent the parent of node $y$.

  Let $g=G(y)$ represent the first node g on the path $y\to root$ such that $P(g)<g$.

  We will read the traversal in reverse. The last element of the traversal is the root. Let $l = root$. $l$ will represent the element last inserted in the BST (except for the 3rd case below- where it will change to the parent). Let $g=root$ tracking $G(l)$, initialize empty stack $stkG$ storing previous $g$'s on current path.
  Loop the following till there's no element left to be inserted

  if $l<n$ then $n$ is the right child of $l$. For the next insertion,
  $l$ changes to it's right child and $n$ becomes the next element(in
  reverse order of traversal ).  Push $g$ on $stkG$, and let $g=l$.
  else, if $l>n$ and $\textbf{P(g)<n}$ then $n$ is the left child of $l$. For the next
  insertion, $l$ changes to it's left child and $n$ becomes the next
  element(in reverse order of traversal).
  else, if $l>n$ and $\textbf{P(g)>n}$ then  $l$ becomes $\textbf{P(g)}$ and pop $g$ from $stkG$.($n$ hasn't been inserted - we loop with $l$ changed)

  [Let $P(root)=- \infty$, so that the $2^{nd}$ case applies]

For correctness, you can prove the following loop invariant:

Root is the first inserted element. for each insertion except root, the parent element has been inserted before.
Each insertion $n$ correctly maintains the order between $n$ and $l$. ($n<l$ if $n$ is left child of $l$, $n>l$ otherwise)
After backtracking step 3, the next insertion always occurs on the left branch.

1 and 3 ensures the post-order traversal, while 2 ensures the BST.

For complexity:

insertion cost: each element is inserted exactly once.
traversal and comparison: the algorithm actually performs a post-order traversal in reverse order, with $O(1)$ comparison on each step.
$g$,$stkG$ maintain cost: each node, which is right child of parent, is pushed and popped from $stkG$ at most once.

Thus the time complexity is $O(k)$.

Alternative algorithm:[1]

Using a recursive procedure:

procedure BST_from_postorder(post, len, target)
/*
input: post[0..len-1] -- (partial) postorder traversal of BST
       len -- length of post to be processed.
       target -- a cutoff value to stop processing
Output: tree_ptr -- pointer to root of tree/sub tree constructed from post[len_rest..len-1]
        len_rest -- remaining length that has not been processed.
*/
 1. if len <= 0 or post[len-1] <= target, then return null.
 2. root <- new Node created from from post[len-1].
 3. (root->right, new_len) <- BST_from_postorder(post, len-1, post[len-1])
 4. (root->left, rest_len) <- BST_from_postorder(post, newlen, target)
 5. return (pointer to root, rest_len)

/* BST_from_postorder(post, length of post, -infinity)
 will return the BST construct from given postorder traversal. */


What do the ∀ and ∃ symbols mean in the Axiom of Choice?

$\forall$ reads as "for all", and $\exists$ reads as "there exists".
So, in english we have

$$\text{"if }\underbrace{\text{for all $x$}}_{\forall x^\sigma}\text{ }\underbrace{\text{exists a $y$}}_{\exists y^\tau}\text{ with $R(x,y)$, }\underbrace{\text{then}}_\to\text{ }\underbrace{\text{there is a function $f$}}_{\exists f^{\sigma\to\tau}}\text{ so that }\underbrace{\text{for all $x$}}_{\forall x^\sigma}\text{ holds $R(x,f(x))$".}$$

I skipped over the $\sigma$ and $\tau$ superscripts, as they indicate types and are not of primary importance here.


Does this program have a runtime of O(N) or O(n*m)

Big $O$ is merely a function that describes an upper bound of another function, so it can be used in different ways.  You can describe the big $O$ of the memory usage of a function, or the big $O$ of the number of operations a function performs.

What you've encountered is simply that, by using different descriptors of the inputs, you wind up with different descriptors of the function itself.  The function you have described is, in fact, linear to the total number of characters in the input.  That statement is not wrong, but $O(nm)$, where $m$ is the average number of characters of the words in a set, is clearly a more useful description of the behavior of the function.