Time complexity of insertion in linked list Apologies if this question feels like a solution verification, but this question was asked in my graduate admission test and there's a lot riding on this:

  What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?

In my opinion, the answer should be $O(n^2)$ because in every insertion, we will have to insert the element in the right place and it is possible that every element has to be inserted at the last place, giving me a time complexity of $1 + 2 + ... (n-1) + n = O(n^2)$

However, the solution that I have says that we can first sort the elements in $O(n \log n)$ and then, we can insert them one by one in $O(n)$, giving us an overall complexity of $O(n \log n)$.

From the given wording of the question, which solution is more apt? In my opinion, since the question mentions "linked list needs to be maintained in sorted order", I am inclined to say that we cannot sort the elements beforehand and then insert them in the sorted order.

The question only says that the target list needs to be maintained in sorted order. It doesn't say anything about any other data structure that you may choose to use. The proposed solution first does some preprocessing of the arguments to insert, then does the insertion proper. This is allowed by the problem statement.

A practical reason to do this, rather than insert the elements then sort, would be if the linked list object is shared with another thread that requires it to always be sorted. (In such a scenario, you'd need to ensure that inserting one element is atomic.) So this question isn't just making strange requirements for the sake of being strange. It's the sort of requirements that come up often in the real world of programming.

Another solution with the same complexity would be to insert the elements into the target list as they come, and maintain a parallel data structure mapping element values to node pointers in the target list. To insert each element, find the preceding element in the mapping, and insert the new element after this node. This assumes that the insertion process creates the list nodes as it goes (as opposed to filling existing blank nodes).

This question is more about reading comprehension than about algorithms. The way it's worded, it's a bit of a trick question. It's somewhat poorly worded because it relies on precise reading, but fails to state some key assumptions, such as the fact that obtaining the elements to insert costs $O(n)$, comparing two elements can be done in $O(1)$, and the input domain is effectively unbounded (exercise: come up with an $O(n)$ algorithm if the inputs are integers in the range $[1,42]$). But the given answer is correct.

You made the assumption that there's no way to use an auxiliary data structure. Nothing in the problem statement forbids using auxiliary data structures. A simple way to forbid auxiliary data structures would be to require $O(1)$ memory overhead.

Note that even under this assumption, your reasoning is wrong, or at least imprecise. If you happened to know that the elements are given in the correct order, you could maintain a pointer to the tail of the list, and keep inserting there, which would take $O(n)$. The worst case is not if every element has to be inserted at the last position in the target list, but at the last position reached when traversing the list in some way. The worst case is indeed $\Theta(n^2)$, but to prove this, you have to prove that finding the insertion point in the list takes $\Theta(n)$ time, and this requires proving that the distance from any pointer you have into the list is bounded below by $\Omega(n)$. This is the case if you have a constant number $A$ of pointers (you implicitly assumed $A=1$, with a single pointer at the start of the list), so that you need to traverse at least $k/A$ nodes after $k$ insertions in the worst case.


Find four sets where each element from those four appears in at least two of those four sets I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array:

$A_i = \{x_{i,1}..x_{i,c_i}\}$
$x_{i,p} < x_{i,p+1}$

$A_i$ has length $c_i$ and the average of $c_i \ll n$. For example in one of the runs, the average $c_i$ ranged from $10$ to $15$ and $n$ from $2000$ to $15000$.

I want to find all combinations of four different arrays $M=\{A_r,A_s,A_t,A_u\}$, where each element that appears in any of the $A$'s, appears in at least one of the other $A$'s:

$\forall A_i \in M: \forall x \in A_i: \exists A_{j \ne i} \in M: x \in A_j$

  Assuming that only a small number of the combinations $\epsilon \ll n
(\ll O(n^4))$
  satisifies these requirements, is there a way to do this
  more efficiently than the obvious $O(n^4f(c))$? Here $f(c)$ is some
  reasonably small function in the average $c_i$.

It's probably viable for me if it can be done in $O(n^2c)$ but not if it's $O(n^3c)$.

If we consider the problem described so far to be the case with $|M|=4$, is there also an efficient algorithm for the case with $|M|=3$?

For the case with $|M|=2$, I can simply add each $A_i$ to a hash set after checking if another $A_j$ with the same values is already in the hash set, with expected time about $O(nc)$.

I'm also very interested in the cases where there's up to $y$ cases of $x_i$ that appear in only one of the sets of $M$, where $y = y'-|M|$ and $y'$ is $4$ or $5$

So where would I use such an algorithm? I'm writing a SAT solver. The idea of the solver is that it looks for an integer solution to an ILP problem (without inequality constraints). I have a rectangular matrix with very small integers (0,1,2 mod 3, without the n=2m constraint and the promise) and bring it into Smith normal form. To reduce the search search space, I look for a small set of rows with a small number of nonzero entries, but such rows could be hidden as linear combinations of the rows in the matrix. However since the matrix is in Smith normal form, a row with 4 nonzero entries can only be a linear combination of up to 4 rows, as any 5 rows have 5 pivots. Each row of the normal-form matrix becomes an $A_i$ in the described problem, with the pivot column removed.

The current implementation on github (first link above) only finds rows with 2 nonzero entries and it takes $O(n^2)$ in the worst case.

Assume set A has an element x. Then you need to add another set B which also has the same element x. Then if there is an item y element of A or B but not both, you need to add a set C contains y. And finally add a set D containing all elements that are elements of exactly one of A, B or C, plus possibly elements common to two of them.

I’d first count for each of the elements how many sets contain it; if x is contained only by one set A, then remove A from the problem. Sort the elements of each set by how many sets contain them. Sort the sets in lexicographic order according to the number of sets containing each element, except sets with fewer elements come later. (So if A contains x and y, both elements of two sets only, and B contains u and v both elements of two sets, and w element of 200 sets, then B comes before A, and both close to the start of the list).

You said that your sets tend to have 10 to 15 elements, then each element will tend to belong to not more than 10 or 15 sets. If you have much more than n different items in total, that number is actually smaller.

Now take the first set A in the list. Take its element x belonging to the smallest number of different sets, and pick each of these sets as the second set B in turn. Take the element y belonging to exactly one of A and B belonging to the smallest number of sets, and pick each of those sets as the third set C. Take the element z belonging  to exactly one of A, B and C belonging to the smallest number of sets, and check all those sets in turn.

In cases where no element is required to be added (all elements belong to two of A, B and C for example), try all possible sets as the next set.

When all possibilities for B, C and D have been examined, remove A, adjusting all the counts. Assuming items don’t belong to more than k sets on average, this should take no more than n k^3 steps.

PS I assumed the number of different items is about the same as n. As long as the number of different items is at least n^(2/3) this will run in O(n^2). Well, roughly.


Finding a maximum-weight base of a a matroid, in reverse Given a weighted matroid with positive weights, we can find a independent set with a maximum weight with a greedy algorithm:

Start with an empty set (by definition of matroid, it is independent).
Add an element with maximum weight among all elements whose addition keeps the current set independent (if there are no such elements, terminate).

My goal is to found out whether this approach can also work in reverse. My first attempt was:

Start with a set containing all elements.
As long as the set is NOT independent, remove the element with minimum weight.

This attempt proved to be false. Here is an example:

There are 8 elements, divided to two groups: A and B. The matroid contains all subsets that have at most two elements of each group. The weights are:

Group A: 303,302,301,300.
Group B: 203,202,201,200.

The forward-greedy approach picks 303, 302, 203, 202 - which is optimal. But the reverse-greedy approach removes 200,201,202,203,300,301, and leaves only 302,303.

But, I think the following alternative algorithm should work:

Start with a set containing all elements.
As long as the set is not independent, remove the element with minimum weight among all elements whose removal leaves a base in the current set.

So, in the above example, this algorithm removes 200 and 201, but does not remove 202 and 203 (since then no base will remain), then removes 300 and 301, and stops with the maximum-weight independent set.

I am not sure about the complexity of this algorithm. Particularly, how much time does it take to calculate whether the current set (after removing an element) contains a base?

Let $M$ be a matroid with non-negative weight function $w$ and rank function $r$ (the rank of a set of points $S \subseteq M$ is the maximal size of an independent subset of $S$). Suppose that the matroid has rank $m$. You propose the following algorithm:

$S = M$.
While $|S| > m$: remove from $S$ a minimum weight element $x$ such that $r(S-x) = m$.
Return $S$.

This algorithm clearly returns a base. Let $W(S)$ denote the maximum weight of an independent subset of $S$. We prove by induction on the steps of the algorithm that $W(S) = W(M)$. The base case is clear. For the inductive step, suppose that $S$ contains a base $B$ of weight $W(M)$, and suppose that we removed an element $x \in S$ to obtain the new set $S'$. If $x \notin B$ then clearly $W(S') = W(M)$. Otherwise, let $B'$ be a base contained in $S'$ (which exists by the definition of the algorithm). Since $|B'| > |B-x|$, there exists an element $y \in B' \setminus B$ such that $B'' = B-x+y$ is a base. By definition, $w(y) \geq w(x)$, and so $$W(S') \geq w(B'') = w(B)-w(x)+w(y) \geq w(B) = W(M),$$
completing the proof.

Answering your question, it is a classical result that the rank function can be computed efficiently using an independence oracle. Perhaps you can come up with the algorithm.


Optimal pairing of points in a set I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the optimal pairing such that the total cost is minimized. What would be a good way/algorithm to solve this?

For example, if you have points $\{a, b, c, d\}$, one possible pairing might be $\{a,d\}, \{b,c\}$. Points can only belong to a single pair.

My Ideas:
The problem seems similar to finding the minimum weighted bipartite matching for a graph. However, I'm not trying to match between two sets of points, just find pairs in a single set. It seems like you might be able to convert this problem to a bipartite graph by duplicating the set of points. This doesn't seem like the right way to do it though (seems like you'd be solving for each pair twice).

You could solve it using an algorithm for weighted matching on general graphs. Just convert the set of points to a complete graph (drawing edges between all possible pairs). It doesn't seem like those algorithms were designed to solve this kind of problem, though (I could be wrong though). So I can't help but wonder if there is a better way to do it.

This problem is the 3-dimensional variant of the Euclidean min-cost perfect matching problem (MCPM), and I don't know if it has been studied.  The general problem (min-cost maximum-cardinality matching) can be solved in time $O(\sqrt n \cdot m )$ [^1].
However, the 2-dimensional version can be solved in time $O(n^{3/2} \log^5 n)$.  Reading the article by Varadarajan [^2], I cannot see any issues lifting the result to 3-dimensional points.
[^1] Micali, Silvio, and Vijay V. Vazirani. "An $O(\sqrt{|v|} \cdot |E|)$ algorithm for finding maximum matching in general graphs." 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). IEEE, 1980.
[^2] Varadarajan, Kasturi R. "A divide-and-conquer algorithm for min-cost perfect matching in the plane." Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280). IEEE, 1998.


Math courses for machine learning I have a few math courses to pick from in my studies, and I would love some insights on which math courses from the following list are the most relevant for machine learning. I will note - to avoid this question being closed on "opinion based" cause, that my question does not involve which math courses I like or interests me, but being objectively as possible - which math courses are the most relevant for machine learning.

This are the following courses I can choose from:

Numerical Analysis
Ordinary Differential Equations 1
Topology
Theory of Functions of a Complex Variable 1
Linear Algebra 3
Number Theory
Probability for Sciences

Since I know Linear Algebra and Probability are very important for Machine Learning, I will note that I have already studied Linear Algebra 1 and 2 (which include matrices, linear transformations, linear and bilinear operators, normed vector spaces, eigenvalues and eigenvectors, diagonalization, Jordan form, hermitian spaces,  unitary and orthogonal transformations, and some more subjects), while Linear Algebra 3 syllabus' is mainly about groups, isomorphism theorems, Lagrange's theorem, group actions, Sylow's theorems, finitely generated Abelian groups, solvable groups, the symmetric group and free groups.

Also, I already had Probability 101 which is mainly discrete probability and includes basic probability theory, discrete distributions (such as Poisson, binomial, HG and more), random variables, markov's and Chebyshev's inequalities,  expected value, variance and covariance, CLT and Markov chains, while the "Probability for Sciences" course has in its syllabus continues distributions, PDF, MGF, convergence of random variables and convergence in probability, the multi-dimensional normal distribution and some more subjects.

I will also note I have studied the following math courses as well:
Calculus 1 and 2 and Discrete Math.

Thanks!

By far the most important in that list is probability -- learn as much probability as you can.  Numerical analysis might also be of a little bit of use.  The others probably won't be directly relevant to most of the practice of machine learning, but hey, become more comfortable with mathematics is probably useful in general.


How to apply Operational Semantics to this function Say I have a function like this:

function colorize(integer) {
  var hex = '#'

  if (integer > 1) hex += 'ff'
  else hex += '00'
  if (integer < 100) hex += 'aa'
  else hex += 'bb'
  if (integer > 10) hex += '11'
  else hex += '22'

  return hex
}

It returns CSS hex colors, not named colors or rgb(...) values or anything else. For now we can ignore the low-level / platform specific details of JavaScript and hardware and just deal with this abstractly as if it was in a perfect environment.

The goal is to use small step operational semantics to prove that it returns a CSS hex color. If it requires too much initialization to do the proof, then assume the initialization is already handled so all that's focused on is the specific function and its implementation.

From my understanding this means we would have some rule for var, =, if, ===, +=, and return. In addition, there is sort of a trace, since it is modifying the value in memory step by step.

From my understanding this would involve using the operational semantics configuration evaluation〈a, σ〉→〈a', σ'〉like:

〈=, σ〉→〈=, σ'[hex ↦ #]〉
   →
〈if (e) x else y, σ〉→〈...〉
   →
   ...

I am not sure how to:

Actually write the configurations out.
Write out the sequence of the evaluations.
Write a proof that the output will be a hex string such as #00aa22 if given 0 for example.

I was wondering if one could point me in the right direction on how to solve this. Basically:

What some configurations look like using this function as an example.
What a sequence of the evaluations (or trace) looks like.
What a proof would entail (not the actual proof as I imagine there will be lots of steps), maybe just the first few steps of the proof.

Thank you very much for your help.

You are looking for Hoare logic. Writing out the answer to the question would pretty much amount to copying the introduction to Hoare logic from Wikipedia. I suggest that you have a look at proving program correctness using Hoare logic, and try to apply it to your problem. It's actually an easy case because there are no loops. If you get stuck, come back and ask a specific question about Hoare logic.

I would break up the problem into proving several properties about hex:

The length of hex is 7 at the end.
The first character of hex is #.
All characters, except the first one, are hexadecimal digits.

Also not that the proof does not require you to write out any operational semantics. You can just use the Hoare logic to argue about your program, and there is a theorem which guarantees that Hoare logic is correct with respect to the standard operational semantics.


Is it decidable whether a linear language contains a square? A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings).

Question: Is it decidable whether a linear grammar generates a square?

What did I do? I know that it is undecidable whether a linear grammar contains a palindrome, and that it is undecidable that a context-free grammar contains a square. Both via reduction from PCP. Given two sequences $(u_1,\dots, u_n)$ and $(v_1,\dots, v_n)$, strings of the form  $u_{i_1}\dots v_{i_k}\#v_{i_k}\dots u_{i_k}$ are linear, whereas those of the form $i_1\dots i_k u_{i_1}\dots u_{i_k}\#j_1\dots j_k v_{j_1}\dots v_{j_k}\#$ are context free.

It is indeed undecidable whether a linear grammar generates a square. Same technique, reduction from PCP.

Starting with the two sequences of strings  $(u_1,\dots,u_n)$, $(v_1,\dots,v_n)$  that define the PCP we can build a linear grammar with strings of the form
$u_{i_1}\dots u_{i_k} j_k \dots j_1 \# v_{j_1}\dots v_{j_k} i_k \dots i_1 \# $.

Rules like $S\to A\#$;

$A \to u_i A i \mid u_i B i$;

$B \to j A v_j \mid j v_j$.

Such a string is a square if both the indices and the strings match, hence iff we generate a solution of PCP.

(I really did not know the answer when I posted the question... Sorry. I started examining ways to show decidability.)


Please provide me a solution of Max-Heapify using Recursion Tree I tried my best to solve the recurrence relation.

$T(n) \le T(2n/3) + \Theta(1)$

Using the recursion tree.

I could reach out the boundary condition when at depth i:

$i= \log_{3/2}n$

Can someone please help me out in adding the costs and taking out the upper-bound.
I know at each depth the cost is increasing by a power of $2$, i:e- $2^i$.

What I have done so far is adding up the costs:

$\sum_{i=0}^{log_{3/2}n-1} 2^i+ \theta(log_{3/2}n)$.

Please correct me if I am wrong.
Thank you.

Try to solve the recurrent by expanding equality case:

$$T(n) = T(2n/3) + \Theta(1) = T(2^2n/3^3) + \Theta(1) + \Theta(1)$$

Now you can see $T(n) = \Theta(\log_{\frac{3}{2}}(n))$. Because each time $\Theta(1)$ is added up to reach to the leaf of the expnasion tree.
Also, you can reach this result using the master theorem.


N songs, M instruments, how to pick K instruments to cover maximal amount of songs I have $N$ songs, $M$ instruments.

Each song requires one or more of the $M$ instruments in order to be played.

My $K-1$ friends and I want to learn to play $K$ different instruments, and we want to pick them such that we maximize the amount of songs we will can play.

How would I efficiently solve this? I'm sure this problem maps to some well known computational problem, but nothing comes to mind at the moment.

I don't know a canonical name for this problem, but unfortunately it's NP-hard, even when every song requires at most 2 instruments.  The upshot is that it's extremely unlikely that any polynomial-time algorithm exists that will solve every instance of your problem.  I'll show this by reduction from the NP-hard problem Maximum Clique, in which we are given an undirected graph $G = (V, E)$ and a positive integer $k$, and asked whether there exists a clique of size $k$ in the graph.

To construct an instance of your problem from the Maximum Clique Instance: Create a song $s_{uv}$ for every edge $(u, v)$ in $E$, and an instrument $t_v$ for every vertex $v$ in $V$, and make song $s_{uv}$ require the two instruments $t_u$ and $t_v$.  Set $K$ (part of the input to your problem) equal to $k$ (part of the input to the Maximum Clique problem).  Now run any algorithm that solves your problem on the just-created instance: if the answer is $\ge k(k-1)/2$ then return YES, otherwise return NO.  (Clearly this procedure could work just as easily with an algorithm that solves the "pure decision" form of your problem, i.e., when a number $r$ is also given as part of the input, and the task is to determine whether it is possible to choose at most $K$ instruments such that at least $r$ songs can be played.)

It is easy to see that, if $G$ contains a clique of size at least $k$, then we must correctly get a YES answer: by assumption, there is a $k$-vertex clique, which comprises $k(k-1)/2$ vertex pairs, each of which are connected by an edge, so choosing the corresponding $k$ instruments satisfies the $k(k-1)/2$ corresponding songs.

In the other direction, suppose that the algorithm for your problem reports that at least $k(k-1)/2$ songs can be played; we need to show that this implies that there is a $k$-clique in $G$.  Given that we permitted at most $k$ instruments to be chosen, there certainly cannot be more than $k(k-1)/2$ songs that we can play, since every song requires a distinct pair of instruments: so we can infer that exactly $k(k-1)/2$ songs can be played.  But every choice of at most $k$ instruments that does not correspond to a $k$-clique in $G$ omits at least one of these $k(k-1)/2$ edges, and thus allows strictly fewer than this maximum possible number of songs to be played; thus the only subgraphs on at most $k$ vertices that can result in at least $k(k-1)/2$ edges are subgraphs that are $k$-cliques.


Indirection in IAS computer From Computer Organisation and Architecture:

  The IAS operates by repetitively performing an instruction cycle. Each
  instruction cycle consists of two sub cycles. During a fetch cycle,
  the opcode of the next instruction is loaded into the IR and the
  address portion is loaded into MAR. This instruction may be taken from
  the IBR, or it can be obtained from memory by loading a word int he
  MBR, and then down to the IBR, IR, and MAR.

Now here, is there part I do not understand:

  Why the indirection? These operations are controlled by electronic circuitry and result in the use of data paths. To simplify the
  electronics, there is only register that is used to specify the
  address in memory for a read or write and only one register used for
  the source or destination.

Can anyone explain this to me more intuitively?  Why is this indirection being used?

the book is describing low level machine language architecture associated with the CPU & what is also known as "microcode". it would be possible to design opcodes that use multiple registers (that does occur in some mostly uncommon cases) but most opcodes generally refer to one register or a memory location, unless its a transfer between two registers. the register number is usually encoded into the opcode in binary. that is, registers serve as a sort of small intermediate "hub" or even a small "cache" between memory and the CPU.

if one had opcodes that refer to multiple registers it quickly leads to a combinatorial explosion where the opcodes become very numerous. even a 2-way register opcode scheme takes roughly $c \cdot r^2$ encodings where $r$ is the number of registers. a 3-way register operation would require $c \cdot r^3$ etc... another scheme is to limit multiway register operations to just a few "privileged" registers, not the full set.

a good case study or example might be the 6502 CPU that has an accumulator, an auxiliary X and Y register, and some limited operations to move between them. a full/general level of register interchange is then supported by stringing several/multiple register manipulation opcodes together.


Chomsky Hierarchy and P vs NP I have read multiple questions here that involve this kind of subject but I haven't found any definite answer. In what class do regular languages belong? (P or NP or some regular are P and other NP), context-free languages? (same question) ,context-sensitive? and general languages? . I personally believe all regular languages belong in P class and the rest (more complex) languages of chomsky hierarchy are in the NP class. Can someone answer and provide some kind of proof for the answer? Thanks in advance.

Regular languages
Regular languages are in $\mathbf{P}$ because a deterministic finite automaton is a restricted deterministic Turing machine that runs in linear time.
Context-free languages
In fact, any context-free language is in $\mathbf{P}$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ [1]. $\mathbf{P}$ strictly includes the set of context-free languages, since $\{a^nb^nc^nd^n\mid n\geq 0\}$ is not context-free but is clearly in $\mathbf{P}$.
Context-sensitive languages
Context-sensitive languages can be parsed in nondeterministic linear space [2]. We don't know the exact relationship between this class and $\mathbf{NP}$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $\mathbf{NP}$. However, showing this would be a major advance in complexity theory as it would imply that $\mathbf{NP}\neq\mathbf{PSPACE}$.
The problem of "Here's a context-sensitive grammar $G$ and a string $w$: is $w\in L(G)$" is $\mathbf{PSPACE}$-complete [2], so certainly every problem in $\mathbf{NP}$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $\mathbf{NP}$ is defined by a context-sensitive grammar, since the $\mathbf{PSPACE}$-completeness result allows arbitrary polynomial-time computation in the reduction and also allows the grammar to depend on the instance. Hopefully, somebody can post a comment or answer clarifying this.
Unrestricted grammars
Unrestricted grammars define all recursively-enumerable languages. This includes all of $\mathbf{NP}$ and includes undecidable languages such as the halting problem, which definitely aren't in $\mathbf{NP}$.

References
[1] L. G. Valiant, General context-free recognition in less than cubic time, Journal of Computer and System Sciences 10(2):308–315, 1974.
[2] Context-sensitive language, Wikipedia.


Maximize entrywise 1-norm of matrix product I have $8$ sets $E_1, \ldots, E_8$, each one of size $256$,  whose elements are $4\times 4$ matrices of (nonnegative) integers. I'd like to design an algorithm to find:

$$\underset{M_1 \in E_1, \ldots, M_8 \in E_8}{\max} ||M_1 \times \ldots \times M_8||_1$$

where:

$$||M||_1=\sum_{i=1}^4\sum_{j=1}^4 M_{i,j}$$

A reasonable time complexity might be approximately $2^{32}$ (time complexity of the naive algorithm is $2^{79}$).

My first idea would be to look for interpretations in various mathematic fields:

geometry: matrix product in an euclidian space.
probability: it reminds me of Markov chains (but the $M_i$ are not normalized).

Is there any known work about this?

Here's one approach, where we prune the set of candidates we examine based on the best combination seen so far.  I don't know how well it will work; you'll probably have to implement and try it to find out.

Suppose we have two sets $S_1,S_2$ of matrices, and we want to find $M_1 \in S_1, M_2 \in S_2$ that maximizes $\|M_1 \times M_2\|_1$.  Here's a plausible  approach.  First, sort the matrices in each set by decreasing value of $\|\cdot\|_1$ norm.  At each stage, we'll keep track of the largest value of $\|M_1 \times M_2\|_1$; let $\ell$ denote that largest-seen-so-far value.  We'll exploit the inequality

$$\|M_1 \times M_2\|_1 \le \|M_1\|_1 \times \|M_2\|_1$$

to prune the set of combinations we need to test.  In particular, we'll enumerate matrices $M_1 \in S_1$ in order of decreasing $\|\cdot\|_1$ value.  For a fixed $M_1$, only need to examine matrices $M_2 \in S_2$ such that $\|M_2\|_1 > \ell/\|M_1\|_1$ (thanks to the above inequality, there's no point in examining the other candidates for $M_2$).  For each candidate pair, we'll compute the value of $\|M_1 \times M_2\|_1$ and update $\ell$ if it is larger than any seen so far.

In this way, we obtain the following algorithm:

Set $\ell := -\infty$.
For each $M_1 \in S_1$, in decreasing order of $\|\cdot\|_1$ norm:

For each $M_2 \in S_2$, in decreasing order of $\|\cdot\|_1$ norm:

If $\|M_2\|_1 \le \ell/\|M_1\|_1$, break out of the inner loop and go on to the next iteration of the outer loop.
Otherwise, if $\|M_1 \times M_2\|_1 > \ell$, set $\ell := \|M_1 \times M_2\|_1$.

What's the running time of this approach, if $S_1$ and $S_2$ are each of size $n$? I don't know.  At worst, it is $O(n^2)$, but one could hope that it might be significantly better -- if we're very lucky, it'll be more likely $O(n \log n)$ (to sort the two sets).

How do we apply this to your problem?  Naively, we can set

$$\begin{align*}
S_1 &= \{M_1 \times M_2 \times M_3 \times M_4 : M_i \in E_i\}\\
S_2 &= \{M_5\times M_6 \times M_7 \times M_8 : M_i \in E_i\}
\end{align*}$$

and then apply the above algorithm.  Here $|S_1|=|S_2|=2^{32}$, so if we're very lucky, this might be efficient enough to apply to your situation.

With a bit more sophistication and implementation complexity, you might be able to apply this recursively.  The above procedure gives a way to enumerate products $M_1 \times M_2$ in decreasing order of $\|M_1 \times M_2\|_1$, given a set of candidates for $M_1,M_2$.  So, you could apply that to $E_1 \times E_2$ and $E_3 \times E_4$ to find $S-1 = E_1 \times E_2 \times E_3 \times E_4$, etc.  You could also use some kind of iterative deepening, to only enumerate combinations such that the norm of their product exceeds some lower bound, and gradually decrease the lower bound as needed.


How is the complexity of algorithms to solve 3CNF (decision problem) specified? For k inputs, the complexity of naive algorithm is O(2^k). I understood this one.

What is meant by "the size of the instance to be solved should be polynomial in k". Is it equivalent to the statement "The number of clauses in CNF of the boolean expression is polynomial in k"?

What should be complexity of a hypothetical efficient algorithm to solve decision version of 3CNF? Can it be called efficient if it is polynomial in the number of inputs and number of clauses?

An algorithm runs in polynomial time if its running time on an input $x$ is $O(|x|^k)$ for some $k$. Here $x$ is a (without loss of generality, binary) string, and $|x|$ is the length of $x$.

For 3CNF it also makes sense to consider the running time as the number of different variables. This is because if there are $n$ variables then there are $O(n^3)$ different clauses. The hardest 3CNF to solve are those in which no clause appears twice, and for such 3CNF, the size of the 3CNF (as a binary string) is polynomial in $n$. Therefore for such 3CNF, an algorithm is polynomial in the input size iff it is polynomial in the number of variables. An additional easy argument shows that 3CNF can be solved in polynomial time in the input size iff it can be solved in polynomial time in the number of variables.


Why is bipartite perfect matching a special case of clique problem? In Lovász writes [1] :

  bipartite graph has a perfect matching, which is a special case of the clique problem

Why is bipartite perfect matching a special case of clique problem?

The Work of A.A. Razborov by L. Lovász (1990)

Let $G=(V,E)$ be the bipartite graph.  Construct a new graph $G'=(V',E')$ whose vertices are the edges of $G$, and where we add $(e,e')$ to $E'$ if $e,e'$ are two edges from $G$ that don't touch each other (don't have an endpoint in common).  Now there's a matching of size $s$ in $G$ if and only if there's a clique of size $s$ in $G'$.  In particular, there's a perfect bipartite matching for $G$ if and only if there is a clique of size $|V|/2$ in $G'$.


What is a computer year? In one of the text book its mentioned that 'running time of this algorithm is 200 computer years'. Can somebody please explain what is the meaning of a computer year?

Computer years, like man hours, are a measure of work. A computer year is the work one computer (of some agreed-upon speed...) performs in a year. 365 computers working in parallel for a day also perform one computer year of work.


"Learning occupancy grid maps with forward sensor models, S.Thurn,2008" a formula that is difficult to overcome I am reviewing the document" Learning occupancy grid maps with forward sensor models, S.Thrun, 2008" (http://faculty.iiit.ac.in/~mkrishna/ThrunOccGrid.pdf)

i am really confused about formula (26), which is merged by formula (22), (24), (25) in an "intersection of probabilities" computed in (22),(24),(25). So, it should be a product of factors in (22),(24),(25). If it is correct, the first factor of (26), 1/sqrt(2*π*σ), should be powered.

any one can tell me why 1/sqrt(2*π*σ) isn't powered?

The vector $c_t$ has exactly one coordinate which is 1, and the rest are 0s. You can check that if, for example, $c_{t,k}=1$, when you substitute $c_{t,k}=1$ and $c_{t,\ell}=0$ for all $\ell \neq k$ in (26) you get (22). The same happens for (24) and (25).


Comparison of Decision Trees: RTED vs MLE I read two papers discussing how to compare between decision trees. One of them is RTED (that is specifically for trees and sub-case is decision trees) can be found here (RTED: A Robust Algorithm for the Tree Edit Distance)here:
and additional approach is COMBINING CLASSIFICATION TREES USING MLE by Shannon and Banks (Shannon, W. D., & Banks, D. (1999). Combining classification trees using MLE. Statistics in Medicine, 18(6), 727-740.). I would like to know if the MLE method is a sub case of RTED algorithm for comparison between decision trees?
"Comparison between decision trees" I mean, given 2 decision trees we would like to compare the structure of them. It means by the location and the name of each node. The RTED transfers the trees into a Bracket Tree Format that contains the names of the tree nodes and compares between the 2 strings. The output is a number that is the Tree distance value (also know in literature Edit Distance).
The question is if the algorithm described by Shannon and Banks (called MLE) is a specific case that is covered by RTED algorithm. If the final result of comparison between 2 decision trees will yield same result. If the answer is No, what are the cases in which the different algorithms will give different results?

The main difference between MLE and RTED is that RTED can compare any kind of decision tree even non binary such as CHAID. In addition, each of them has different approach for scanning the tree. MLE is from top down and find all the possible paths while RTED can go in breadth way.


$A$ nonregular language, is $A\cup B$ nonregular? I was reading this question; regarding whether $L=A\cup B$ is nonregular if $A$ is. As is rightly pointed out in that answer, there is no simple rule. But what if we imposed the following conditions:

$A \cap B=\emptyset$
$A\neq B^C$ and $B \neq A^C$

The examples I know of where $L$ fails to be nonregular is where $B$ somehow "makes up" for the nonregularity of $A$, such as setting $B$ as the language of all strings, or the complement of $A$.

But with these new conditions, is there any way for $B$ to turn the union $A\cup B$ into a regular language?

EDIT: Actually, if $L=\{0^n1^m|n,m\geq 0\}$, then

$$L=\{0^n1^n|n\geq 0\} \cup \{0^n1^m|n\neq m\}$$

and both the conditions above are fulfilled. So $L$ can still be regular. Sorry :)

Here is one result in the direction you're looking into:

  Suppose that $A,B,C$ are languages such that $A$ is a non-regular subset of the regular language $C$, and $B$ is disjoint from $C$. Then $A \cup B$ is non-regular.

For the proof, consider the intersection of $A \cup B$ and $C$. Details left to the reader.

The question you link to concerns the language
$$
\{ a^p : p \text{ is prime} \} \cup \{ w : |w| \text{ is even} \} =
\{ a^p : p \text{ is an odd prime} \} \cup \{ w : |w| \text{ is even} \}.
$$
We can write this in the form $A \cup B$, where $A = \{ a^p : p \text{ is an odd prime}\}$ and $B = \{ w : |w| \text{ is even}\}$. Let $C = \{ w : |w| \text{ is odd} \}$. Applying the result above, we deduce that $A \cup B$ is non-regular (assuming we already know that $A$ is non-regular).


Optimal partition of a set of pairs Suppose we have a set $S = \{(a_1,b_1),...,(a_n,b_n)\}$ where $a_i < m$, $b_i = m-a_i$, $m \in \mathbb{Z}^{+}$, $m>2$ and $n$ is an even number greater than $3$. What is the most efficient algorithm to determine if it is possible to partition $S$ into two distinct subsets, $C$ and $D$, of equal size such that

$\sum_{a \in C} a > \sum_{b \in C} b$   and   $\sum_{a \in D} a > \sum_{b \in D} b$

or  $\sum_{b \in C} b > \sum_{a \in C} a$  and  $\sum_{b \in D} b > \sum_{a \in D} a$  ?

For example, if $S = \{(56,44),(48,52),(43,57),(60,40)\}$, $C = \{(56,44),(48,52)\}$, and $D = \{(43,57),(60,40)\}$.

I am considering iteratively matching a pair with the best value of $a$ with a pair with the worst value of $a$. Is there another algorithm?

If I understood well the problem:

$S = \{ (a_1, m-a_1), (a_2, m-a_2), ..., (a_n, m-a_n),\; m>2 $

$\sum_{a_i \in C} a_i > \sum_{a_i \in C} (m - a_i)$ and $\sum_{a_j \in D} a_j > \sum_{a_j \in D} (m - a_j)$ is equivalent to

$\sum_{a_i \in C} a_i > m * |C| - \sum_{a_i \in C} a_i$ and $\sum_{a_j \in D} a_j > m * |D| - \sum_{a_j \in D} a_j$  is equivalent to

$2 * \sum_{a_i \in C} a_i > m * |C|$ and $2 * \sum_{a_j \in D} a_j > m * |D|$  is equivalent to

$2 * \sum_{a_i \in C} a_i > m * |S| / 2$ and $2 * \sum_{a_j \in D} a_j > m * |S| / 2$  is equivalent to

$4 * \sum_{a_i \in C} a_i > m * |S|$ and $4 * \sum_{a_j \in D} a_j > m * |S|$

Then given an instance of the PARTITION problem $\Pi$, $S = \{ a_1, ..., a_n \}, \sum a_i = 2k$

Add two equal big integers $z >> k$ such that $z = t * (|S|+2) - k + 1$;
the equivalent partition problem $\Pi'$ is $S' = S \cup \{a_{n+1}=z, a_{n+2}=z\}$, $\sum = 2(k+z)$ i.e. the sum of the elements of the two equal partitions must be equal to $k+z$

Now you can set $m = 4*((k+z)-1)/|S'|$ which is an integer: $m  = 4 * ( k + t*|S'| - k + 1 - 1)/|S'| = 4 * (t - 1) * |S'|$ and your problem inequalities become:

$\sum_{a_i \in C} a_i > k+z-1$ and $\sum_{a_j \in D} a_j >  k + z - 1$

And it have a solution if and only if $\Pi'$ has a solution.


Remove duplicates of first elements of pairs A list of pairs is given using Python. I want to remove duplicate occurrences of the first element of the pair leaving only one occurrence of each first element paired with the highest second element it comes with. I am looking for an efficient solution that returns the pairs sorted.

>>> myfunc([[2, 0], [3, 0], [4, 0], [5, 0], [3, 2], [4, 0], [5, 3], [5, 3]])
[[2, 0], [3, 2], [4, 0], [5, 3]]

You can do this pretty easily in $O(n log(n))$ time by using a hash table (such as Python's dict) to map from the first value in a pair to the largest second value it's been seen with.

def myfunc(pairs):
   mapping = {}
   for key, value in pairs:
       if key not in mapping or value > mapping[key]:
           mapping[key] = value
   return sorted(mapping.items())

Hash table lookups take $O(1)$ time on average, so eliminating the duplicates in the loop will take $O(n)$ time. Sorting is (asymptotically) slower, taking $O(n log(n))$ time.


Proof of Program Correctness - Loop Invariants I've been reading a book on using loop invariants and induction to prove program correctness. Then I came across the following program which got me thinking...

Specification for Cube_Root(n)

Pre-Condition: $n$ is a natural number.
Post-Condition: Cube_Root returns a natural number $i$ that is the cube root of $n$ or it returns $-1$ if no such root exists

Cube_Root(n)
  i = 0
  while i < n
    if i * i * i = n
      return(i)
    else
      i = i + 1

  return(-1)

In the book, the proof proceeds by finding a loop invariant.
So for example let us define the following as our loop invariant:

Loop Invariant $P(i)$: $i$ is either the natural number cube root of $n$ or $i \geq n$.
The proof is then supposed to proceed by induction on $i$.
So we need to prove that $P(0)$ is true, assume that $P(i)$ is true for some $i$ and then establish that if $P(i)$ is true then $P(i+1)$ is true.

$P(0)$ is trivial to prove true:
    if $n = 0$ then $i$ is a natural number and the the cube root of $n$
    otherwise $n > 0$ (since $n$ is a natural number) and hence $i < n$.

However, the problem arises when you try to infer $P(i+1)$ from $P(i)$. it doesn't look like you can because if $i$ is not the cube root of $n$, it doesn't tell you anything about whether $i+1$ is or is not the cube root of $n$.

So my question(s) are:

Has it been proven that for any program there exists a loop invariant on which you can
use induction to prove the program is correct?
The loop invariant chosen for Cube_Root is obviously true after the loop terminates
which proves that the post-condition of the program is satisfied. Hence, that proves
partial correctness of the program. However, we did not need to use induction to prove
that. Is that an acceptable proof? If not, how do we use induction to prove Cube_Root
correct?

Generalities

Regarding your first question, the correctness of every loop (without fancy control flow!) can always be proven using a loop invariant which states all the possible values of all variables. In your case (or rather in the modification below), this loop invariant would be
$$ (n,i,r) \in  \{(0,0,-1),(0,0,0),(1,0,-1),(1,1,-1),(1,1,1),(2,0,-1),(2,1,-1),(2,2,-1),(2,3,-1), \ldots \}. $$
Of course, this invariant isn't particularly helpful, though it can certainly be used to prove the correctness of the loop. A more delicate issue is whether we can actually express the invariant in any formal sense - when the loop always terminates as in this case, the set of possible values of the variables is certainly computable.

Regarding your second question, when you're using a loop invariant you always reason by induction - that's how you know that the loop invariant is actually maintained. Consider the following problem:

x, y = 0, 1
for i in range(n):
    x, y = y, x + y
return x

I claim that this program computes the $n$th Fibonacci number $F_n$. Here is a "loop invariant" that can be used to prove it: if $i = n$ then $x = F_n$. Of course, this is not really a loop invariant since you can't prove that it's maintained by the loop; an actual loop invariant is $(x,y) = (F_i,F_{i+1})$.

Your suggested loop invariant is like the first example above - it's simply not a loop invariant, and in particular it's not clear how you'd prove that if the loop terminates then it holds. It might seem "trivial", but this argument doesn't constitute a formal proof. In contrast, if you use an actual loop invariant, then you can use induction to prove that the loop invariant is maintained throughout the loop, and in particular is satisfied if the loop terminates. That's more formal, and can be turned into an actual formal proof (in the sense of program verification or axiomatic logic).

Whether your type of proof is acceptable or not depends on the venue. If this is a question in a course in which you're supposed to learn how to write this kind of formal proofs, then your answer isn't acceptable. In an algorithms class, it might be acceptable since the proof is "obvious". Ask your professor if in doubt.

Specifics

We now turn to the problem at hand.

The idea of a loop invariant is a condition which is true throughout the loop. As you mention, the condition that you describe is only true after the loop terminates (in the return statement). Ergo, it's not the correct condition. First, let's modify the program in the following way: instead of returning $i$, let's have a variable $r$ initialized with $-1$; when $i^3 = n$, assign $r = i$ and break out of the loop. Throughout the loop one of the following is always true, assuming $n > 1$ (for $n = 0,1$ the program fails; the condition in the main loop needs to be $i \leq n$ instead of $i < n$):

$i^3 < n$ and $r = -1$.
$i^3 = n$. In this case, $r = -1$ if the loop hasn't terminated, and $r = i$ otherwise.
$\sqrt[3]{n} \notin \mathbb{Z}$ and $i^3 > n$ and $r = -1$.

The second condition isn't quite of the usual form, and that is because usually break statements are not allowed. You can correct this by modifying the code as follows (this code also corrects the bug mentioned above):

r = -1
i = 0
while i <= n and r == -1:
    if i*i*i == n:
        r = i
        continue
    else:
        i = i + 1
return r

Now the loop invariant becomes:

$i^3 < n$ and $r = -1$.
$i^3 = n$ and $r \in \{-1,i\}$.
$\sqrt[3]{n} \notin \mathbb{Z}$ and $i^3>n$ and $r = -1$.

Now the loop termination condition makes it clear that if $i \leq n$ then necessarily $r \neq -1$, and so by the loop invariant, $r = i$.


Defining a new (informal) operator in CTL If you were given a "new operator" Wh and a formula a Wh b meaning that a holds for at least as long as b does (in all executions). How would you define this operator in CTL? This is an exercise question in the book "Principles of Model Checking" (page 303) if anyone has a copy.

My first thoughts are that I'll definitely need to use the "FOR ALL" quantifier, but I'm not sure where to go from there. So I want to know the thought-process that I should have when dealing with these types of questions more than anything. What I'm looking for is for someone to perhaps give me a walk-through or a very quick guide to solving questions like these.

Thanks in advance for any input.

You seem to be stuck, so here is the answer:

You want $a$ to hold for at least as long as $b$ does. The alphabet consists of $2^{\{a,b\}}=\{\emptyset, \{a\},\{b\},\{a,b\}\}$.

Rephrasing the condition, it means that $\{b\}$ cannot appear before either $\{a\}$ or $\emptyset$ have appeared. Indeed, this is the only violation of the condition.

So once $\{a\}$ or $\emptyset$ hold, you're in the clear. You just need to make sure that until then (sounds familiar?), $\{a,b\}$ holds.

Thus, you have
$$a\ Wh\ b\equiv (a\wedge b)U(\neg b)$$


Find a sequence of $n$ integers with $\Omega(n^2)$ inversions So right off the bat, this is in fact a homework question. I've been banging my head on this problem for hours. From my naive understanding of inversions, I feel that this is not possible.

Considering for $n=1$ elements, there are no inversions, it already seems like this won't work, but maybe it's just for $n > 1$, so we try $n = 2$. And the best I can seem to get is $1$ inversion, where the set is $\{2,1\}$, thus there is one inversion, since $0 < 1$ but $S[0] > S[1]$. The best I can seem to get is $\{n, n-1, \dots, 2, 1\}$, where there are $n(n-1) - 1$ inversions.

Am I missing something in my approach?

Sorta answered my own question in the comments, so I decided to put this here:

If we take any sequence of $n$ integers, in reverse order like $\{n,n-1,\dots, 2, 1\}$. Then each digit $S[i]$ will have $(i-1)$ inversions, and there are $n$ digits.

Thus $I(n) = \displaystyle\sum_{0}^{n-1} n = 0 + 1 + 2 + \dots + (n-1)$. So the total number of inversions will be $I(n) = \dfrac{n(n-1)}{2}$.

Then see, since $n^2 = O\left(\dfrac{n(n-1)}{2}\right)$, $\dfrac{n(n-1)}{2} = \Omega(n^2) $.

Thus $I(n) \in \Omega(n^2)$, and we have a sequence of $n$ digits with $\Omega(n^2)$ inversions.


Intersection of a language with a regular language imply context free Lets say you have a language $L$ and you want to determine if it is context free.
Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is context free?

Meaning, given a regular language $P$, if
$$L \cap P = T$$
where $T$ is context free, is $L$ is context free?

Let $A  =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$
how can I show this is context free? Is the only way to create a PDA or a CFG?

In a nutshell

Using closure with one regular language ($\exists P \text{ regular such
 that }L\cap P$ is context-free)  as apparently envisioned in the
question does not work. Indeed, for any language $L$ there is a
regular language $P$ such that $L\cap P$ is context-free. So there is
no way a family of languages can be characterized by this property,
other than the family of all languages on an alphabet $\Sigma$, i.e.,
$2^{\Sigma^*}$.
Using a more universal closure property with all regular languages
(universal quantification: $\forall P \text{ regular, }L\cap P$ is
context-free) does not work either. But, to prove the context-free (CF)
property for intersection with any regular set, you have to prove it
in particular for the regular set $\Sigma^*$. But $L\cap\Sigma^*=L$,
so that you are back to the initial problem of proving that $L$ is
CF. This is quite simple, and is not further developed below.
The language you are interested in, $A  =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$, is indeed
context-free. A simple way to establish that is to build a
non-deterministic PDA that recognizes it. Intuitively, such a PDA
could first work as if recognizing  $A_1=\{x \in \{a,b\}^{\ast} \mid |x|_a = |x|_b \}$, then switch non-deterministically to the
transitions of a PDA recognizing $A_2=\{x \in \{a,b\}^{\ast} \mid 2|x|_a = |x|_b \}$ while keeping the same stack.
Following site policies, I would also suggest you look at
the reference answers to frequently asked questions on this topic,
and in particular to How to prove that a language is context-free?.

Using closure as proposed in the question does not work

This is an answer to the first question, since you are actually asking
two questions, about using the property of clusre of CF languages with
regular sets. You are actually using the property backward, which is
not permissible.

There is a very simple counter-example. If you take any language $L$, and
any finite subset $R\subset L$, the language $R$ is regular, since all finite languages
are regular, and is also context-free since all regular languages are
context-free. But $R\subset L$ implies $R\cap L=R$. There is always such a subset $R$ since the empty language $\emptyset$ is regular and is a subset of any other language.

Hence for any language $L$ there is a regular language $P$ and a CF
language $T$ such that $L\cap P=T$. You only lave to take $P=T=R$ for
some finite subset $R\subset L$ (including the empty one).

Note that this still works when $L=\emptyset$.

The property you are trying to use is a trivial property, in the sense
that is is true of any language, without exception. Hence, you cannot infer from it alone any specific property that is not equally trivial.

I use finite subsets because they always exists, while some languages do not have infinite regular subset. Infinite regular subsets work too, when they exist.

Proving that your language $A$ is Context-free

$A  =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$

There are various ways a language can be proved to be CF. It is always
possible to do it with closure properties, because of the
Chomsky-Schutzenberger representation theorem ... but that does not
mean it is easy.

My suggestion is to build a PDA, actually a non-deterministic one.  I
have not proved it (so take this with care), but I suspect it cannot
be recognized by a deterministic PDA.

If you had to have as many $a$ and $b$, you would use the stack to
count the extra $a$'s or the extra $b$, so that you can match the
numbers. If you wanted twice as many $b$'s, you would count 2 $b$'s
for one $a$, which you can achieve by pushing two $a$'s on the stack
for each extra $a$, and matching each with a later $b$, or by matching
the $a$ just read with two $b$'s from the stack (I am skipping
details). Since you want something in between, you can arbitrarily decide
for each $a$ whether it matches one $b$ or two $b$'s.

There is however a much simpler solution (at least simpler to explain) which I give in the next section. But I decided to leave this one as it may be instructive too.
So you may choose to skip to the next section.

You also have to be careful that at least one $a$ matches two $b$'s, so
that you have strictly more $b$'s than $a$'s, and that at least one
$a$ matches a single $b$ so that the number of $b$'s is strictly less than
twice the number of $a$'s.

The stack bottom is supposed to be $\$$.
The behavior is the same for all states, which are used only to
remember an $a$ has matched one $b$, and whether another $a$ has matched
two $b$'s.

So you have 4 states: initial $q_0$, then $q_1$ when an $a$ has
matched a single $b$, $q_2$ when an $a$ has matched two $b$'s, and $q_b$
when both have occured, which is a requirement to accept thhe string.

When reading an $a$, you decide non-deterministically whether it must
match one $b$ or two $b$'s, and possibly change the state acordingly.

If you decide for a single $b$:

If the top of stack is $b$, you just pop that $b$
otherwise you push the $a$ on the stack to be matched with a later
$b$.

If you decide for two $b$'s:

If the top of stack is $bb$, you just pop these two $b$
(this can be decomposed into two pops, if your PDA model requires
it, by introducing other states)
if the top of stack is $b$ with no other $b$ in second position,
you pop that $b$ and push an $a$.
if the top of the stack is not a $b$, you just push 2 $a$'s.

When reading a $b$, you just try to match it on the stack:

if the top of the stack is an $a$, just pop it.
otherwise push a $b$ on the stack.

If you reach the end of the input with an empty stack and state $q_b$,
then you accept.

Alternative simpler solution

Actually, you do not need to have a PDA that is non-deterministic
on each input $a$, and you can make a single non-deterministic choice.

The idea is that you start the PDA working as if it were recognizing
 $A_1=\{x \in \{a,b\}^{\ast} \mid |x|_a = |x|_b \}$

Then, after reading at least one $a$, you continue recognition as if
you were recognizing $A_2=\{x \in \{a,b\}^{\ast} \mid 2|x|_a = |x|_b \}$
and must scan at least one $a$ in that phase.

Of course, this is a single PDA. and you do not change the stack as you switch the recognition mode.

You accept on empty stack.

Note that this does not imply that the string recognized is the concatenation of a string in $A_1$ and a string in $A_2$. The string could be all $a$'s followed by all $b$'s, or the reverse, as long as the number of $a$'s and $b$'s is right.


Is there a TM that halts on all inputs but that property is not provable? Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason?

I am wondering if this question has been studied. Note, "unprovable" could mean a "limited" proof system (which in the weak sense think the answer must be yes). I am of course interested in the strongest possible answer, i.e. one that is not provable to halt on all inputs in say ZFC set theory or whatever.

It occurred to me this could be true of the Ackermann function but I am hazy on the details. It doesn't seem like Wikipedia describes this aspect clearly.

Yes. The Turing machine that computes the Goodstein sequence beginning from its input and terminates when the sequence hits zero.  It always terminates but this can't be proven in Peano arithmetic.  I'm sure there are equivalent things for ZFC or any other system you might choose.

Edit For ZF, Hartmanis and Hopcroft show that there's a Turing machine $M$ that rejects every input but that this can't be proven in ZF.  I'm not sure if ZF can prove that $M$ always halts but it certainly can't prove that the machine $M'(x)$ $=$ "If $M$ accepts $x$ then loop forever, else halt" always halts, even though it does.  That still leaves ZFC open but ZF is more powerful than PA.

See Sec. 3 of Scott Aaronson's survey on independence of P=NP for an exposition of the Hartmanis–Hopcroft result and citations to their original papers.


Computing coefficients of $p(x)^n$ in time $O(n \log n)$ For homework I've to give an algorithm that computes the coefficients of the polynomial $p(x)^n$ in time $O(n\log n)$, where $p(x)$ is a polynomial of degree 7.
As an hint I'm told to consider first the case where $n$ is a power of 2.
My guess is that I should use FFT and somehow manipulate it with modulo operations (maybe using the fact that for even powers the unity roots of power $n$ are the same as for $n/2$, only twice) but I'm pretty clueless about this one.

Suppose $n = 2^k$ and for $0\leq i \leq k$, set $p_i(x) = p(x)^{2^i}$. We want to efficiently compute $p_k(x)$.
It is clear that for $0\leq i < k$, $p_{i+1}(x) = p_i(x)^2$. Using the Cooley-Tukey algorithm, knowing $p_i(x)$, we can compute $p_{i+1}(x)$ in time complexity $O(d_i\log d_i)$ where $d_i = \deg p_i = \deg p \times 2^i = 7\times 2^i$.
We can know compute $p_k(x)$ by successively computing $p_1, p_2, …, p_{k-1}$. The total time complexity will be:
$$O\left(\sum\limits_{i=0}^{k-1} i 2^i\right) = O(k2^k) = O(n\log n)$$
Now for the general case where $n$ is not a power of two, you can choose the intermediate polynomials you compute based on the binary decomposition of $n$, like in fast exponentiation.


Convolutional and Linear block codes Both convolution and linear block codes can be used for error correction. The main benefits I gathered from using convolutional codes is that, it's easy to implement and does better (than linear codes) in cases where you have higher error probability rates and noisy channels. Information bits are spread along the sequence. Lastly, these codes have memory.

However, linear block codes, especially the newer ones such as polar code, can actually achieve the channel capacity. And, in block codes, information bits are followed by parity bits and code information in blocks. Lastly, they are memory less.

How exactly can a noisy channel contain "memory?" I've read some articles,
    but would like some more clarification. Right now, I am under the impression that, if we find that an error occurs, with much higher frequency, on the  4th bit, for example, then we shall have some redundancy bit at that location, so no real information is lost. So that when we decode, we simply ignore the 4th bit. Am I right in my understanding?

A memoryless channel is one where the probability of an error at a particular bit is independent of what happened at all prior bit positions.  A channel can have memory if errors are correlated across bit positions.

For instance, consider the following simple binary channel: if there was no error in the prior position, then there is a probability of 0.1 that this position and the next 7 positions are all flipped (have an error); otherwise (with probability 0.9) this position is not flipped (no error).  This would be an example of a channel with memory, because the probability of error for a particular bit depends upon the location of previous errors.  Slightly more generally, bursty errors are an example of a channel with errors.

Note that the question of whether the channel has memory is independent from whether the code has memory.  You can use a memoryless code with a channel that has memory; or use a code with memory with a memoryless channel.


How many pairs of brackets are sufficient to make Brainfuck Turing complete? Brainfuck is a Turing complete programming language that uses only 8 symbols (6 if you ignore I/O).

The two most notable ones that push it to Turing completeness are [and ], essentially Brainfuck's label and goto.

Normally, programs in Brainfuck use multiple sets of [], but I was wondering exactly how many pairs of these brackets have to be used to make Brainfuck Turing complete?

More simply, what is the least amount of brackets that you'd need to simulate an n-state Turing Machine (Give the number of brackets for 1, 2, and three state Turing Machines)?

Notes:

We are assuming an infinite tape and no computational limits.

It is a 2-symbol Turing Machine

I'm not 100% sure that it's impossible to do this with two sets of brackets. However, if the cells of the BF tape allow unbounded values, three sets of brackets are enough. (For simplicity, I'll also assume that we can move the tape head left past its starting point, although because this construction only uses a finite region of the tape, we could lift that restriction by adding sufficiently many > commands at the start of the program.) The construction below requires assuming Artin's conjecture to be able to compile arbitrarily large programs; however, even if Artin's conjecture is false, it will still be possible to show Turing-completeness indirectly via translating an interpreter for a Turing-complete language into BF using the construction below, and running arbitrary programs via giving them as input to that interpreter.

The Turing-complete language that we're compiling into unbounded BF is The Waterfall Model, which is one of the simplest known computational models. For people who don't know it already, it consists of a number of counters (and initial values for them), and a function $f$ from pairs of counters to integers; program execution consists of repeatedly subtracting 1 from every counter, then if any counter $x$ is 0, adding $f(x,y)$ to each counter $y$ (the program is written in such a way that this never happens to multiple counters simultaneously). There's a Turing-completeness proof for this language behind my link. Without loss of generality, we'll assume that all counters have the same self-reset value (i.e. $f(x,x)$ is the same for all $x$); this is a safe assumption because for any specific $x$, adding the same constant to each $f(x,y)$ will not change the behaviour of the program.

Let $p$ be the number of counters; without loss of generality (assuming Artin's conjecture), assume that $p$ has a primitive root 2. Let $q$ be $p(1+s+s^2)$, where $s$ is the lowest power of 2 greater than $p$. Without loss of generality, $2q$ will be less than $2^p$ ($2q$ is bounded polynomially, $2^p$ grows exponentially, so any sufficiently large $p$ will work).

The tape arrangement is as follows: we number each counter with an integer $0 \leq i < p$ (and without loss of generality, we assume that there's a single halt counter and number it $2$). The value of most counters is stored on tape cell $2^i$, with the exception of counter 0, which is stored on tape cell $2q$. For each odd-numbered tape cell from cell -1 up to and including $2^{p+1}+2p+1$, that tape cell always holds 1, unless it's immediately to the left of a counter, in which case it always holds 0. Even-numbered tape cells that aren't being used as counters have irrelevant values (which might or might not be 0); and odd-numbered tape cells outside the stated range also have irrelevant values. Note that setting the tape into an appropriate initial state requires initialising only finitely many tape elements to constant values, meaning that we can do it with a sequence of <>+- instructions (in fact, only >+ are needed), thus no brackets. At the end of this initialisation, we move the tape pointer to cell -1.

The general shape of our program will look like this:

  initialisation [>>>[ >$\times(2^p-1)$ [ <$\times(2p)$ ]>-] adjustment <<<]

The initialisation puts the tape into the expected shape and the pointer on cell -1. This is not the cell to the left of a counter (0 is not a power of 2), so it has value 1, and we enter the loop. The loop invariant for this outermost loop is that the tape pointer is (at the start and end of each loop iteration) three cells to the left of a counter; it can be seen that the loop will thus only exit if we're three cells to the left of counter 2 (each other counter has a 1 three cells to its left, as to have a 0 there would imply that two counters' tape positions were 2 cells apart; the only two powers of 2 that differ by 2 are $2^1$ and $2^2$, and $q$'s binary representation changes from strings of $0$s to strings of $1$s or vice versa at least four times and thus cannot be 1 away from a power of 2).

The second loop repeatedly loops over the counters, decrementing them. The loop invariant is that the tape pointer is always pointing to a counter; thus the loop will exit when some counter becomes 0. The decrement is just -; the way we get from one counter to the next is more complex. The basic idea is that moving $2^p-1$ spaces to the right from $2^x$ will place us on an odd-numbered cell $2^p+2^x-1$, which is to the right of any counter ($2^p$ is the last counter, $2^x-1$ is positive because $x$ is positive); modulo $2p$, this value is congruent to (by Fermat's Little Theorem) $2^x+1$. The innermost loop repeatedly moves left by $2p$ spaces, also not changing the index of the tape cell modulo $2p$, and must eventually find the cell congruent to $2^x+1$ modulo $2p$ that has the value (which will be the cell to the left of some counter); because of our primitive root requirement there's exactly one such cell ($2q-1$ is congruent to $-1$ modulo $2p$, and $2^{\log_{2,p}(r)+1}-1$ is congruent to $2r-1$ for any other $r$, where $\log_{2,p}$ is the discrete logarithm to base 2 modulo $p$). Additionally, it can be seen that the position of the tape pointer modulo $2p$ increases by $2$ each time round the middle loop. Thus, the tape pointer must cycle between all $p$ counters (in order of their values modulo $2p$). Thus, every $p$ iterations, we decrease every counter (as required). If the loop breaks partway through an iteration, we'll resume the decrease when we re-enter the loop (because the rest of the outermost loop makes no net change to the tape pointer position).

When a counter does hit 0, the middle loop breaks, taking us to the "adjustment" code. This is basically just an encoding of $f$; for every pair $(x,y)$, it adds $f(x,y)$ to the tape element which is the same distance left/right of the current tape pointer as counter $y$'s tape location is left/right of counter $x$'s tape location (and then removes the tape pointer back to where it started). Whenever $x\neq y$, this distance turns out to be unique:

The difference between two powers of 2 is a binary number consisting of a string of 1 or more $1$s followed by a string of 0 or more $0$s (with the place values of the start of the number, and the start of the $0$ string, depending on the larger and smaller respectively of $x$ and $y$); thus all those differences are distinct. * As for the difference of a power of 2 and $q$, it must contain at least two transitions between strings of $1$s and $0$s ($q$ contains at least four such transitions, the subtraction can only remove 2), thus is distinct from all differences of two powers of two, and these differences are obviously also distinct from each other.

For $x=y$, we obviously find that the distance moved is 0. But because all $f(x,y)$ are equal, we can just use this as the adjustment for the current cell. And it can be seen that the adjustment code thus implements the "when a counter hits 0" effect for every counter; all the cells that actually represent counters will be adjusted by the correct amount, and all the other adjustments will affect non-counter even-numbered cells (the difference between two even numbers is even), which have no effect on the program's behaviour.

Thus, we now have a working compilation of any program in The Waterfall Model to BF (including halt behaviour, but not including I/O, which isn't needed for Turing-completeness) using only three pairs of brackets, and thus three pairs of brackets are enough for Turing-completeness.


Describe an algorithm for painting cards in the following game It's my first question out here, so please don't judge me too strictly.
I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) painted on cards, while for every pair of cards there's one and only one common object. The game is for two players. At each step each player draws a card and puts it along the card of the other player. The player who is the first to pronounce the common object wins the step and takes both cards. The one who attains all cards first is the winner.

Specifically:
1. There're 50 cards
2. Each card contains 8 different objects
3. There's set of 36 possible different objects (from which 8 objects are chosen)
4. The set of cards has the following property: for each pair of cards there's one (and only one) common object

What I'm asking is how to build an algorithm that chooses the subset of objects to paint on cards.

To make it strict:
Input:{N, O, K},
N-number of cards
O-total number of objects
K-number of objects on a card

Output:
N lines of k numbers each: n_1, n_2, ..., n_N where
n_1= {k1_1, k1_2, ..., k1_K}
n_2= {k2_1, k2_2, ..., k2_K}
....
n_N= {kN_1, kN_2, ..., kN_K}
such that for any i,j<=N exists |n_i X n_j|=1, where X is intersection of sets

It's clear to me, that not for all triples {N,O,K} there's a solution.
No limitations on time/space complexity. All supporting data structures are allowed. Thanks in advance

The Ray-Chaudhuri–Wilson theorem states that the number of cards is at most the number of objects. See for example a paper of Noga Alon (in your case, $L = \{1\}$).


FSA for $(ab)^*(cb^n)^*$ How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$?

An automaton can easily be drawn for the part $(ab)^*$, but the part $(cb^n)^*$ doesn't seem to be regular because if the Kleene closure is taken $\ge2$ times, then it will be of the form $(cb^n)(cb^n)$, which reduces to string matching and is context-sensitive.

This was actually a question, solution to which said that the above language has the following regular expression: $(ab)^*(cbb^*)^*$.

For the correct/sensible interpretation, $(ab)^*(cbb^*)^*$, I will list the states and its corresponding regular expressions below; you can figure out the transitions between the states.

$q_{0}$: $(ab)^*$, start state
$q_{1}$: $(ab)^*a$
$q_{2}$: $(ab)^*(cbb^*)^*c$
$q_{3}$: $(ab)^*(cbb^*)^*$, accepting state
$q_{4}$: for all other strings, rejecting state/dead-end state

For the incorrect/unlikely interpretation, where $(cb^n)^*$ means all words like the empty word, $cb^n$, $cb^ncb^n$ and $cb^ncb^n\cdots cb^n$ for some $n\ge1$, the corresponding language is not regular since its intersection with the language with regular expression $cb^*cb^*$, $\{cb^ncb^n\mid n\ge1\}$ is not a regular language. So there is no FSA for that language.


How to statically type polymorphic lambdas using hindley milner style type inference I am playing with a simple implicitly typed functional language and have implemented type checking using a Hindley Milner style system. In order to guide code generation, I want to tag each term with its type during type inference.

Of course my language uses lambda expressions and the implicit typing should enable nice polymorphic use of those lambdas. Unfortunately, this goal clashes with the static type tagging as each lambda can be tagged only once which specializes it for a particular set of argument and closure types. It is also not possible to statically copy lambdas on each use, as this requires dynamic knowledge.

I thought about dynamically copying and tagging lambdas at runtime but this would involve quite some work and possibly overhead. Is there a standard solution for this kind of problem?

Update 1
The following example might help to clarify my point.

add := func (a, b) begin a + b end
a   := add(2, 3)
b   := add('hello', 'world')

The lambda add has polymorphic type (T1, T1) -> T1 and during type checking add is first instantiated to (Int, Int) -> Int and then to (Str, Str) -> Str, everything fine so far. But, during compilation, I want to have the tree representing add to be annotated with conrete types. Unfortunately, add is a single tree and that tree is either tagged with the first or the second type instantiation.

I could create copies of the add tree for each application but it seems to me that this is only possible at runtime, when the actual target of a call is available. On the other hand, maybe I could somehow let bind copies of the lambda for each instantiation and mangle the type variant into the name? That would entail updating references and I'm not sure whether this is actually possible in general? What about lambda return values, conditionals and so forth?

Update 2
I still feel like I did not describe my problem sufficiently. My language is really rather simple and I would like to stick with a simple typing solution. I found an article series that exactly details my problem and even explores the approaches that I envisioned: type spacialization per application and selecting specialized trees using a structured ler naming scheme.

You should use a polymorphic lambda calculus, e.g. System F for representing typed terms. Then, when you generalize a let binding, you also insert lambdas which abstract over types, and when you check a function application, you also insert type applications as needed. This is precisely what GHC Haskell does, and is the standard solution.

Now, your concrete example does not fit into pure H-M inference, because you seem to be using an overloaded + operation. Unless + is implemented for every type or fails at runtime for some types, (T1, T1) -> T1 is not a valid polymorphic type for add.

For a pure H-M example program, elaborating to System F would look something like the following, with input:

id := func a begin a end
a  := id 'hello'
b  := id 100

And output:

id := Func A (func (a : A) begin a end)
a  := id [String] 'hello'
b  := id [Int] 100

Where I use Func A to mean a lambda binding a type (corresponding to big lambda in System F), and id [String] to mean applying the polymorphic id to a String type. The point of type lambdas and applications is to have an explicit internal representation of polymorphic functions.


Prove that in a tree where each node has 0 or 2 children, number of nodes with 0 child is one more than the number of nodes with 2 children How to prove
In a tree where every node has either $0$ or $2$ children, the number of nodes with $0$ child is $1$ more than the number of nodes with $2$ children.

This can be proven by induction. What you describe is a Full binary tree, and it has a convenient induction definition:

a single node (or leaf) is a full binary tree;
a tree with two children that are full binary trees is a full binary tree.

This permits a structural induction proof of the property you want:

prove that it is true for a single node tree;
suppose that it is true for two full binary trees $a$, $b$, then prove that it is true for the node $N(a, b)$ with $a$ and $b$ as children.


Complexity of an encoded turing machine This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it.

First, we have the variable m which is a binary encoding such as 100#001#010 which is translated to [4, 1, 2]

Next is the variable n = the total length of the input/encoding

And k which is the largest number in the list (4 in the previous list)

Now we set $f(n)$ as the turing machine that took m as input, and want to see if $f(n) = O(g(n))$ where $g(n)$ is a polynomial.

How can I solve this on $f(n) = m (log (n)) (log (k))$?

Your question is rather unclear but I think it's something like this:

  I have a Turing machine and I want to figure out if it runs in polynomial time.  That means that its running time must be bounded by a polynomial function of the input's length. I've figured out an expression for its running time but this expression is in terms of, e.g., some of the numbers represented in the input, and not just the input's length.  How do I proceed from here?

So you've computed a running time that's something like $f(n, x_1, x_2, ...)$ where the $n$ is the input length and the $x_i$ are other quantities associated with the input.  What you need to do is bound how big those quantities in terms of $n$ and then substitute those bounds into&nbsp:$f$, to obtain a function whose only input is $n$.

For example, your input includes a list of numbers. That list could have as many as roughly $n/2$ entries, since it could be $0\#0\#0\#\ldots$.  If the list has just one entry, that number has roughly $n$ bits, so the biggest number in the list could be as big as $2^n$ or so.

In other situations, you might know more about the input.  Perhaps the entries in the list all have to be different.  Then the input can't be $0\#0\#0\#\dots$ and the entries themselves have to get longer than just one bit.  If you had $k$ entries in the list, they'd need about $\log k$ bits each, at a minimum, so you'd have $k\log k\leq n$, which you can try to solve and use.

Then, substitute everything you get into $f$ and see what you get.  For the example you have in your question, it's something like $|m|=\Theta(n)$, $k=\Theta(2^n)$, so $|m|(\log n)(\log k)$ is about $n(\log n)(\log 2^n) = n^2\log n$.


How does "solving" a game like connect four or tic-tac-toe work? To mathematically solve a game you have to prove, using various tehniques, that some player will win, lose or draw the game. Specifically I'm interested in solving games by brute force (trying out all the possible combinations).

If I were to try every possible move for some game I would get a tree of all the moves and each branch of that tree would represent a single game and each node on a branch would represent a move.

The last node of each branch is the finished game. Some will be ties, some will be won and some lost. Now the question is how am I supposed to create a winning strategy from that tree? It basically boils down to: if you know every possible position for a game, how would you go about winning?

It sounds like a trivial question when you say it out loud (and maybe it is), but it just doesn't click for me. Any insights are appreciated.

In  short, minimax is what you're looking for.

We say that a game is valued $1$ if player 1 wins, $-1$ if player 2 wins and $0$ if it's a tie.

You have your brute-forced game tree. At each level you check who's turn it is. If it's player 1's turn, he/she will try to maximize the outcome. If it's player 2's turn he/she will try to minimize the outcome.

So you apply that. Literally. At each node you take the maximum or minimum of the child nodes and assign it to that node, depending on the depth at which you're looking (AKA who's turn it is). Then the value of the root node is the outcome of the game with perfect play.


Matching Lemma with infinitely many symbols I was reading about Universal Turing Machines.

I see that the matching lemma states, that between two symbols X and Y, if there are only 1-s and blanks, then a TM exists, which can count the number of ones.

This is used to match strings of ones between two tapes.

Now I wonder, would there also be a TM or a method of implementation of a TM which can match two strings? To me it intuitively appears, that inifinitely many symbols implies infinitely many states for the machine, and an example workflow may look like:
found symbol X, enter state stateX, exit stateX to state readnextchar if again X was found on the second tape.

Would that not mean an infinitely long transition table? or is there an way to represent a table in a smaller way?

if the symbols are represented via some kind of place value system, e.g. decimal, binary, would that shorten the transition table length?

Turing machines can simulate whatever algorithm you can actually program. So if you can solve your problem by writing a program in C or python (for example), then a Turing machine can also solve your problem.

The most general statement of this principle - everything that is computable can be computed using a Turing machine - is known as the Church-Turing hypothesis. For the specific case of languages like C or python, we know that this hypothesis is true - in principle you can convert every program in C or python to an equivalent Turing machine. The Turing machine would be a lot slower, though. (But only by a polynomial amount!)

For your specific problem, you can allocate a specific location in the tape for your the variables you need, and then update them as you go. The number of states in the Turing machine is proportional (more or less) to the number of instructions in assembly code for your algorithm. Actually programming Turing machines is hard and somewhat pointless. Memory handling is particularly awkward, but Turing machines can implement arrays, tables, and other data structures by allocating special areas on the tape and maintaining them. Perhaps you will hear more about that later in your class.

Finally, for the reason you mention, the tape alphabet is always finite. Without loss of generality, we can assume that it contains only zero and one, though that might make programming the Turing machine even harder. Data structures such as strings and numbers can be encoded in just the same way that they are encoded in your computer - as a string of zeroes and ones.


Algorithmic Complexity of Statistical Estimators This might be very basic but I am interested in evaluating the algorithmic complexity of an estimator of the form:

$$\hat{\theta} = \text{argmin}_{\theta} \;\; Q_n (\theta)$$

where $Q_n(\theta)$ denotes some objective function of interest (e.g. - log likelihood) computed on a sample of length $n$. $\hat{\theta}$ is assumed to be obtain through some numerical optimization methods (typically a stepwise procedure). Under this setting, how could I compute the algorithmic complexity of $\hat{\theta}$?

I am really not sure if this makes sense but here is how I approach this problem:

Suppose that the numerical procedure used to compute $\hat{\theta}$ requires $S$ steps to converge.
Assume that there exist a deterministic function, say $f(p)$, where $p$ denotes the dimension of $\theta$ such that $S \leq f(p)$ and that $f(p) < \infty$ for $p < \infty$.
Assume that $\mathcal{O} (Q_n(\theta)) = g(n)$ for all $\theta$.
Then $\mathcal{O}(\hat{\theta})$ is simply given by

$$\mathcal{O}(\hat{\theta}) = \mathcal{O}(Q_n(\theta) S) = g(n),$$

since $p$ is assume to be fixed (and bounded). This seems really too simple... Any comments would be more than welcome. Thank you very much.

The bound $O(Q_n(θ) \cdot S(p))$ represents only the cost of evaluating $Q_n$ once per step in the "numerical optimization method"; you ignore all other cost that incurs.

Without looking at the whole algorithm, little more can be done.

Note: I very deliberately replaced $S$ with $S(p)$. That is because there is no reason, per se, to believe that $S$ is a constant. You need to be more careful about setting up your cost functions; our reference question may be helpful.


Matrix rank only adding single row I have a dense matrix and a set of rows. I would like to check if adding any single row from the set to the original matrix would make the new matrix rank deficient. Right now I am doing a full LU decomposition each time. This feels wasteful, and I have a hunch that I should be able to keep some information between iterations. Does anyone know of a way to speed this up?

It's unnecessary to perform an LU factorization each time. Instead, you can compute a projection matrix $P$ from your dense matrix. Then, for any vector $x$ in your set, just check if $Px = x$.
In particular, suppose your original dense matrix $A^T$ has all of its rows independent (if it doesn't just delete rows until it does) and you wanted to know if adding any $x$ to the columns of $A$ would increase its rank. Then compute $P = A(A^T A)^{-1} A^T$ once. Here, $P$ projects any vector $x$ onto the column space of $A$, which is the row space of your original dense matrix $A^T$.
Alternatively, you can factor $A = QR$ using either Gram-Schmidt or Householder, in which case you would have $P = QQ^T$.
Then, for every $x$, concatenating it onto the columns of $A$ would increase its rank if and only if $Px \neq x$.


How to construct a running kd-tree? I have a stream of 3-tuples of type (x,y,t) where x and y are in the range 0-127 and t is time, therefore monotonic increasing.

I want to be able to quickly search for points around a query point and think that constructing a kd-tree from the data is a good way to achieve that.

Now I can hardly construct a kd-tree by inserting each new point as, due to the monotonic increasing t, it will inadvertently become unbalanced.

Is there a way to create a "running" kd-tree, that is inserting elements on the one t-side, while dropping elements on the other t-side without the tree becoming unbalanced?

How about a bitwise trie? For 3D, you would interleave the bits of your three values into a single bitstrings, which could be used as a binary key.
The maximum depth is determined by the number of bits. If x, y and t each have 32 bits, the depth is limited to 3*32=96 bits. Usually the depth is much less, because depth is solely determined by the type of data, not by the insertion order. Insertion and deletion time does also not change over time, only with the size of the tree.

The bit-interleaving imposes a z-order on the tree which helps with window queries by roughly translating spatial proximity into neighbourness in the tree.

A Java example, with support for kD-window queries, can be found here (my own code). THis also contains code to do the bit-interleaving, also for floating-point values.

If you do bit-interleaving, it may be worthwhile to transform the coordinates to a similar value range. For example if x and y range from 0 to 10000, then it may be useful to multiply and/or add a constant to t, such that it also ranges from 0-10000 (you can also transform x,y instead). This is not essential. You may also want to use t as the first dimension, because it sounds like you perform a lot of window queries over t to remove old values. Having t as first dimension should improve such queries.

If you are looking for something more sophisticated, especially with more dimensions or large datasets, there is the PH-Tree. It is similar to a bitwise trie, but uses larger nodes like a quadtree, so the maximum depth is more limited. The linked website also links sourcecode and a description, including a performance comparison of kDtree, bitwise tries (critbit tree) and PH-Tree.

Disclaimer: The last part is basically self-advertising, but to the best of my knowledge, the PH-tree may be the best solution in your case, at least if you have large datasets.


Computer Algebra: Algorithms for solving equations symbolically As a hobby, I have written a basic computer algebra system. My CAS handles expressions as trees. I have advanced it to the point where it can simplify expressions symbolically (i.e., sin(pi/2) returns 1), and all expressions can be reduced to a canonical form.  The CAS can also differentiate expressions.

Using this paradigm, what kinds of algorithms are there for solving equations? An equation in my model would be represented as an (=) tree with two subtrees that are the left and right expressions. I know there is no "magic bullet" for solving all equations, but are there algorithms out there that are designed to symbolically solve an equation? If there aren't, what would be the general approach? What kind of classes can equations be split into (so that I might be able to implement an algorithm for each kind)? I don't want to use naive methods and then paint myself into a metaphorical corner.

The are some open source JAVA libraies with complete documentation for math/CAS like:

Jasymca, Java Algebra System and many more.

I think a good way is start with them and try to contribute more!


SMT solves with functions for free varibles So this sounds like this might lead to an undecidable theory but I thought I would give it a try and ask about it after I found nothing on the subject. I am somewhat interested in finding functions which are counter examples to predicates (or solutions to the inverse rather). I would like to restrict the functions to some small class however (possibly even smaller than primitive recursive) so I think there is hope of this working if I restrict them enough.

Has any work been done in this area? Have any tools been written for such things?

SMT solvers do support uninterpreted-functions as part of many logics. If there's a counter-example, then they will also print a "counter-example" function, which will be the predicate you're looking for. If you have a concrete example, we can surely see if one can be coded up using Z3.


Showing Context Free Grammars that are regular if and only if L(G) = Σ∗. Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗.

This is what I have so far

Let N be some language that is known to be context-free but not regular (for example, {a^nb^n | n ≥ 0}). Consider the language L = N#Σ∗ ∪ Σ∗#L(G), where # is some symbol that is not in L(G) or N.

Where to? I just know my prof is going to put this on my exam :s.

This proof-snippet is what you are probably looking for.

We follow your definition. $N$ is a fixed non-regular context-free language over $\Sigma$, $\#$ is a new symbol. For a given grammar $G$ let $L = N\#\Sigma^* \cup \Sigma^* \# L(G)$. Assume $L(G) = \Sigma^*$, then $L = \Sigma^*\#\Sigma^*$ which is a regular language. On the other hand, if $w\notin L(G)$, then $L\cap \Sigma^*\#w = N\#w $, which is not regular (as regular languages are closed under quotient, and $N$ is not regular). Thus also $L$ itself is not regular (as regular languages are closed under intersection).

Conclusion: $L$ is context-free, and $L$ is regular iff $L(G) = \Sigma^*$.


N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its maximum sum is 3 + 4 = 7, and that is the minimal sum possible for a max sum in any pairing. The key to the algorithm is to sort the values from least to greatest. Then pair the least with the greatest, and so on, until you reach the center of the ordering.

Example: 3, -2, 4, 5

Algorithm sorts the values: -2 , 3, 4, 5

Then pairs first with last: (-2, 5)

Then pairs the next available first and last: (3, 4)

Terminates since no pairs left.

This is a greedy algorithm and I am trying to prove that it is always correct using a "greedy stays ahead" approach. My issue is that I am struggling to show that the algorithm's maximum sum is always $\leq$ optimal maximum sum. My intention was to suppose for contradiction that the optimal maximum sum is $<$ the algorithm's maximum sum. But I'm not sure how to find a contradiction. How would this proof go?

Can you see why $\max((-2)+5, 3+4) \lt \max(-2+3, 4+5)$?

The reason is simple. Because on the right hand side, the maximum number 5 is not  paired with the minimum number.

Let the numbers are $a_1\le a_2\le \cdots\le a_n$. Let the numbers be paired in some way.

If $a_n$ is paired with $a_1$, we are done at this round.
Suppose $a_n$ is paired with $a_j$, $j\not= 1$. Then $a_1$ is paired with $a_k$ for some $k\not= n$. So we have two pairs, $\{a_n, a_j\}$ and $\{a_1, a_k\}$. The sums of these two pairs are $a_n + a_j$ and $a_1 + a_k$, the large one of which is $a_n+a_j$.

Let us switch $a_j$ and $a_1$ so that $a_n$ will pair with $a_1$, and $a_j$ will pair with $a_k$. The sums of the two new pairs are $a_n + a_1$ and $a_j + a_k$, both of which is at most $a_n+a_j$, i.e., the large one of them is at most $a_n+a_j$. So after the switch, the maximum sum of the pairs involving $a_n, a_j, a_k, a_1$ does not increase. Since other pairs stays the same, So after the switch, the maximum sum of all pairs does not increase.

Continuing this process, we will make sure the largest number remaining be paired with the smallest number remaining at each round. The maximum sum of the pairs will never increase at each round. After $n/2$ rounds, we will reach the pairing where $a_k$ is paired with $a_{n+1-k}$.

You can see the above approach is indeed the "greedy stays ahead" approach.


Do theorem provers demonstrate their own correctness? I am not very well-versed in the world of theorem proving, much less automated theorem proving, so please correct me if anything I say or assume in my question is wrong.

Basically my question is: are automated theorem provers themselves every formally proven to work with another theorem prover, or is there just an underlying assumption that any theorem prover was just implemented really really well, extensively tested & reviewed, etc. and so it "must work"?

If so, does there always remain some underlying doubt in any proof proven by a formally verified automated theorem prover as the formal verification of that theorem prover still lies on assuming that the non-formally verified theorem prover was correct in its verification of the former theorem prover, even if it might technically be wrong - as it was not formally verified itself? (That is a mouthful of a question, apologies.)

I am thinking of this question in much the same vein as bootstrapping compilers.

I recommend reading Pollack's How to believe a machine-checked proof. It explains how proof assistants are designed to minimize the amount of critical code.

There are many levels of formal verification (that's the phrase you're looking for in place of "proven") of a proof assistant:

Verify that the algorithms used by the proof assistant are correct.
Verify that the implementation of (the critical core of) the proof assistant is correct.
Verify that the compiler for the language in which the proof assistant is implemented is correctly designed and implemented.
Verify that the hardware on which the proof assistant runs is correctly designed and built.
Compute the probability that a cosmic ray passes through the CPU and tricks your proof assistant every time you run it.
Estimate the likelihood that you are insane.

People put serious effort into these (well, at least the first four). For example,
steps 1 and 2 are addressed in Coq Coq Correct!, and steps 3 and 4 in the amazing award-winning CompCert project.


Short and slick proof of the strong duality theorem for linear programming Consider the linear programs

\begin{array}{|ccc|}
\hline
Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} &
\max \vec{c}^T\vec{x} \\
\hline
\end{array}
\begin{array}{|ccc|}
\hline
Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} &
\min \vec{y}^T\vec{b} \\
\hline
\end{array}

The weak duality theorem states that
if $\vec{x}$ and $\vec{y}$ satisfy the constraints then
$\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$.
It has a short and slick proof using linear algebra:
$\vec{c}^T\vec{x} \leq  \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$.

The strong duality theorem states that if the $\vec{x}$ is an optimal solution for the primal then there is $\vec{y}$ which is a solution for the dual and
$\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$.

Is there a similarly short and slick proof for the strong duality theorem?

Probably not. Here is a conceptual argument based on

Farkas Lemma:
Exactly one of the following alternatives has a solution:

  $Ax \le b$ and $x \ge 0$
  $y^TA\ge 0$ and $y^Tb < 0$

Now let $\delta$ be the optimal objective value of the primal.
Let $\epsilon > 0$ be arbitrary.
Let  $A'$ to be $A$ with an additional $-c^T$ as the last row.
Let $b'$ to be $b$ with an additional $-\delta - \epsilon$ as the last value.

The system $A'x'\le b'$ has no solution.
By Farkas, there is a $y' = (y,\alpha)$ such that:

  $y^TA\ge \alpha c$ and
  $y^Tb < \alpha (\delta + \epsilon)$.

Note that if $\epsilon  = 0$ we are in the other alternative of Farkas.  Therefore $\alpha > 0$.

Scale $y'$ so that $\alpha = 1$.
$y$ is dual feasible.
The weak duality implies $\delta \le y^Tb < \delta + \epsilon$.


Using Little's law to find the average N of customers I'm trying to understand Little's law and can't seem to get past this scenario:

Let's say people arrive at the register at 12 per hour. It takes 10 minutes (1/6 of an hour) to service each one of them. The law says that the long-term average number of customers is 12 * 1/6 = 2. After the first hour, my assumption is that there will be 6 customers not serviced. Then after the second hour, there will be 6 more. Why is the long-term average 2 and not the storeCapacity?

Is my usage of the law wrong because I'm not talking about a stable system?

Your intuition was right.  As you hinted, Little's law only applies to a stable system.  This is not a stable system.  The arrival rate exceeds the rate at which customers can be serviced.  Therefore, the number of customers waiting in line will grow without bound, getting increasingly larger as time increases.  That means this is not a stable system.

You can only apply Little's law to stable systems.  Since this isn't a stable system, Little's law doesn't apply.


Is Bitcoin mining NP-Hard? I can't find this anywhere online. Is bitcoin mining NP-Hard?
If so, how would we be able to prove a reduction from a known NP-hard problem? I am a bit lost.

No. Bitcoin mining can be solved in $O(1)$ time. Unfortunately the hidden constant is quite large.