How can I optimize 3 variables in order to maximize the end product? I am in the process of making a cryptocurrency trading bot. Currently, I am doing backtesting over a period of 7 months in which I provide a portion of historical data as if it were in real-life.

By modulating 3 variables: decision threshold, maximum % gain per trade, and stop loss, I want to find the best input values in order to maximize the amount of ending money I have at the end of the backtest.

What would be a good way to go about this? Currently, I'm running each backtest, and changing only 1 variable, but it seems like a slow process and I feel like there has to be a better way to do it. I've heard about neural networks, but I'm not 100% sure this would be a good scenario to apply that here.

This area is known as black-box optimization: you have a function $f(x,y,z)$ where you have the ability to evaluate $f$ on an input of your choice, and you want to find $x,y,z$ that maximizes $f(x,y,z)$.  (Here $x$ is the decision threshold, $y$ is the maximum % gain per trade, and $z$ is the stop loss, and $f(x,y,z)$ is the amount of ending money at the end of a backtest with those parameters.)

There is a broad literature on black-box optimization, with many methods you could try.  See, e.g., Google Vizier, BBComp, and derivative-free optimization; there are many other resources as well.

One last warning: your current procedure is likely to greatly overfit.  If you get a rate of return of 10% on your historical data, that doesn't mean this is expected to give you a rate of return of 10% on future data; the future return rate will probably be far lower, due to overfitting.  If you want to estimate the likely future rate of return, I suggest you split your historical data into a training set and a validation set (e.g., 4 months into the training set, 3 months into the validation set).  Use the training set for the backtesting and to select the parameters.  Then, once you have picked a value for the parameters, you can measure how well it performs on the validation set.  To avoid bias, you're only allowed to use the validation set once -- if you don't like the results you get on the validation set, you're not allowed to go back to the training set and try to choose new parameters.

Personally, I suspect that 7 months won't be nearly enough.  There are financial behaviors that only occur once every few years (e.g., due to financial cycles that occur on a multiple-year horizon), so it's likely that optimizing based solely on 7 months of historical data could lead you to parameters that might perform badly when the situation changes.


Karp reduction from NP-hard problem to unknown problem If I know that problem $A$ is NP-hard, but know nothing of problem $B$ and I know that the following Karp reduction is true:

$$A \to B \, .$$

Is it correct to conclude that $B$ must also be NP-hard?

Short answer, yes. I won't provide an actual proof (you probably saw one in class), but rather, a sort of mnemonic that helps if this comes up on an exam.

A Karp reduction is also known as a polynomial-time reduction. If you can reduce from $A$ to $B$, that means if I give you a subroutine that solves $B$, you can build an algorithm to solve $A$, which does at most polynomial-time work and then calls the $B$ subroutine to get the answer.

The question is now, if you can reduce from $A$ to $B$, and $A$ is $NP$-hard, then is $B$ $NP$-hard?

Assume it isn't. In other words, assume $B$ can be solved in polynomial time. Then that means $A$ can be solved in polynomial time: run the polynomial-time reduction, call $B$ which takes polynomial time, and you have a solution to $A$ in polynomial time. We've proven $P = NP$ and earned a million dollars!

Since we haven't proven anything of the sort, our assumption must be false. In other words, $B$ must be NP-hard.

(Now, this would be a formal proof if $P \neq NP$ were a known result. But it isn't. So while this is good enough to remember on an exam, and the fact that $B$ must be $NP$-hard is in fact true, I haven't actually given a full proof of that fact.)


How to solve a Simple Linear Equation using a binary tree data structure i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so:

        =
     /     \
    +       -
   / \     / \
  x   3   *   2
         / \
        3   x

now that i have the expression in this format could someone please explain how can i obtain the value of x, any help is appreciated and if you have an alternative method that may make it easier i would love to hear it thank you

You don't really want to solve the equation using this representation. You want to convert it into a normal form such as $ax+b = 0$, from which you can read the solution. The first step would be to replace $P = Q$ with $P - Q = 0$. The second step would be to normalize $P - Q$ to some standard form, say a polynomial (or in you case, perhaps $ax+b$). One way to do this is to convert each subexpression into normal form recursively, using rules for handling leaves such as numerical constants and $x$, and mathematical operations such as $+,-,\times$.


How is heap memory allocated to a process? I want to better understand how OS provides heap memory to a process. Here by heap memory I mean the memory allocated dynamically, say by call to malloc.

When a process is newly created, does OS reserve some heap memory for it?
If a process calls malloc, does OS associate a "Page" (from paging concept) with process and then return some portion from that page? And so do later calls to malloc try to provide memory from this page, and if not possible OS associates another page from RAM(or virtual memory)?

Heap allocators typically call a system call to reserve a region of pages and then dole out chunks of that to new, malloc, and other higher-level calls. The system call on Unix used to be brk and sbrk, but implementations sometimes use mmap as well. I think windows uses VirtualAlloc, but it's not totally clear to me.  A good resource for this is Wikipedia's page on C dynamic memory allocation.


Solving distance-d independent set in a simple way I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). So far I have:

Input: undirected planar grid graph $G$, which might not be "full", but be  a subgraph of a full rectangular grid. Also, a natural numbers K (size of independent set) and L (distance).
Represent graph as a adjacency list (or dictionary of adjacency sets, it should be more efficient), since it's sparse (property of planar grid graphs).
Calculate $G^L$ (graph power) with BFS - $O(V*E)$ (complexity explanation)
Solve independent set problem.

The last one has at least a few solutions:

Find independent set with brute force - $O(2^V * V^2)$
Calculate complement of $G$ in polynomial time (I think $O(V+E)$, but I'm not sure) and check if it contains a clique of size $K$, e. g. with brute force, which for fixed K is polynomial - $O(V^K * K^2)$
Since Independent Set and Vertex Cover problems are complementary, find Vertex Cover of size $V - K$; there exists simple algorithm with complexity $O(1.47^{VC size}$) - $O(1.47^{V - K})$

My questions (simple = understandable and "code-able" in less than 1 day for an undergraduate student):

Am I missing something here altogether and should I go other route, without calculating $G^L$, e. g. vertex coloring?
Is there a simple direct independent set algorithm better than brute force?
Am I right that VC is straight up better than brute force clique here?
Wikipedia article on clique problem states that maximum clique can be found by simple enumeration in $O(1.4422^n)$. For my fixed size k, can this bound be tightened? If so, how should I modify the clique enumeration algorithm? Or is there a simpler way?

I'm sorry although I prefer to think of simple answers, ur Q triggers in my mind addressing other problems (a level of a research topic not an under graduate task)

Anyways, here is what popped up in my mind just incase u find something inspiring in them

-About the Kth Largest Subset problem http://dx.doi.org/10.1016/j.ipl.2015.09.015

-About Goemetric Set Packing problem
(I myself didn't study it a lot, but read some papers about it when someone suggested it to me. I did not use it in my work, but the way u r trying to describe ur problem tells it has a Goemetric landscape nature so maybe it will be useful for u)

https://www.sciencedirect.com/science/article/pii/S0925772112000740

https://slideplayer.com/slide/4514539/

I have more resources if u need so

.

Finally, u may search for exact MWIS algorithms and u'll find a lot. Here is one paper
"Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs", Sebastian Lamm
, Christian Schulz, Darren Strash, Robert Williger, Huashuo Zhangk.
arXiv:1810.10834v1 [cs.DS] 25 Oct 2018


Behavior of specific PDA for a certain input Suppose we're given the non-deterministic PDA shown below which reads from the alphabet $\sum = \lbrace a,b \rbrace$. How will this PDA behave if we pass it the string $ba$? We read $b$ first and push $b$ to the stack, but when we read $a$ I get confused. My assumption is that we fork into two new branches - one in which $b$ was popped and one in which $a$ was pushed. Is this correct? If not, can you tell me where I go wrong?

Thank you very much!

This PDA is non deterministic. So just like in non-deterministic Finite State Machines you fork.

A string is only accepted by the PDA if one of the forks ends in an accepting state.


what is routine induction? I read a paper which mentioned routine induction many times.
But when I google it, there are nothing showed up.

I think routine induction means the induction on the structure, analyzing possible cases in proofs.
am I right?

Just to make sure, I am asking it here.

The word routine is used here in its non-technical sense: normal, usual, plain. It just means a proof by induction where nothing special happens.


Minimize number of DFS searches in a graph I got a weird homework question about graph.

A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed however the helicopter won't know beforehand. Once the the helicopter lands on a house u, they can drive to any neighboring house v if the road (u,v) is not destroyed. The rescue team would only know if a road (u,v) is destroyed or not after they arrive at either u or v. They also don't know the number of safe roads in advance. Design a strategy to minimize the number of helicopter landings, also the plan needs to have less than 2n trips along the safe roads.

My thinking is to do a DFS search on a random unvisted node. After the DFS is done, if there are still unvisited nodes, then do another DFS search from a random unvisited node again. Repeat this until all the nodes are visited. However, I don't know how to prove that this minimize the number of searches. Can anyone help me? Thanks!

Your problem has two clauses:

A) Given a set $V$ of houses, decide on the set of existing edges $\{(u,v)\}$ with a minimal amount of queries (=helicopter landings), when a single query $Q(v)$ reveals all the edges $(v,u)$.

B) Given a graph $G=(V,E)$, find a path that visits all vertices, that traverses at most $2n$ edges.

The connectivity problem A has a trivial solution of $O(n)$, which under the model you describe can be easily bounded below by an adversary argument, showing it is also optimal.

Consider the following adversary:

Choose arbitrary $v_k$ that was not queried before.
Given query $Q(v_i)$:

If $i$ has been asked before, answer accordingly
If $i$ is new and $i \neq k$ answer that $v_i$ is only connected to $v_k$
If $i$ is new and $i = k$ answer that $v_i$ is connected all previous vertices connected to $v_k$ through previous phase, and to a new vertex $v_j$. Set $v_k \leftarrow v_j$

It is clear any query connects at most $1$ vertex (beside the very first), so regardless of the order of queries an algorithm makes, it must make at least $n-1$ queries to reveal the set of edges, and the connectivity status of the graph.

It follows the naive algorithm of asking all vertices for neighboring edges is also optimal.

The traversal problem is simple; find a spanning tree of $G$ (denoted by $T$), after its been revealed by your helicopter. To visits all vertices, do an euler-tour on $T$. Since $T$ has $n-1$ (or less, if it's a spanning forest and $G$ is not connected) edges  and an euler tour visits each edge twice, you visits all vertices at the maximal cost of $2n-2$ edges.


is (infinitely often p) ∨ (infinitely often ¬p) valid? i'm trying to prove every trace over PROP = {p} is a model of the formula.
I am very stuck in figuring out a model pi that satisfies this formula, can anyone point me in the right direction?

The LTL formula for the given problem could be: $G(F(p)) \lor G(F(\lnot p))$. Consider a $\omega$-word $w = w_1w_2w_3 \ldots$ over $\{\{\}, \{p\}\}$:

Let $w_i = w_iw_{i+1}\ldots$
\begin{align*}
& \; \; \; \; \; \;  \; \; \; w \not\models G(F(p))\\
&\implies \exists i . w_i \not\models F(p)\\
&\implies \exists i. \forall j \geq i . w_j \models \lnot p\\
&\implies \exists i. \forall j \geq i . w_j \models F(\lnot p)\\
&\implies \exists i. w_i \models G(F(\lnot p))\\
&\implies w \models G(F(p)) \lor G(F(\lnot p))
\end{align*}

Therefore, $G(F(p)) \lor G(F(\lnot p))$ is valid.

Note that this doesn't mean that $G(F(p)) \land G(F(\lnot p))$ is not satisfiable. For example, consider the word $w=\{p\}\{\}\{p\}\{\}\{p\}\{\}\ldots$


Finding a 4-clique among $k$ node groups Given a connected graph $G = (V,E)$, assume that there are partitions $\{p_0, p_1, ..., p_k\}$.
Denote the partition set of a vertex $v \in V$ as $p(v)$.
The neighborhood of a vertex $v$ is denoted as $N(v)$

I need to find a 4-clique $V' = \{v_0, v_1, v_2, v_3\}$ such that the total degree of $V'$ is maximum and $\forall v_i, v_j \in V', p(v_i) \neq p(v_j)$.

Is this an NP-Hard problem?

The most straightforward method that comes to my mind is:

pick $v \in V$ with maximum degree.
pick vertex $w \in N(v)$ with maximum degree
pick vertex $u \in N(w) \bigcap N(v)$ with maximum degree
pick vertex $x \in N(u) \bigcap N(w) \bigcap N(v)$ with maximum
degree

Is there any more efficient way to do this?

First of all, the greedy strategy you outlined does not work. It may be possible that the node with highest degree is in a clique with lower total degree than the clique with the maximum degree.

Second, this problem is clearly in P because we can simply check all $\binom{n}{4} = O(n^4)$ cliques, checking they meet the partition requirement, and keeping track of the one with largest total degree. It's possible there's a more efficient algorithm though, especially considering this naive one does not use the partition information to rule out any cases.


Suggestions for Short Examples Contrasting Functional Programming Languages A fellow student and I are writing a paper on functional programming for a programming languages course, part of which will be comparing and contrasting Lisp (Scheme), ML (SML), and Haskell. We'll be coding the same algorithm in each language and we're at a bit of a loss for exactly what to code. We would be grateful for some suggestions for algorithms that fit the bill (described below). We'll work out the code---we're just looking for suggestions. But if there's a particular tricky point or useful idiom we'd welcome a heads-up.

We envision the code being about a page. In particular, the professor wants something more substantial than a line or two. To the degree possible, we'd like to use this to contrast the styles of the three languages and at the same time showcase the benefits of functional programming. I considered quicksort, but the standard Haskell code is just a line or two.

I would have tagged this with "homework" and "soft question" (as well as "ML" and "Haskell"), but those tags don't seem to exist. Also, I wasn't sure whether Computer Science or Stack Overflow was the right place for this, but decided on Computer Science because we're not really looking for worked-out code or solutions to a particular coding problem. Instead we're looking to demonstrate the benefits of the functional programming paradigm and three important branches thereof.

Project Euler has nice problems for showcasing the core of a programming language.
An important part of a programming language are user defined (container) data structures. Bread and butter containers include random access arrays, bidirectional lists, hash tables, and search trees. You may take the implementations from standard libraries of the languages to get interesting real world programs for you comparisons.
A strong point of functional programming languages is that they allow modular reuse of standard algorithms. The C++ stl header algorithm provides a nice collection of those reusable standard algorithms.


Testing whether a tetrahedron lies inside a Polyhedron I have a tetrahedron $t$ and a polyhedron $p$. $t$ is constrained such that it always shares all its vertices with $p$. I want to determine whether $t$ lies inside $p$.

I would like to add one detail to the problem in case it may contribute to the solution: $t$ is a Delaunay tetrahedron and faces of $p$ are triangular and are strongly Delaunay both with respect to vertices of $p$. A tetrahedron is Delaunay if circumsphere of its vertices contains no other vertex inside it. A face is strongly Delaunay if there exists a circumsphere containing vertices of that face on its surface but no other vertex on or inside it.

Following figures show the same problem in $2D$ space:

The original polygon $p$:

Delaunay triangulation of vertices of $p$:

Result of inside/outside test over triangles $t$(Shaded triangles are inside $p$ and rest are outside):

Desired result(pruning outside triangles):

My original problem is in 3D space so triangles $t$ in above figures translate to tetrahedrons and polygon $p$ translates to an arbitrary polyhedron $p$. I have figured out some formulations of this problem:

Formulation 1
The only parts of $t$ which can be outside $p$ are its edges and triangular faces but in general there may exist a $p$ which has edges of all outside $t$'s on its surface, so alternatively, this problem may also be formulated as to test whether for a tetrahedron $t$ there exists a face which lies outside $p$?

Formulation 2
I have another possible perspective towards this problem but lacking any formal idea:
Geometrically, if $t$ is outside then it will always be sticking on the outer surface of $p$. So if we can compute the contours(informally, the outer boundary)  $C_{V}$ and $C_{V_{p}}$ such that $V=V_{t}\cup V_{p}$ and $V_t,V_p$ are sets of vertices in $t,p$ respectively, then $C_{V}=C_{V_p}$ iff $t$ lies inside $p$.

I would like to know:

How can I solve either of Formulation 1 or Formulation 2?
Or, is there any completely different approach to solve this?

Update:
I now realize that this problem can be reduced to Point in polyhedron problem. Since an outside tetrahedron $t$ will have at least one face which lies outside $p$, so any arbitrary point on that face(except its vertices,in general) will always lie outside $p$. Therefore, for each face of $t$, I need to take an arbitrary point and test if that point lies outside $p$.

From point in polygon article I came to know about Ray casting algorithm and Winding number algorithm. Ray casting is not numerically stable for cases where point lies on the surface of $p$. But numerical robustness of Winding number algorithm has not been addressed there.

Based on above, my core problem now seems to be(please suggest if it should be asked as a separate question):
Is there any numerically robust algorithm for point in polygon problem?

I recently found one solution to this problem in a paper 'Robust inside-outside segmentation using generalized winding numbers' by Alec Jacobson et.al., here. It solves the problem of locating if a point is inside(or outside) an arbitrary(one with self-intersections, non-manifold, open-surfaces etc.) polygonal mesh using the notion of generalized winding number.

Problem can be solved if I compute the generalized winding number of the centroid of $t$ against the surface of $p$.


Non-reducible Unsatisfiable 3SAT instance example Can someone provide with the smallest (as small as possible) 3SAT example (w.r.t. number of variables and the number of equations) that is:

Unsatisfiable.
Not provable unsatisfiable by simply reduction (successive simplification and rewriting) of the equations by the process similar to as described below:

Example:

Assuming a 3SAT Problem that includes 4 equations:

~a + b + c  = 1
~a + ~b + c = 1
b + d + ~e  = 1
b + d + e   = 1

(1. and 2.) combined can be replaced with ~a+c=1.
(3. and 4.) combined can be replaced with b+d=1.
and so on..

Thus, we require a problem instance where such a successive reduction/simplification of the equations (containing either 2 or 3 variables) in the given problem do not automatically lead to the conclusion of unsatisfiability.

Resolution is a complete proof system for contradictions: if a given set of clauses is contradictory, then this fact is provable using resolution.

Since Resolution exactly corresponds to your "simple reduction", it follows that your question cannot be answered.


A Myhill-Nerode type characterization of the regular languages using fooling sets? Ultimately, my question is whether it's possible to exactly characterize the regular languages in terms of fooling sets. To help explain my motivation for asking this, here's a quick exposition.

Let $L$ be a language. A set of strings $S$ is called pairwise distinguishable relative to $L$ if for any two distinct strings $x, y \in S$, there is a string $w \in \Sigma^*$ such that exactly one of $xw$ and $yw$ belongs to $L$.

Assuming the axiom of choice, the Myhill-Nerode theorem can be framed in terms of pairwise distinguishable sets:

  Theorem: let $L$ be a language. Then $L$ is nonregular if and only if there is an infinite set $S$ that is pairwise distinguishable relative to $L$.

Now, let's consider a related definition. If $L$ is a language, a set $S \subseteq \Sigma^* \times \Sigma^*$ is called a fooling set for $L$ if for any distinct pairs $(x_i, y_i), (x_j, y_j) \in S$, then $x_i y_i \in S, x_j y_j \in S$, and at least one of $x_i y_j$ and $x_j y_i$ isn't in $L$.

I'm curious whether the following statement is true:

  Conjecture: let $L$ be a language. Then $L$ is nonregular if and only if there is an infinite set $S$ that is a fooling set for $L$.

I can prove one direction of this using the Myhill-Nerode theorem: if there is an infinite fooling set $S$ for a language $L$, then we can take the first halves of each pair in $S$, gather them into a set $S'$, and we'll have an infinite set $S$ that is pairwise distinguishable relative to $L$, so $L$ is nonregular.

However, I keep getting stuck trying to go the other way. I'm not sure how to show that if $L$ is nonregular, then there must be an infinite fooling set for $L$. The equivalent direction of the Myhill-Nerode theorem follows by the contrapositive and the fact that the binary relation "is indistinguishable relative to $L$" is an equivalence relation. We don't - I believe - have a similar equivalence relation when it comes to fooling sets.

Does the other direction of implication hold here? Or is this a strictly weaker criterion than the Myhill-Nerode theorem?

Thanks!

Your conjecture is refuted by the language $\{ 0^n : \text{$n$ is not a power of $2$}\}$. Let $\{(x_i,y_i) : i \in \mathbb{N}\}$ be an infinite fooling set for this language. We can identify $x_i,y_i$ with integers. These pairs have to satisfy the following conditions:

$x_i + y_i$ is not a power of $2$.
For each $i \neq j$, either $x_i + y_j$ is a power of $2$ or $x_j + y_i$ is a power of $2$.

Color $\mathbb{N}^2$ with two colors according to whether $x_i + y_j$ is a power of $2$ or $x_j + y_i$ is a power of $2$, where $i < j$. Ramsey's theorem shows that without loss of generality we can assume that for all $i < j$, $x_i + y_j$ is a power of $2$.

If $x_i = x_j$ for $i < j$ then $x_j + y_j$ is a power of $2$, contradicting (1) above. Similarly, if $y_i = y_j$ for $i < j$ then $x_i + y_i$ is a power of $2$, contradicting (1) above. Thus all $x_i$ are distinct and all $y_j$ are distinct.

Assume without loss of generality that $x_1 < x_2$. Let $x_1 + y_3 = 2^a$ and $x_2 + y_3 = 2^b$. Choose $j$ so that $y_j > 2^b$. Let $x_1 + y_j = 2^c$. Then $2^c < x_2 + y_j < 2^c + 2^b < 2^{c+1}$, and we obtain a contradiction.


Returning two array indices in an array for a given value Give an algorithm that takes as input an array A sorted in non-decreasing order, and a value x, and that returns two indices (F and L) into A, where A[F] is the first value equal to x and A[L] is the last value equal to x. Your algorithm should run as fast as possible in the worst case. State the worst case running
time of your algorithm.

A O(n) algorithm is very easy for this. A for loop running on the input array could easily find F,L. I think for sure there is a better algorithm. I am thinking of modifying binary search to search for the same value repetitively. I think O(logn) might not be possible, but something like $O(log ^2 n)$ might be. I am unable to come up with a precise algorithm that achieves something like this running time.

Yeah, bisection'll maximize the information gained from each check.  If you do any sort of check other than bisection, then in the worst-case, the sought element'll be on the larger section of the selected divide.

The worst-case scenarios will occur whenever bisection has to happen $O\left(\log{n}\right)$ times to find the first/last indices of the selected value, x.  For example, if the array's all the same value, e.g. A=[0,...,0], then bisection'll have to occur until the algorithm whittles it down to the first 0 at $i=0$, then a separate bisective search would have to go just as many times to find the last 0 at $i=n_{\mathrm{length}}-1$.

Both searches'll be $O\left(\log{n}\right)$.  But since two sequential $O\left(\log{n}\right)$ processes are still just $O\left(\log{n}\right)$, the overall algorithm's $O\left(\log{n}\right)$.


Reducing the vertex cover problem to a variation of the vertex cover problem The following variation on the vertex cover problem was given:

  Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$?

I was asked to prove that this problem is also $\mathsf{NP}$-hard. I am pretty sure that this can be done by using Karp-reduction from the original vertex cover problem to this variation.

That means that I would need some transformation function $f$ that would transform an instance of the vertex cover problem, $I = (V, E, k)$, to an instance of the above described problem, $f(I) = (V', E')$.

I am not sure how to come up with the proper transformation function, but this is what I think have figured out:

Let $V = \{v_1, v_2, ..., v_n\}$.
Let $V' = V \cup V^+$, where $V^+ = \{v_{n+1}, v_{n+2}, ..., v_{4n}\}$, because this would mean that the total size $|V'| = 4 \cdot |V|$.
Let $E' = E \cup E^+$, where $E^+ = \{\{v_i, v_j\} \mid v_i \in V, v_j \in V^+, j \in \{n +i, 2n+i, 3n+i\}\}$. Basically, this means that each vertex in $V$ is connected to three different vertices in $V^+$ such that all vertices in $V^+$ are connected to exactly one vertex in $V$.

However, I am having a hard time proving the correctness of this reduction. I think I messed up the generation of $E'$, which would make the transformation function wrong. Anyone have an idea what the actual transformation function could be?

One note is that you'll have to use $k$ in your transformation.

Here's one approach that I think works:

We want some $G' = (V', E')$ that has a vertex cover of size $\le \frac{|V'|}{4}$ iff $G$ has a vertex cover of size $\le k$.

If $k = \frac{|V|}{4}$, just set $G' = G$.

When $k \neq \frac{|V|}{4}$, one idea is to add a disconnected graph $H$ to $G$, where we know the vertex cover size of $H$.

Case 1: $k > \frac{|V|}{4}$. Then we want to add a graph with a small vertex cover. A star graph should do it. A star graph $H$ with $m$ vertices has vertex cover size $1$.

Set $G' = G \cup H$, a graph with $|V| + m$ vertices. It has vertex cover of size $\le k+1$ iff $G$ has a vertex cover of size $\le k$.

What should $m$ be? Let's solve

$$\frac{k + 1}{|V| + m} = \frac{1}{4}$$

This gives $m = 4(k+1)-|V|$. So when $k > \frac{|V|}{4}$, add a disconnected $[4(k+1)-|V|]$-vertex star graph to $G$, and call the $\frac{|V|}{4}$ vertex cover algorithm on that. $\square$

Case 2: $k < \frac{|V|}{4}$, we can add a complete graph with some properly chosen number $m$ vertices*. Will leave it at that.

*In this case when you solve for $m$, $m$ may not always be an integer; this can be dealt with by adding a $\lceil m \rceil$-vertex complete graph, which "overshoots" a bit, and then adding a small star graph

[Let me know for further clarification/etc]


Some questions on kernels and Reinforcement Learning I've a test in a few days and I've a few issues with some of the subjects.

Let's start with kernels, basically I understood that a kernel needs to be positive semi-definite and symmetric in order to be valid. Is that enough? For example the following kernel, $\mathrm{kernel}(x,y) = 2 k(x,y)$ for some $k$ which is a valid kernel. Is that valid? My question is how can I distinguish between a valid kernel and an invalid kernel if I'm given a kernel in the test?

Reinforcement learning - Value iteration, upper bound confidence and Q-learning. I'm trying to figure out the major differences between them, Value Iteration is when we are familiar with the world, with the probabilities and such. And Q-learning is basically learning the world first. Where does upper bound confidence enter?

Thanks.

Is that valid? My question is how can I distinguish between a valid kernel and a nonvalid kernel if I'm given a kernel in the test?

Yes, it will be a valid kernel for all practical purposes, because kernel functions measure the similarity of some points relative to other ones (that's why they are also called similarity functions). Making your kernel function twice as big doesn't change that.

The next quote is from Wikipedia:

Although no single definition of a similarity measure exists, usually such measures are in some sense the inverse of distance metrics: they take on large values for similar objects and either zero or a negative value for very dissimilar objects. E.g., in the context of cluster analysis, Frey and Dueck suggest defining a similarity measure $s(x,y)=-\|x-y\|_{2}^{2}$
where $\|x-y\|_{2}^{2}$ is the squared Euclidean distance.

As you can see, a kernel function can be negative, if that's convenient in a particular problem. I don't know any example of an asymmetric kernel function. See this question for more examples.

The answer to your question boils down to this: can you apply a particular kernel function to a particular method? So it depends on a problem to large extent.

  Where does upper bound confidence enter?

In general, Upper Confidence Bound (UCB) is a Bayesian Optimization method, that aims to deal with exploration-exploitation trade off in the multi-armed bandit problem. In this problem, there is an unknown function, which we can evaluate in any point, but each evaluation costs (direct penalty or opportunity cost), and the goal is to find its maximum using as few trials as possible. Basically, the trade off is this: you know the function in a finite set of points (of which some are good and some are bad), so you can try area around the current local maximum, hoping to improve it (exploitation), or you can try a completely new area of space, that can potentially be much better or much worse (exploration), or somewhere in between.

Just as a side note, Bayesian Optimization methods, UCB in particular, build a model of the target function using a Gaussian Process (GP) and at each step choose the most "promising" point based on their GP model.

In Reinforcement Learning, the same exploration-exploitation dilemma arises as well. When an agent chooses an action to make, it has a choice between low uncertainty actions with a known value (exploitation) and high uncertainty actions (exploration). Without proper exploration, an agent would always do the same actions and never actually learn.

In this setting, UCB is counting how many times each action $a$ has been selected, $N_t(a)$, and maximizes the following expression:

$a_t = \underset{a∈A}{\operatorname{argmax}} Q(a) + \sqrt \frac{2 log t}{N_t(a)}$

where $Q(a)$ is an action-value function. If you compare this formula to the one used in Bayesian Optimization, you'll notice it's actually the same idea.


Set of vertex-disjoint cycles maximizing different colored vertices Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$.

I am looking to find a set of vertex-disjoint cycles that:

First maximizes the number of differently colored covered vertices.
In case of ties, break ties by secondly maximizing the number of chosen edges.
In case of any further ties, third minimizes the total cost of the chosen edges.

This is very similar to this problem, with additional constraint (#1). Without the first constraint (maximize the colors) this problem is easily solved by:

Splitting each vertex $v$ to $v^+$ and $v^-$.
Each vertex $v^+$ and $v^-$ provides a supply of $+1$ and $-1$, respectively.
Replacing an original edge $e': v \to w$ with $e: v^+ \to w^-$. Such each edge has cost $cost(e') = cost(e)$ and unit capacity.
Adding a "bind" edge $e'' : v^+ \to v^-$. Its cost is $c(e'') \gg 1$

Here is a representation:

And the problem has been reduced to a minimum-flow problem (MCF). A MCF algorithm will choose $A_1 \to B_1 \to A_2 \to B2 \to A_3 \to B_3 \to A_1$.

My question: is it possible to apply a similar modeling to satisfy the color constraint in polynomial time? If so, is it possible to reduce the problem to a MCF problem?

Here is how far I have managed to take it:

Here, bind-edges $e''$ go through a collective set of nodes, one per color, e.g., "A no+" and "A no-". These represent the corresponding vertices not chosen. Between "A no+" and "A no-" three edges are added with unit capacities and costs $ c(e_{red}) >> c(e_{orange}) >> 1$

I basically model that the cost of not choosing one or even two yellow items is insignificant to the cost of not choosing all three yellow items. Therefore, the goal is to choose $A_1 \to C \to B_3 \to A_1$.

Nevertheless, this did not quite work. Basically, if a flow goes through $A_1^+ \to A_{no}^+ \to A_{no}^-$, it's not guaranteed that it will return to $A_1^-$.

I have tried other approaches, including toying around with non-unit capacities, but I didn't find a solution. Can it be solved in polynomial time?

It cannot be solved in polynomial time, assuming P$\,\neq\,$NP.

Without worrying about colors (i.e. if every vertex had the same color), it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature and can be solved in polynomial time with a reduction to the Assignment Problem.

With the introduction of colors to the problem, it is NP-hard (and the corresponding decision problem is NP-complete).  The problem that you described can be called TROPICAL MAX SIZE EXCHANGE (TROPMAX EXCHANGE).  CNFSAT reduces to TROPMAX EXCHANGE.

Create a graph with one vertex for each variable in the CNFSAT expression, with all of these "variable vertices" colored the same way.  Assign each clause in the expression its own color.  From each "variable vertex" create two cycles - label one cycle 'true' and one 'false'.  For each literal in the expression, create a vertex that is the color of its clause and put it on the appropriate 'true' or 'false' cycle of the corresponding variable vertex.  Finally, add additional vertices of some new color so that every 'true' and 'false' cycle has the same number of vertices.

Because we are choosing vertex-disjoint cycles, each 'variable vertex' can only be in its 'true' cycle or 'false' cycle, not both.  There are no cycles in the graph other than those true/false cycles.  Every cycle has the same number of vertices, so an algorithm that first maximizes the number of vertices in the cycles can choose any combination of cycles: either true or false for each variable vertex.  If the secondary criterion is to maximize the number of colors in the cycles, then if all colors can be included the CNFSAT expression can be satisfied.

Highley, Timothy and Le, Hoang. "Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent"
dmtcs:3186 - Discrete Mathematics & Theoretical Computer Science, July 31, 2018, vol. 20 no. 2
https://dmtcs.episciences.org/4690
https://arxiv.org/abs/1610.05115


Gauss-Jordan using stacks and list I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting.  Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows and columns are swapped around pivots.  This is done to minimize the numerical errors by avoiding operations with small floating-point values.

A common approach would be to use for loops for swapping rows, but it would cost $O(n)$ operations to move a row and $O(n)$ to move a column. Using stack and list could be faster.

So the question is, how can stacks and lists be used in an implementation of Gauss-Jordan to efficiently swap columns in a matrix $A$?

I can change rows using pointers, but I can't realize how to use those structures to move columns and do Gauss-Jordan.

EDIT: Sorry i was to tired when create this question, as i'm not from a english speaker native country, i made some mistakes. The questions is about swapping columns using lists and stack. I'm really sorry, i wasted almost week thinking about it.

What you want is called indirection. Instead of physically moving the rows/columns, you move their names.

Let's say I call row 1 r[0], and row 3 r[2], in a matrix A, which has size n  by n. Initially, the rows are exactly as I call them, so we initialize r[i] = i for all i < n.

Now I want to swap the third (r[2]) and the fifth row (r[4]). I could move the elements in matrix A, but this would require n swaps. Instead, I can just swap r[2] and r[4]! This is just swapping one integer.

The tradeoff is that now we must read matrix A as A[r[i]][c[j]] (where c is the equivalent of r, but for columns) instead of A[i][j]. This is a bit slower.


Which complexity classes are $\mathsf{RE}$? Given some complexity class $\mathsf{C}$, I want to know if there exists a function (Turing machine) $F:\mathbb{N} \to \mathsf{C}$ such that, if $S$ is any set for which the problem $x \mapsto x \in S$ is in $\mathsf{C}$, then $F(n)$ is a Turing machine which (partially, if $\mathsf C = \mathsf{RE}$) decides $x \in S$ for some $n$.

Note that if $g$ and $h$ are two Turing machines that decide $x \in S$, then $F$ only needs to enumerate one of them (hopefully this makes the problem easier). Thus the title is a bit wrong, but kept as it is for lack of a better one.

Trivially, if $\mathsf{C}$ equals something in the Chomsky hierarchy, such machine $F$ exists (enumerating all grammars of the required type). I'm interested in the less obvious classes.

Time-bounded classes can be enumerated. Suppose we want to enumerate all languages in P. Every language in P is accepted by some Turing machine $T$ running in time $f(n)$ for some polynomial $f$. We can construct a Turing machine $T'$ that emulates $T$ but also keeps track of the time, and stops after $f(n)$ steps. Every Turing machine of the form $T'$ accepts a language in P, and vice versa, for every language in P, we can construct such a machine $T'$. The machines $T'$ themselves can be enumerated by enumerating the simulated machines $T$ and the "timers" $f(n)$.

For a space-bounded class, you do something similar, keeping track of the space usage of the Turing machine. You also need to prevent infinite loops somehow, either using a timer or by keeping track of all positions encountered so far during the simulation.

Non-deterministic and randomized versions can also be handled this way, so for example, PH can be enumerated.


How do GPUs compute sines? I've been wondering lately how GPUs compute sines and cosines, and Google hasn't helped me finding a precise answer.

Initially, I was thinking that in order to make the computations as fast as possible, the GPU would use some kind of lookup table. But then I realized, storing all sin values in a table of the range of doubles between [0, 2 * pi] would be a massive one, and thus not be a valid option.

The table could possible be shrunk down in resolution, and the missing values for a lookup can then be lerped. This however, introduces a possible error which can propagate to bigger and unacceptable errors when performing the computation multiple times.

My last idea is then that they could be using a Taylor approximation, but that would involve quite some arithmetic, which may be too slow for a GPU. So the question is, what do GPUs use to calculate the sines? Are it lookup tables, approximations, or a hybrid of both? And possible, do they use the same method for other computations like sqrt()?

I believe that NVidia GPUs they use a table lookup, followed by a quadratic interpolation.  I think they are using an algorithm similar to the one described in: Oberman, Stuart F; Siu, Michael Y: "A High-Performance Area-Efficienct Mutlifunction Interpolator," _IEEE Int'l Symp Comp Arithmetic, (ARITH-17):272-279, 2005.

The table lookup is indexed with the $m$ most-significant bits from the input, $x$, and returns three coefficients, $c_0$, $c_1$, $c_2$.  The final result is produced by evaluating $c_0 + c_1 x + c_2 x^2$.  The coefficients for each range of $x$ are chosen to minimize the maximum error from the target function over that range.

So that the unit can be fully pipelined to produce one result per cycle the unit contains a special squaring unit and two booth-encoded wallace-tree multipliers.  For each special function they choose the number of table entries ($2^m$) so that the polynomial evaluation will give them a single-precision IEEE FP answer correct to within a couple of units in the last place.


What does "AC0 many-one reduction" mean? What does $\mathsf{AC^0}$ many-one reduction mean?

I know about polynomial time reductions, but I'm not familiar with $\mathsf{AC^0}$ reductions.

An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit.  It's just like a polynomial-time many-one reduction, except that instead of requiring that the mapping takes polynomial time, we require that the mapping is in AC0.

David Richerby further explains: "AC0 is a very low-complexity class so it can be used, for example, to study reductions between logspace problems, which doesn't make sense with polytime reductions since, then, the reduction would be more powerful than the problem class being studied."  For instance, if problems A,B can be reduced to each other with polynomial-time reductions, then you learn that their complexity can't be exponentially different (if one is polynomial, the other must be too), but it's possible that they still might be fairly different (polynomially different).  If they can be reduced to each other with AC0 reductions, then this has stronger implications about their  complexity (it has to be pretty similar).


How is wordnet curated? I use Princeton's WordNet in NLP applications. I always read that it is "human-curated." But how is it curated? Who decides that words belong in a synset? How does the process work? Wikipedia does not give many details. How does it work?

As far as I know, they do the same way they created things like Penn tree bank.
They have a panel of experts, usually linguists, who sat together and decided synset taxonomy based on various widely used dictionaries.

PS: Please up-vote me so I can up vote others, thanks :)


relational algebra and SQL Using the following relations:

consultant(id,Name,Skill)

CustomerCompany(Id,name Address, Phone, Email, WebAddr,Market)

project(id,StartDate,EndDate,ConsultantID,CustomerId,Days)

Invoice(id,Date,Customer,Amount,Status)

Im trying to work out the following scenario using SQL and Relational algebra

Find the names of the consultants and the names of customers, where the consultant has worked for the customer, and the customer received an invoice in the range of GBP 100k to 200k

Using SQL i have:

Select I.amount, C.name
from CustomerCompany C, Invoice I
where I.Customer= C.id and > all
(
  select C.name, Con.Name
  from CustomerCompany, Con Consultant
  where i.amount between 100 and 200
 );

Relational algebra:

amount = σ(Invoice, amount>=100 and amount<=200)

joininv= Ⓧ(amount, Customer, CustomerCompany, id)

joincon Ⓧ(joiniv, Consultant id, Project, ConsultantID)

π =(joincon, name, Name)

I was wondering if write or wrong?

Thanks for any help!

The correct SQL would be :

select co.name, cu.name
from consultant co join project pr on co.id = pr.ConsultantID
                   join CustomerCompany cu on cu.id = pr.CustomerId
                   join Invoice i on i.Customer = pr.CustomerId
where i.amount between 100 and 200

Converting to relation algebra is straightforward...


Can Tug of war problem be solved by DP or greedy approach? For problem explanation: https://www.geeksforgeeks.org/tug-of-war/

I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ideology of the solution. Also please mention if there are exceptions to this greedy or DP solution where it may not apply.

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

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

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

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


Execution time of NP and NP-Complete algorithms For P algorithms, we say that the execution time can be logarithmic O(log n), lineal O(n), quadratic O(n^2), etc.

For NP and NP-Complete algorithms is there a way to represent the execution time? Or is there a 'standard' way of doing it?

Asymptotic (/Big-Oh/Landau) notation is not special to polynomial time algorithms, or indeed any class of algorithm. It is the standard way of communicating (asymptotic) running times, amongst other resources.

So we say that binary search runs in time $O(\log n)$ because that is what its asymptotic running time is, and hence the Searching problem in $\mathrm{P}$, but not it is in $\mathrm{P}$ and hence we can get some $O(\cdot)$ expression for it. The Tower of Hanoi problem has an $O(2^{n})$ algorithm for example (in fact $\Theta(2^{n})$), this happens to put it in the class $\mathrm{EXP}$ , but the asymptotic expression is still an evaluation of the running time, regardless of which class it is in.

Note the distinction here between problems an algorithms as well. A problem is in a complexity class, and algorithm has a running time. By extension we say that the problem can be solved in time "blah" because it has an algorithm runnning in that time. So we can't have an $\mathrm{NP}$-complete algorithm, only an $\mathrm{NP}$-complete problem. We can abuse the language a small amount an say we have and $\mathrm{NP}$ algorithm, but what we mean is that we have  a nondeterministic polynomial time algorithm, i.e. an algorithm that demonstrates that whatever problem it's for is in $\mathrm{NP}$, just as binary search is a polynomial time algorithm that demonstrates that Searching (the formally defined problem) is in $\mathrm{P}$. Then David Richerby's answer applies - they're just polynomial but on a nondeterministic machine, i.e. $O(n^{c})$ for some fixed $c$.

On the flip side, we can have an algorithm for an $\mathrm{NP}$ problem that is not the one that shows that the problem is in $\mathrm{NP}$. For example, there's an algorithm for the Travelling Salesman Problem that just tries all the possibilities. This algorithm has running time $O(n!)$. It's not the best algorithm, but it is an algorithm for an $\mathrm{NP}$-complete problem, and that's its running time expressed asymptotically.

Finally, $\mathrm{P}$ is a subclass of $\mathrm{NP}$, so all those "P algorithms" are also "NP algorithms" - they just don't use the nondeterminism.


Knapsack and set cover-like problem Given $n$ sets $r_1, r_2, \cdots, r_n$ and a number $\delta$ where $0 \le \delta \le 1$. Let $T=\cup_{i=1}^{n}r_i=\{t_1,t_2,\cdots,t_m\}$. Each $t$ has a value $v(t)$, which is given to us.  The task is to find a subset $S$ of $T$ that minimize the total value $\sum_{t\in S}v(t)$ while guaranteeing $\sum_{i=1}^{n}\frac{|r_i \cap S|}{|r_i|}>\delta n$.

Is this problem NP-complete? If so, which problem should I reduce from?

I've tried reduce it from the knapsack problem. One of the steps is not in P time and the attempt failed.

Your problem is an instance of the following problem:

VECTOR-MINIMIZATION:
Input: vectors $v,w \in \mathbb{R}^m$, a threshold $\gamma \in \mathbb{R}$
Goal: minimize $v \cdot x$, subject to $w \cdot x \ge \gamma$ and $x \in \{0,1\}^m$

In your problem, $v=(v(t_1),\dots,v(t_m))$ and $w=(w_1,\dots,w_m)$ where $w_i = \sum_{t_i \in r_j} 1/|r_j|$, where the sum is over all $j$ such that the set $r_j$ contains the element $t_i$.

So, your problem is an instance of VECTOR-MINIMIZATION.  In turn, VECTOR-MINIMIZATION is basically an instance of the knapsack problem (it is at least as hard as knapsack, and thus NP-hard).

That raises the question, is your problem any easier than the general VECTOR-MINIMIZATION problem (or knapsack)?  In your problem, each $w_i$ has a special form: it is a sum of a polynomial number of reciprocals of polynomial-size integers.  I don't think there's any way to use the special structure of the $w_i$'s (and there are exponentially many possible values for the $w_i$'s), so I think your problem is NP-hard, but I don't have a proof at the moment.

That said, you can still use the standard algorithms for knapsack-like problems: e.g., integer linear programming (ILP).


Why it is not a Huffman code I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was:

$\{00,01,10,110\}$

This code is not Huffman becuase it has just one codeword of maximum length whereas there should be two as a minimum.

Next, the one I hava a problem in proving:

$\{01,10\}$

Why this code is not a Huffman code?

(Minimum number of codewords) (Binary complete) Huffman code of maximal code length $n$ must have at least $n+1$ codewords.

The maximal code length of codewords $\{01, 10\}$ is 2. However, there are only two codewords. So those codewords is not a Huffman code.

(Exercise.) Prove the claim of the minimum number of codewords of Huffman code.


Hamiltonian path in grid graph Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that neither the source or the destination is an obstacle.

I need to, provided a starting node (a square), find any path that visits every single node that is reachable, without visiting any node twice.  If there is no such path, then any path that would visit as many nodes as possible.  In other words, I'm looking for an algorithm to find a Hamiltonian path in such a graph.

I am not looking for the shortest path.

The most important factor is the time the algorithm takes to complete (complexity).

I have searched Google and this site, and I only find variants of the travelling salesman, or algorithms for shortest path visiting all nodes, which won't work in my situation. My algorithm needs to find a path of any length visiting as many nodes as possible while never visiting a node twice. The path can end anywhere.

Does anyone have any tips? I've tried to do this with a variant of A*, but I couldn't make it work. I've succesfully done it by brute-forcing, but as the graph can be rather large, I need something a faster than O(n!).

It would be even better if the algorithm was non-deterministic, which means that if there are multiple possible solutions, we wouldn't always get the same one with the same graph and starting location. I have no idea how to do this without slowing it down though, and speed is more important.

There isn't going to be a fast algorithm for this problem.

The class of graphs you're dealing with is, in some of the literature, called grid graphs.  That is, they're finite induced subgraphs of the infinite graph with vertices $\mathbb{Z}\times\mathbb{Z}$ with an edge from $(x,y)$ to $(x',y')$ if, and only if, $|x-x'|+|y-y'|=1$.

Itai, Papadimitriou and Szwarcfiter (Hamiltonian Paths in Grid Graphs, SIAM Journal on Computing, 11(4):676–686, 1982) showed that it's NP-complete to determine whether a grid graph has a Hamiltonian path. Your problem is NP-hard (under Cook reductions, and possibly also under the more usual Karp reductions): if you can determine the length of the longest path from a vertex, just do that for each vertex in turn and see if any of the longest paths is Hamiltonian.


Efficient data structures for building a fast spell checker I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to determine which words are closest to the misspelled word.

I'm looking for a data structure who would give me the best compromise between space complexity and runtime complexity.

Based on what I found on the internet, I have a few leads regarding what type of data structure to use:

Trie

This is my first thought and looks pretty easy to implement and should provide fast lookup/insertion. Approximate search using Damerau-Levenshtein should be simple to implement here as well. But it doesn't look very efficient in terms of space complexity since you most likely have a lot of overhead with pointers storage.

Patricia Trie

This seems to consume less space than a regular Trie since you're basically avoiding the cost of storing the pointers, but I'm a bit worried about data fragmentation in case of very large dictionaries like what I have.

Suffix Tree

I'm not sure about this one, it seems like some people do find it useful in text mining, but I'm not really sure what it would give in terms of performance for a spell checker.

Ternary Search Tree

These look pretty nice and in terms of complexity should be close (better?) to Patricia Tries, but I'm not sure regarding fragmentation if it would be better of worse than Patricia Tries.

Burst Tree

This seems kind of hybrid and I'm not sure what advantage it would have over Tries and the like, but I've read several times that it's very efficient for text mining.

I would like to get some feedback as to which data structure would be best to use in this context and what makes it better than the other ones. If I'm missing some data structures who would be even more appropriate for a spell-checker, I'm very interested as well.

I've encountered same problem, but took different approach.
You can construct some kind of "hash" function, which will for similar word give same or near number.

Problem is, that function which will give "good" result for words with inserting/removing, will give "bad" for transition, and vice versa.
Example: map letters to numbers, similar letter to adjacent numbers, and just sum them for every letter in word.
Then create hash-tables with sets for each key and find intersection for word.

May be some results can be achieved if we look at "space" оf words. X for changing letter, Y for adding/removing, Z for transition, or something like that.

However this is only abstract ideas, I haven't enough time to implement them.


How to sample Bivariate Normal Distribution with Accept reject method I have to write python code in jupyter due to sampling bivariate normal distribution with 3 sampling methods:

Prior Sampling
Gibbs Sampling
Rejection Sampling

I have done the first two samplings and I also have clear understanding of what accept reject method or so-called rejection sampling is.
yet I can not find any proposal distribution for it.

Rejection Sampling and proposal distribution
assume you have a distribution $f(x)$ which is not easy for you to sample.
choose another distribution that is easy for you to sample wisely called $g(x)$ so that for some constant $C$ for all $x$ we have $C.g(x) > f(x)$.
we call this $g(x)$ the proposal distribution.
sample from $g(x)$ and name it $X_i$ as you chose $g(x)$ because it was easy to sample. accept this sample with a probability of $p = f(X_i)/C.g(X_i)$.
As I said before I cant find any $g(x)$ easy enough to sample and yet bigger than bivariate normal distribution for some $C$.

I came up with this answer which can approximately sample a bivariate normal distribution with accept reject method and I thought it might be useful for others in future.
we choose a 2D uniform distribution called $F_{X,Y}(x,y) = F_X(x).F_Y(y)$ where both $X$ and $Y$ are uniform distributions in range of $(0, +a)$ and they are independent of each other.
We choose a constant $C$. Both $C$ and $a$ are chosen based on our bivariate normal distribution so that:

for all $x, y$ we have $C.F_{X,Y}(x,y) \geq BN(x,y)$, Where $BN$ is our bivariate normal distribution.
$x, y \in (-a, +a)$ supports most of our $BN$ density.

The Accept Reject Method:

Now we sample from our $F_{X,Y}(x,y)$. Suppose it's $X1 = (x1, y1)$.

We uniformly choose from:
$$X_{1.1} = (x1, y1),$$
$$X_{1.2}=(-x1, y1), $$
$$X_{1.3}=(x1, -y1), $$
$$X_{1.4} = (-x1, -y1)$$
and name that $\hat{X_1}$ so that we consider all four quadrants of $xOy$.

Now we accept $\hat{X_1}$ as a sample of $BN$ with a probability of $p=BN(x1,y1)/C.f_{X,Y}(x,y)$.

We come back to step 1 and do this cycle to collect as much sample from the bivariate normal distribution as we want.


How to analysis the complexity of this LIS program? I found a pseudocode online and I don't know why the complexity of it is $O(2^N)$, according to the site.
Given a fixed curr, the for-loop in lis_ending_here(...) will recursively call curr times itself will new curr range from 0 to curr-1, then I stuck here and don't know what's the next step to get the conclusion $O(2^N)$. You can also provide me resource (i.e. book name) which is about the technique to analysis the complexity of recursion, since I don't know what are the beginner friendly ones.
int lis_ending_here(int arr[], int curr)
{
    // Only one subsequence ends at first index, the number itself
    if(curr == 0)
        return 1
    int ans = 1
    for(i = curr-1 to 0, decrement of -1)
        if(arr[i] < arr[curr])
            ans = max(ans, 1 + lis_ending_here(arr, i))
    return ans
}
int longest_increasing_subsequence(int arr[], int N)
{
    // Because a single number can be a subsequence too
    int max_ans = 1
    for(i = 0 to N-1)
        max_ans = max(max_ans, lis_ending_here(arr, i))
    return max_ans
}

The worst case running time of your first procedure satisfies the recurrence
$$
T(n) = T(n-1) + \cdots + T(1) + O(1).
$$
The worst case running time of your second procedure is $T(n) + \cdots + T(1) + O(1)$, which we can identify with $T(n+1)$. Thus it suffices to understand the first recurrence.
Let us assume replace $O(1)$ with $1$, obtaining the recurrence
$$
T(n) = T(n-1) + \cdots + T(1) + 1.
$$
Therefore
$$
T(n+1) = T(n) + [T(n-1) + \cdots + T(1) + 1] = 2T(n).
$$
Consequently, $T(n) = 2^{n-1} T(1) = 2^{n-1}$.
If we replace $1$ back with $O(1)$, we get $T(n) = O(2^n)$.


Find all cycles through a given vertex Given a directed graph $G$ and a vertex $v$, how can we enumerate all simple cycles that pass through $v$?

I found a question that describes how to enumerate all simple cycles in $G$, but I want only the cycles that pass through $v$, so this question is a bit different.  The total number of cycles in $G$ can be exponentially larger than the number of cycles passing through $v$, so just enumerating all cycles in $G$ and keeping only those that go through $v$ might be inefficient.

I'm not asking to count the number of cycles; I want an algorithm to list them all. I would like an output-sensitive algorithm, where the running time is some low-order polynomial of the number of cycles that go through $v$.  I know there can be exponentially many cycles, so there is no hope for an algorithm whose running time is polynomial in the size of the graph.

Motivation: This is a cleaned-up version of Given a directed graph and a vertex v, find all cycles that go through v?.  I wanted to ask the more general version of the question.

Solution: Modify Johnson's algorithm

Johnson's algorithm can be used to enumerate all cycles in $G$.  It can be easily modified to enumerate only and all the cycles that contain $v$.

Johnson's algorithm works by numbering the vertices from $1$ to $n$, and classifying each cycle according to the smallest-numbered vertex in the cycle.  It first enumerate all cycles whose smallest-numbered vertex is $1$, then all whose smallest-numbered vertex is $2$, and so on.

So, here is the modification to Johnson's algorithm.  Choose a vertex numbering where $v$ receives the number $1$, and the other vertices are numbered in any order.  Run Johnson's algorithm, but only enumerate the cycles whose smallest-numbered vertex is $1$.  This will enumerate all the cycles containing $v$, and only the cycles containing $v$.

Running time

The running time of this algorithm is $O((m+n)(q+1))$, where $q$ is the total number of cycles containing $v$, $n$ is the number of vertices, and $m$ is the number of edges.  Its space consumption is $O(n+m)$.

References

Here is a full citation to Johnson's paper describing the algorithm:

[Finding all the elementary circuits of a directed graph][1]. Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, March 1975

See also Find the Simple Cycles in a Directed Graph.  For help understanding Johnson's algorithm, see

https://stackoverflow.com/q/2908575/781723
https://stackoverflow.com/q/2939877/781723
What is the difference in 'logical array blocked' and array list B, and what do they represent?

For pointers to implementations of Johnson's algorithm and discussion of other algorithms to find all cycles in a graph, see https://stackoverflow.com/q/546655/781723.  I don't know if there's a way to modify them to enumerate only cycles that contain $v$.


How does Server know window size for TCP Header? I'm trying to understand TCP right now. In the header there is "Window Size" which to my understand is the maximum amount of data that can be sent at once. My question: How does the server know how much data it can send? If I understand it correctly, the only information the server gets from the client is the ACK number that says "Package Received". Or is there more? Do I miss something?

The Window Size field in the TCP packet header is the number of bytes the sender will buffer for the response. Basically, during the handshake each side will say how large its receive window is. That is, the Window Size field in a packet sent by the client, tells the server how much data the client can receive and thus how much the server can send before the client would need to drop packets. Symmetrically for the packets the server sends to the client. See the flow control section for details on how the window size changes. Of course, see the relevant RFCs for the authoritative recommendations.

As far as how the initial receive window is calculated, this is based on local resources and policies. Clearly, the initial receive window shouldn't be set to be larger than the amount of buffer memory you have. For a specific connection, larger is better for throughput if packets aren't being dropped, but larger packets are more likely to be dropped and when they are dropped require more data to be resent. RFC3390 presents a recommendation for what the initial receive window size should be assuming local resource limitations aren't a concern. This link describes what the Linux 2.6 kernel did (at least for RedHat distributions), though it may be out of date.

There is a different thing called the congestion window which each host may maintain itself as an estimate for how much data it can reliably send. This isn't communicated since it's unlikely there's anything the receiving end can do about it as it may well be intermediate nodes in the network that are limiting the rate. Again, this is an estimate and many variations of TCP are due to different strategies to estimate this value. Hosts don't have to agree on these congestion control algorithms for TCP to work.


Functions between sets? I recently took a practice exam for the Computer Science GRE and this was one of the questions:

  Assume that set $A$ has 5 elements and set $B$ has 4 elements, how many functions exist from set $A$ to set $B$?

I had no idea what this means, I don't recall ever studying functions between sets, could someone shed some light on this question for me ?

$\newcommand{\stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}$Your comment is correct in that there are $4^5=1024$ functions from $A$ to $B$.

Letting $|A| =n, |B| = m$ this can be seen by the identity:

$$\sum_{k=0}^n \stirling{n}{k} m(m - 1) \dotsb (m - k + 1) = m^n$$

This describes all the ordered partitions of $A$ over $B$ where each partition is an assignment to the same item in $B$.

A less heady explanation (and perhaps easier to visualize) is the following:

We have a vector of length $n$. Each position in this vector can choose $m$ possible values. That is, the $i$th value in the vector represents what $f(a_i)$ maps to. How many $n$-length vectors over $m$ values can we have? Exactly $m^n$.


Sum of 3 integers with full adder 1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image below).I mean C1 comes from the frist block and I dont provide it. And this mean I can only choose the first bit of C0. So it does not add 3 integers, right?

2)Is it possible to get the sum of k n-bit integers with full adder circuit?

Thanks in advance!

It seems you have almost invented the carry-save adder.

You can use independent full adders for several layer, each time reducing 3 wires of equal weight to 1 wire of that weight and 1 for the next higher weight. Of course if there are 6 wires of the same weight, you can reduce them to 2 of the same weight and 2 of the next higher weight, and so on.

But the result of doing a bunch of that is not the sum, but two partial sums, one coming from all the S outputs of the last layer and one coming from all the C outputs. They still have to be added normally. You can use a ripple-carry adder or something faster/bigger there like a Kogge-Stone adder (which you'd only need once, compared to n-1 times if you just added up everything the obvious way).


How to distinguish between bits? I read a post about differences between synchronous and asynchronous transmission modes.
That post has a picture about how bits flows from terminal to computer in async mode.

But how computer can distinguish between 1s and determine what 1 does actually mean. Is it parity bit, is it start/stop bit or maybe it's start of idle bits?  Or just part of data is being transmitted?

If the computer starts in the middle of the stream, it has no way to know—it will be completely confused.

Fortunately, that's not how the protocol works. The computer and terminal have to sync up before they can communicate. There are a few different ways of doing that, but once they're in sync (which includes agreeing on how long each 1 or 0 should last), they both follow a set pattern.

In this example:

The terminal starts out holding the line high (sending constant 1s) to indicate that it has nothing to say.
When the terminal has something to say, it brings the line low for a moment (sending a 0). That's the "start" bit.
The terminal then sends seven bits for the character: always exactly seven, since it's using ASCII, which is a seven-bit encoding.
After those seven bits, it sends one additional bit for error checking. This is a 1 if there were an odd number of 1s in the character, and a 0 otherwise. This is the "parity" bit.
Finally, it pulls the line high again to indicate that it once more has nothing to say.

The computer keeps track of which "mode" the connection is in at all times. If it sees a zero, it might record it as part of the data, or might switch from "idle" mode to "start listening for data" mode, or check the parity: it all depends on what it's seen before.


How many languages are described by a regular expression? How many languages can a Regular Expression describe is it only one or infinite?
I have tried to google it but i haven't found any answer?
I know that a Regular Expression describes a Regular Language?

Every regular expression describes one language --- the language of words matched by the regular expression, or, in other words, the language of words accepted by the finite automaton corresponding to the regular expression.


Counting pairs of intervals where one is a subset of the other Given a list of intervals with nonnegative endpoints, e.g. $ [3,5][1,7][2,60] $, the goal is to find the number of pairs of intervals $I,J$ such that $I$ is a subset of $J$.
In this particular case the total number is 2 because $[3,5]$ is a subset of $[1,7]$ and a subset of $[2,60]$.
Furthermore we were asked to find a solution to this problem with time complexity less than $O(n^2)$.

At first I thought of sorting the given sets based on their lower bound and in this example the order would be $ [1,7] \to [2,60] \to [3,5] $  so the time complexity so far is $O(n\log n)$, but I can tell nothing about the total number of pairs cause of the order of the upper bounds of the sets is a mess. Then I thought of sorting them based on their middle element and then performing a Binary Search based on this sorting so my time complexity would still be $O(n\log n)$. However now I am stuck and a direction would be appreciated.

Sort all endpoints of intervals, and maintain a self-balancing order statistic tree, initially empty. Scan the endpoints from left to right. Add each left endpoint to the tree. When reaching a right endpoint, determine the order statistic of the left endpoint, and then remove the endpoint. Update the number of intersections accordingly: if the left endpoint was that $i$th smallest element (counting from $1$), then add $i-1$.

Since each operation on a self-balancing order statistic tree takes $O(\log n)$, the entire algorithm runs in $O(n\log n)$.

As an example, consider your list of intervals.

Initially, the tree is empty, and the counter is 0.
Read left endpoint of [1,7]. Tree contains 1.
Read left endpoint of [2,60]. Tree contains 1,2.
Read left endpoint of [3,5]. Tree contains 1,2,3.
Read right endpoint of [3,5]. Since 3 is the third smallest point, increase counter by 2. Tree contains 1,2.
Read right endpoint of [1,7]. Since 1 is the smallest point, increase counter by 0. Tree contains 2.
Read right endpoint of [2,60]. Since 2 is the smallest point, increase counter by 0. Tree is empty.


simulation of PDA with turing machine How to simulate a non-deterministic PDA with a turing machine?

A PDA is a special (degenerated) case of a TM. Specifically, TM can be seen as a PDA whose stack's head can read from within the stack and not only the top of the stack.

Therefore, simulation of a PDA by a TM is trivial.


Can a weaker version of the Halting Problem be solved? I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this:

Assume that some machine $H$ exists that can solve the halting problem on a given machine $A$ with input $x$ ($H$ determines whether the machine $A$ halts on input $x$).
Now build a machine $Q$ which consists of $H$ and an extra component that takes in the output of $H$ and functions by never halting whenever $H$ returns "true", and halts whenever $H$ returns "false".
Then feed into $Q$ itself as both its given machine and the machine's input. Now, what does $Q$ return? If the machine $H$ inside $Q$ determines that the system halts, thereby returning "true", then $Q$ does not halt, as outlined above. However, if $H$ determines that $Q$ does not halt, then it does halt, as outlined similarly above. Therefore $H$ cannot exist.

I understand how this prevents any machine from existing that provides a general solution to the halting problem for any input, but does it also prevent solutions to certain smaller problems as well?

Specifically, could there theoretically be a 1000-state or larger Turing machine which can solve the halting problem for all Turing machine inputs with 50 states or fewer (the specific values aren't relevant)? That way, the machine cannot be input itself as a parameter, and the contradiction above would not be relevant.

To be clear, I'm not asking whether such a machine could be feasibly built, but rather whether is it theoretically possible for such a program to exist that solves the problem for machines smaller than a certain limit?

If you define $H$ to take a 50-or-fewer state Turing machine (TM) and an arbitrarily large input, then if you can build a universal Turing machine (UTM) in 50-states, then you can simulate $H$ by encoding its description as well as its input into the input of the 50-state UTM.

If $H$ merely needs to tell whether any 50-or-fewer state TM halts with an empty tape as input, then, since there are finitely many such TMs, it can simply have a table hard-coded into it. Producing this table may be difficult, but it "exists" in the usual mathematical sense.1 Given values of the Busy Beaver function, we can actually easily describe one potential implementation. Simply simulate the input TM up to the appropriate Busy Beaver number of steps, and if it hasn't halted by that point, then it never halts.

To give an idea of how difficult it is to produce the aforementioned table, just note that we can write a program that terminates only if ZFC set theory is inconsistent. Gödel's incompleteness theorem then implies that if ZFC is consistent, then it is not possible to prove that that program doesn't halt. The upshot of this is after a certain number of states (and not a very large number) even if you were outright given the (correct) TM to do what you describe, you could not prove that it was correct in ZFC. (This isn't particular to ZFC. ZFC is just the formal system that is usually considered the "foundation" of mathematics. Other formal systems will merely have different cut-offs.) In other words, even if you were given the answer, you could not convince yourself that it was correct.

1 Actually, it exists in a stronger sense than many mathematical objects in that we can actually enumerate all the Turing machines and at some point the correct one will come up. We just won't realize it when it happens, in general.


Prove that $TQBF \notin SPACE(n^{\frac{1}{3}})$ I would like some hints on how to approach this problem, I know for instance that $TQBF$ is $PSPACE$-$Complete$, so it can solved in poly space and any other $PSPACE$-$Complete$ problems can be log spaced reduced to $TQBF$. I believe that I need to employ the space hierarchy theorem in some way but I am not sure how, this is a homework question so I just want a hints. Thank you!

The argument is actually surprisingly delicate. This sketch follows Tompa's Introduction to computational complexity, Chapter 10. The space hierarchy theorem shows that there is some problem $L \in \mathrm{SPACE}(n^{1+\epsilon}) \setminus \mathrm{SPACE}(n)$ for every $\epsilon > 0$. Since TQBF is PSPACE-complete, there is some logspace reduction from $L$ to TQBF. But we actually know more - using Savitch's theorem, we can come up with some reduction which blows up instances of $L$ of size $n$ to instances of TQBF of size $O(n^{2(1+\epsilon)} \log n)$ (at least according to Ryan Williams, page 1 at the bottom). If TQBF were solvable in space $O(n^\delta)$ then this would give an algorithm for $L$ in space $O(n^{2\delta(1+\epsilon)})$. Taking the limit $\epsilon \to 0$, this shows that $\delta \geq 1/2$.


Logic applications and security protocols references request I'm a student of logic and I'm interested in looking at logic applications, of which I am told there are many, in computer science and allied areas. I've seen some applications. More specifically, I keep seeing little things about security protocols which use logical methods. I'd like to learn some more about this material, although I suspect it may require I obtain a knowledge of networks and cryptography which I currently lack (although hopefully not for long!). I have recently obtained Ryan and Schneider's textbook on Security Protocols.

Are there any other suggestions for reading and self-teaching in this and / or other areas in computer science which use logical techniques  / formal methods? (I expect there are many; just looking to be pointed in a couple of amenable directions which are reasonable for someone who knows some pure logic.)

I really like the phrase, as well as the book, that logic is calculus of computation. It is kind of hard to find an area in computer science where logic is not used. I will just mention few areas where knowing logic comes in handy.

Verification. Techniques of logic are heavily used in verification area. Specification of hardware and software systems is usually given as logical formulas. Depending on what properties are being checked, such systems are also modeled by appropriate logic (propositional, FOL, modal logics, linear logic, etc.). Methods like satisfiability and model checking are usually used to check whether a system meets its specification. Moreover, there is an area of decision procedures that tries to come up with efficient procedures for checking satisfiability of formulas in various logics (by most first order theories). In general, you might want to take a look at automated theorem proving.
Programming languages. As pointed earlier, there is a deep connection between programming languages and logic. By Curry-Howard isomorphism, every functional program is isomorphic to some proof in constructive logic. Logic is also used for defining axiomatic semantics of programming languages; see Hoare logic. Prolog is a programming language based on a paradigm where computation is specified by logical formulas. Lambda calculus was first intended as a formal logical system aimed to laying foundations of mathematics, but turn out to be more useful as a programming language. It is now at the core of every functional programming language.
Misc. You might also be interested in the way logic and computability interplay. What might be specially interesting to you is descriptive complexity. Logic is also getting more attention in computational biology. It is also used in AI for knowledge representation.

Hope this gives you some kind of a starting point.


What do we call a function that outputs 0 on half and 1 on the other half of all inputs? I have a Boolean function that outputs a one on half of its inputs and outputs a zero on half of its inputs, the inputs are assumed to be coming from the uniform distribution. Another way of saying this is the output is one half the time and zero half the time, on average. What is the scientific notation for describing this output scenario?

A boolean function is called balanced if it is zero on half its inputs and one on half its inputs.  So, "balanced" might be the term you are looking for.


Most common subset of size $k$ I'm trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets.  If there are ties for the most common subset, I want the one of them whose size is as large as possible.

For example if I have:

s1 = {A, B, C   }
s2 = {A, B, C, D}
s3 = {   B, C, D}

Then the most common subset of size $\ge k=2$ is {B, C}. As another example, if I have:

s1 = {A, B, C  D}
s2 = {A, B, C, D}
s3 = {   B, C, D}

Then the most common subset of size $\ge k=2$ is {B, C, D}. It's important that in this instance the algorithm would give me {B, C, D} and not {B, C}, {B, D} etc. Note that I'm not interested in the longest common subset (a different problem), I'm interested in the longest most common subset if you will. I also don't care about enumerating all the different subsets, I just want to find the most common.

Is there an efficient algorithm for this problem?

I have an algorithm for this problem, but I don't think it's very efficient. For $k=2$ I enumerate all subsets of size 2 and count how many times each one appears in the collection. If the most-frequently occurring pair is more frequently occurring than any other pair then that must be the most common subset. If there is more than one with the same (maximum) frequency then I look at the sets they are contained in. If these overlap exactly then I take the union of the pairs and that gives me the most common subset (with size > 2).

I think this could be related to the maximum clique problem but I'm not certain.

Note that just taking the intersection does not give the correct answer.  For instance, if I have

s1 = {A, B      }
s2 = {      C, D}
s3 = {A,    C, D}

then the intersection is the empty set, but the most common subset is {C, D}.

This problem is known as frequent itemset mining, or more precisely, maximal itemset mining.  You can take a look at the Apriori algorithm and the FP-Growth algorithm.


Can we recognize the difference of two strings of $2^n$ length using polynomial size strings? Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that
$$\forall s_1,s_2 \; \exists i \in \{1,\cdots,n^c\} \; f_i(s_1)\neq f_i(s_2),$$
Where two strings $s_1,s_2$ have length $2^n$ and $\forall i\in\{1,\cdots,n^c\}, \; f_i(s_j)\leq n^d, \;  j\in \{1,2\}$?

It seems a little similar to hash functions but since we don't have any restrictions (e.g. having uniform distribution or being oneway) our hands are open to define whatever we like.

I think it's not possible. Because we have $2^{2^n}$ strings of size $2^n$ and transformring them into polynomial size strings means we have put many strings in a single string. But when I make an example this comes to my mind that maybe by defining a good design for each function we can recognize the difference by probability one.

One example can be:

For $c=3$ and $d=1$,

$f_1$: it takes string of length $2^n$ and transforms it to $mod\, n$.

$f_2$: it takes string of length $2^n$. (suppose we have divided $2^{2^n}$ strings into $\frac{2^{2^n}}{n}$ collections) If the input belongs to $i$th collection, $f_2$ transforms it to $i$.

$f_3$: it takes string of length $2^n$ and transforms it to the number which shows its $1$s number.

The probability that for two strings $s_1$ and $s_2$, these three maps $f_1, f_2,f_3$ be the same would be
$$\frac{1}{n}\times \frac{1}{n} \times \frac{1}{2^{2n}}$$
That is negligible.

So my question is that can we ever understand the difference of two long strings with probability $1$ using polynomial size strings?

There is no sequence of functions $f_1,...,f_{n^c}:\{0,1\}^{2^n}\rightarrow\{0,1\}^{n^d}$, such that for all $s_1\neq s_2\in\{0,1\}^{2^n}$ $\exists i\in\{1,...,n^c\} : f_1(s_1)\neq f_i(s_2)$.

Examine the function $F:\{0,1\}^{2^n}\rightarrow \prod\limits_{i=1}^{n^c}\{0,1\}^{n^d}$ defined by $F(s)=\left(f_1(s),f_2(s),...,f_{n^c}(s)\right)$.

The domain of $F$ is of cardinality $2^{2^n}$, while its range is of cardinality $\left(2^{n^d}\right)^{n^c}=2^{n^{c+d}}$. Since for large enough $n$ it holds that $2^{2^n}>2^{n^{c+d}}$, $F$ is not one to one, and thus the condition is not satisfied.


Examples of exact computation of Kolmogorov complexity? First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed exactly and not approximately through practical compression algorithms.

Second question and I quote from the "Elements of Information Theory" textbook:
"one can say “Print out the first 1,239,875,981,825,931 bits of
the square root of e.” Allowing 8 bits per character (ASCII), we see that
the above unambiguous 73 symbol program demonstrates that the
Kolmogorov complexity of this huge number is no greater than (8)( 73) =
584 bits. The fact that there is a simple algorithm to
calculate the square root of e provides the saving in descriptive complexity."
Why take the 584 bits as an upper bound for the KC and not include the size of the actual "simple algorithm" that calculates the square root of e?? It is like cheating...

The underlying problem with the example you quote is that it's informal and completely imprecise. As you say, why don't we include the size of the "simple algorithm"? Why are we allowed to assume that it is known what "$e$" is?

Formally, Kolmogorov complexity is defined with respect to a particular encoding of Turing machines.  If you fix an encoding, then the Kolmogorov complexity of a string $x$ is $K(x)$, the length of the shortest encoding of a Turing machine that prints that string when started with empty input.  (Informally, but still reasonably precisely, you can think of Turing machine encodings as programming languages, and the encoding of a specific Turing machine is a program in that language.)

A key point is that, if we choose different encodings, we get different values for the Kolmogorov complexity.  At the level of the informal example, we could both agree that "DO IT!!" means "Print out the first 1,239,875,981,825,931 bits of the square root of e", so now that has very low Kolmogorov complexity. Because of this, it's very unlikely that anyone has sat down and figured out the exact Kolmogorov complexity of some nontrivial string with respect to some specific Turing machine encoding. It would be very difficult to do, and nobody cares about the answer because, in a sense, it's just an artefact of the choice of Turing machine encoding. Unlike actual programming languages, there isn't really any standard scheme of coding Turing machines as strings, so all your hard work would just be proving an uninteresting fact about your arbitrary choice of coding.


How hard is finding the shortest path in a graph matching a given regular language? Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some alphabet $\Sigma$. We are also given a description of an NFA $M$ (or DFA, or regular expression) accepting some regular language $L(M) \subseteq \Sigma^*$, and two vertices $s, t \in V$.

The problem is to find the shortest path in $G$ from $s$ to $t$ whose edge labels form a string that is a member of $L(M)$. That is, we only consider paths $e_1, e_2, \dots, e_k$ where $\ell(e_1) \ell(e_2) \dots \ell(e_k) \in L(M)$.

Can this problem be solved in time polynomial in $|V|$, $|E|$, and $|M|$?

This question was inspired by these other questions about special cases of this problem.

This problem can be solved in polynomial time by a product construction. Construct the graph $G^\prime$ as follows:

The vertices of $G^\prime$ are $(V \times M) \cup \{\#\}$, i.e. all pairs of a vertex of $G$ and a state of $M$, together with an extra vertex identified by the arbitrary symbol $\#$.
For each edge in $e \in E$ from $v_1$ to $v_2$, add an edge in $G^\prime$ from $(v_1, m_1)$ to $(v_2, m_2)$ with weight $w(e)$ if and only if there is an edge in $M$ from $m_1$ to $m_2$ that is labeled $\ell(e)$.
For each accepting state $m$ in $M$, add an edge in $G^\prime$ from $(t, m)$ to $\#$ with weight 0.

Then the shortest path in $G^\prime$ from $(s, m_0)$ to $\#$ (where $m_0$ is the initial state of $M$) gives the shortest path in $G$ from $s$ to $t$ matching $L(M)$. There cannot be a negative cycle in $G^\prime$, since dropping the $m$ states from the vertex labels would give a negative cycle in $G$, which we are assuming does not exist.

This also answers the question if $M$ is a DFA or regular expression instead of an NFA, since these can be converted to an equivalent NFA in polynomial time. We can also directly handle NFAs with $\varepsilon$-transitions: if $M$ contains an $\varepsilon$-transition from $m_1$ to $m_2$, add an edge in $G^\prime$ with weight 0 from $(v, m_1)$ to $(v, m_2)$ for each $v \in V$.

For fixed $M$, the product graph $G^\prime$ has only linearly more vertices and edges than the original graph $G$. This means that any fixed problem of the form "find the shortest path that visits edges in such-and-such order", such as the problems linked in the question, can be solved just as fast as the ordinary shortest path problem asymptotically.

As an implementation detail, note that there is no need to actually write down the whole product graph in memory. The vertices and edges can be generated dynamically while running the shortest path algorithm, which allows unused vertices to be skipped entirely.


Are assembly languages untyped? I'm writing my Bsc thesis about type systems of various languages and I want to have a short section about assembly languages. Initially I thought I'll bring up assembly as a counter example to languages with advanced type systems. My goal was to explore the reasons why assembly omits most (all?) type system features but eventually I found papers about typed assembly languages and I started to get confused.
So here are my questions:

Can we say that assembly is generally untyped? If so, what is the reason we don't have assemblers with advanced types and type checkers?
Arguments for having a typed assembly language?

Here is a list of papers about typed assembly languages from the end of the last century: http://www.cs.cornell.edu/talc/papers.html.
Links to other papers are highly appreciated!

Assembly language is normally untyped, in the sense that there is no type-checking.  Adding type-checking is a non-trivial research challenge (hence the papers you see).  Papers on typed assembly language should explain the motivation.  One application is that they can be used to support proof-carrying code, which can be used to securely execute untrusted code.  Another potential application is to support formal verification.  But I suggest reading some of the key papers to see what they say about the applications and motivation for typed assembly language.

You can find other papers yourself by doing a literature search -- see https://crypto.stackexchange.com/q/8316/351.


How important is to formulate a convex optimization for a proposed algorithm? I proposed a new sparse coding algorithm which has good results compared to the baselines, however, it has a non-convex optimization framework.
I solved the problem using a general solver (e.g. Matlab), and although the solution is local optimum, it is still better than other relevant approaches.
So how important is to formulate the problem in a convex setting? especially for publishing the work.

I don't know whether any of us can predict how reviewers or your community will react, especially without seeing the manuscript; probably your best bet is to talk to your advisor or to collaborators or colleagues and ask them for their advice.  You might also ask them if they'd read a draft of your paper.

My expectation is that it might depend on whether your field values provable results ("theory"), or pragmatic empirical results ("engineering").  The benefit of a convex formulation is that it allows proving some theorems about the approach, e.g., that it will always find the optimum under certain conditions.  The benefit of your approach is that it seems to get better results in practice, at least on the workloads you've been testing it on.  I can't tell you which your community will value more highly.


Boosting algorithms: Confusion between "weak classifiers" versus "number of boosting rounds" I've been reading up on boosting algorithms.

I understand that the main crux of the algorithm is to build weak classifiers that are slightly better than random guessing, and then to add them up so that we end up with a strong classifier. This is done via "boosting rounds".

With different papers using different variables, like k, n, m, etc, it's gotten a bit confusing.

I just want to confirm, if I run a boosting algorithm for, say 150 rounds, is that equivalent to saying that I'm training 150 weak classifiers? I mean, is a weak classifier the output of one boosting round?

I went back to the original paper from the literature by Schapire (http://www.cs.utah.edu/~piyush/teaching/brief_intro_boosting.pdf) and it does sound like a weak classifier is the output of a boosting round. Consider how the output of the overall classifier is $$H(x)= \text{sign}\left(\sum_{t=1}^T\alpha_th_t(x)\right)$$ which is expressing a threshold for the sum of $T$ weak classifiers.


How to compute Jacobi symbol efficiently? How do I compute the Jacobi symbol $(N|A)$ efficiently?

In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod_i Q_{p_i}(A)$ where $p_1, \dots , p_k$ are all the (not necessarily distinct) prime factors of $N$ (i.e., $N =\prod_i p_i$), and where $Q_p(A)$ is defined as below (i.e., $Q_p(A)$ is the Legendre symbol $(A|p)$).

Arora and Barak claim that the Jacobi symbol is computable in time $O(\log A \cdot \log N)$.  How do I see this?  What algorithm can be used to compute the Jacobi symbol like this?

Motivation:

Sanjeev Arora and Barak sketch a proof that $PRIMES$ is in $BPP$. First they define a function $Q_N(A)$

$$Q_N(A) = \begin{cases}
  0, & \text{if } \gcd(N,A) \ne 1, \\
  1, & \text{if } A \text{ is a quadratic residue modulo $N$} \\
  -1, & \text{otherwise}.
\end{cases}$$

Then they state the following properties:

For every odd prime $N$ and $A ∈ [N − 1]$, $QR_N (A) = A^{\frac{(N−1)}{2}}
\pmod N$.
The Jacobi symbol is computable in time $O(\log A \cdot \log N)$.
For every odd composite $N$, $|\{A ∈ [N − 1] : gcd(N, A) = 1 \text{ and } (A|N) = A^{\frac{(N−1)}{2}}\}| \le \frac{1}{2}|\{A ∈[N − 1] : gcd(N, A) = 1\}|$

Then they give the corresponding algorithm :
Choose a random $1 \le A \le N$, if $gcd(N, A) > 1$ or $(A|N) = A^{\frac{(N−1)}{2}}
\pmod N$ then output “composite”, otherwise output “prime”.

If all the above 3 properties hold then I can see that $PRIMES$ is in $BPP$, but I am unable to prove property 2, regarding the Jacobi symbol.

The Wikipedia article on the Jacobi symbol describes an efficient algorithm for calculating it which uses quadratic reciprocity and operates similarly to the GCD algorithm.