Are there any estimated, imperfect or fuzzy sorting algorithms? I'm implementing some estimation metrics that take samples of optimisation functions and estimate their properties. One of the metrics requires the data to be sorted; however, since the metric is only an estimation, I was wondering if I could get a comparatively accurate result if the data wasn't sorted precisely, but well enough.

I would expect data could be nearly sorted in less time than actually sorting it. However, I can't find any algorithms that will do this, which I find rather odd, so I thought I'd ask around here.

My idea of "imperfectly sorted" is quite loose. It could, for example, mean:

Many elements are perfectly sorted, but some are not
Adjacent elements are not necessarily in the correct order, but when comparing groups of elements, the elements increase on average; if plotted, there would be a visible general upwards trend

For the first definition above, I suppose you could take a sub-sample of the data and just quick-sort that, but I don't imagine it'll get you much of a performance improvement without seriously reducing the quality of the estimation.

It might also be possible to take something like quicksort and limit the depth of the recursion.

Do imperfect sorting algorithms exist? Can they significantly out-perform regular sorting algorithms?

The term you're looking for is approximate sorting. This is a topic that, as greybeard mentions in a comment, was more popular back in the 90s. But it's quite helpful for presorting (e.g. getting an array a little bit sorted to ensure that Quicksort doesn't get stuck in its worst case), and this is what's led to most of the research in the area.

You can, in fact, make it somewhat faster than full sorting. Giesen, Schuberth, and Stojaković showed that you can get $n$ elements sorted to a Spearman distance (*) of $\frac{n^2}{\nu(n)}$ in $O(n \min(\log n, \log \nu(n)))$. So the more you're willing to sacrifice accuracy (the smaller you make $\nu(n)$), the faster the algorithm can run.

Giesen, Schuberth, and Stojaković also present a very simple algorithm to do this approximate sorting, either deterministically or with a bit of randomness mixed in. The full details are in the linked paper, but basically they use Quicksort's partitioning a limited number of times and don't care about the order of the elements between the partitions, as long as they end up in the right "bin". If you pick your partitions well, this is in fact equivalent to running Quicksort and limiting the recursion depth.

(*) The Spearman footrule distance between two sequences is the sum of the distance between each element's intended position and its actual position. So if you swap two elements, that leads to a Spearman distance of 2: those two elements are each one position away from their intended place.


Does MiniSAT need exponential time? I'm asking for a sequence of instances for SAT, one instance for each length, such that the sequence takes exponential time with MiniSAT.

When pure CDCL solvers (such as MiniSAT, I believe) are run on unsatisfiable instances, their transcript can be converted to a Resolution refutation of the instance. In particular, the running time of the solver is lower bounded by the length of the smallest Resolution refutation of the instance. There are instances which are known to take exponential length to refute in Resolution, for example the Pigeonhole Principle on $n+1$ pigeons and $n$ holes. Such instances will take exponential time to refute on any pure CDCL solver.


Is this index algorithm worth anything? I have theorised a indexing algorithm (like a B-tree).

However, there's a mental block stopping me actually implementing it.

The algorithm comes in to forms:

form 1:

A look up time of O(1) to O(log2(n))

Each value in the index will have metadata associated to it that is of the size log2(n)*memory address size

form 2:

A look up time of O(1) to O(log2(n)/2)

Each value in the index will have metadata associated to it that is of the size log2(n)*2*memory address size

Unlike B-tree/other index algorithms, there's no time penalty for a add/deletion.

You can for example do a add, then do a search straight after (with no waiting in between).

You get a faster search at the expense of more metadata (memory) along with being able to insert/delete in real time.

You can also do sequential access/search sequential data values fast.

I can't find any other algorithm that has that attributes and time complexity.

If I can get it to work, I plan to sell it.

My question is; would this actually worth anything to anyone/or useful in any particular application?

Or is the amount of memory it uses too much of a deal breaker?

If I understand correctly, you have designed a data structure for what is known in the scientific literature as dynamic dictionary problem: keep an index I that can dynamically maintain a set S supporting queries like "is $x \in S$?" under a stream of insertions/deletions.

There are many solutions to this problem. The classical solution is to use a dynamic perfect hash function, which takes $O(1)$ worst case lookup time and $O(1)$ expected amortized update time (it's randomized) and $O(n)$ bits of space.

An arguably more practical solution to your problem is given by Cuckoo hashing, that has the same theoretical bounds of the previous solution but is much easier to understand and implement, and has reportedly better experimental performances.

These solution take much less space than your solution and have favorable time bounds (even if the bound on the update time hold only in expectation).

Moreover, your claim that "add/deletion have no penalty" is unclear to me. If your claim is that an insertion/deletion takes $O(1)$ time, then that's obviously impossible because you cannot build a data structure of size $\Omega(n \log n)$ with time complexity $O(n)$, and if you mean that they take as much time as a look-up, then your solution is no better than any self-adjusting binary tree, like AVLs or Splay trees.

Provided that this problem is well-studied and that there are quite a few high-quality implementations around, I think it is quite hard to design a new competitor that might enjoy commercial success.


Variation of the dining philosophers: is the standard solution still valid? I have a problem that is almost equal to the standard one of the dining philosophers, but has a quirk: while a philosopher thinks, he still holds the fork on his left.

If after the period of thinking (which isn't infinite), I release the fork on the left and then apply the normal solution (that is, acquire forks in the order of their priority), then would this solution be correct for this problem?

If the philosopher eats (holding both forks), drops the right fork and thinks for a while, and then drops the left fork to take a nap (or something similar), it is just the original problem: Each philosopher must ensure getting both forks without deadlock. Take a look at Allen B. Downey's "The Little Book on Semaphores" for in-depth discussion (this problem is hard!).


General theory on Hash Functions? I'm a computer engineer and I've met hash functions theoretically speaking in "algorithms and data structure" and then in several applications (like databases, operating systems, computer architecture etc).

But I was wondering if there's some general theory about these functions and, specifically, if there's a general way to build such functions.

There is a general cryptographic theory of provably secure hash functions. There are several inequivalent notions of security. Hash functions are a cryptographic primitive, and the goal of cryptography is to explore relations between different primitives – can one primitive be constructed using the other.

All of this, however, has no relevance on hash functions practically used, for various reasons. Practically, hash functions come in two flavors: cryptographically secure and not cryptographically secure. There isn't really any theory regarding the construction of both types. Cryptographically secure hash functions are constructed according to various and changing heuristic principles, but their strength lies in the community trying to break them and failing. Non-secure hash functions have other properties, and successful one have emerged from practice.

Don't construct your own hash function. If you attempt to construct a cryptographically secure hash function, you will probably fail unless you're an expert. Constructing a non-secure hash function is less harmful, but still, existing ones are probably better than one you would come up with.

If you want a hash function with a particular integer range $[a,b]$ (as indicated in the comments), there are two basic options:

If your function doesn't need to be cryptographically secure, you can use the formula $h \pmod{b-a+1} + a$, where $h$ is a general-purpose hash function. The range of $h$ should be large compared to $b-a+1$, unless $b-a+1$ happens to divide the range of $h$.
If your function does need to be cryptographically secure, you have to be more careful. In that case I suggest you ask a question on the dedicated crypto stackexchange site.


Hardness of the Minimum Steiner Tree problem on grid Is the Minimum Steiner Tree problem $NP$-hard even on (2D, unweighted) grid graph ? A proof (for either case) will be very appreciated.

This problem is $NP$-complete as shown by a reduction from Rectilinear Steiner Minimum Tree (RSMT) problem. Consider the Hanan grid: https://en.m.wikipedia.org/wiki/Hanan_grid. Since Planar-3-SAT is strongly NP-complete, we can subdivide every segment of this grid into unit segments to obtain a grid graph.


Is string matching and replacement considered in formal languages? Is string matching and replacement, as an operation on strings or on formal languages, considered in  formal languages?

For example, the family of regular languages, or the family of
context free languages, ..., are closed under certain string
operations.

I would wonder if these families or some others may be closed under
string matching and replacement?
Are string matching and replacement equivalent to some combination
of other string operations?
Or is matching and replacement considered in formal languages in
some other ways?

Thanks and regards!

Match & replace is a special case of rational transduction, a quite powerful class of string mappings with a number of nice properties.

The classes of regular, context-free and recursive enumerable languages are all closed against rational transduction (source), so this carries over to match & replace.

It does not seem as if the necessary elementary operations had a representation in formal language theory.


Seating Chart Optimization I'm trying to find an algorithm to solve the seating chart problem. The goal is to place pepole at one (or multiple) tables such that the overall happiness is maximized.

Each seat has neighbors. A person on a seat can talk to persons on neighboring seats (note that these neighbors normally sit next to each other or on the opposite side of the table).

Example of a table with 4 seats on each side:

1 2 3 4
8 7 6 5

6 has neighbors 2, 3, 4, 5 and 7, 8 has neighbors 1, 2, 7

There's a matrix describing how well two persons get along with each other. This is a value between 0 and 9 (the relation value). Relations are symmetrical.

Example of a relation matrix with four people:

  A B C D
A 0 2 0 5
B 2 0 3 6
C 0 3 0 1
D 5 6 1 0

The happiness of a single person is the sum of the relation values of all neighboring persons.

How would you find a solution that maximizes the overall happiness?

I use an ILP. I hope there are better solutions available.

Let H be your $n\times n$ happiness matrix. I use $n^2$ 0-1-variables $uv_{ij}$ per edge $uv$ in the seating graph. $uv_{ij}$ is 1 if person $i$ sits at place $u$ and person $j$ sits at place $v$.

maximize $\sum_{uv\in E} h_{ij} \cdot uv_{ij}$
s.t.
$\sum_{i,j} uv_{ij}=1$ for all $uv$, each edge gets exactly one neighbor configuration
$\sum_{j} ux_{ij} = \sum_{j} uy_{ij}$ for all edges $ux$ $uy$ that share an endpoint and all i, if $i$ sits at $u$ according to $ux$, they must also sit at $u$ according to $uy$


Parallel or efficient computation of value with momentum I have a matrix $A$ with dimensions $M \times N$ and I want to compute $A'$ such that:

$$
A'_{i,j} = \alpha A'_{i,j-1} + (1 - \alpha) A_{i,j} \\
1 \leq i \leq M, 1 \leq j \leq N, \alpha \in [0, 1]
$$

Where $A'_{i,0}$ is some given constant.

I want to perform this computation as part of a machine learning training process on the GPU (I am using TensorFlow), but the only way to do it I can think of is with a loop over $j$, which makes the training tremendously slower (even if it's a TensorFlow loop, not a regular Python loop).

I know that being each value dependant on the previous one this is not a parallel-friendly computation, but I was wondering if there is some trick or reformulation that I am missing to make this in a smarter way.

I have noted that the above expression can be rewritten as:

$$
A'_{i,j} = \alpha^j A'_{i,0} + \sum_{1 \leq k \leq N} (1 - \alpha) \alpha^{j-k}A_{i,k}
$$

Which makes me think I can define a $M \times N$ matrix $P$ as:

$$
P_{i,j} = \alpha^j A'_{i,0}
$$

And a $N \times N$ matrix $R$ as:

$$
R_{i,j} =
\begin{cases}
\alpha^{j-i} & \text{if}~i \leq j \\
0 & \text{otherwise}
\end{cases}
$$

And so I think that I would have:

$$
A' = P + (1 - \alpha) A R
$$

Which would be a more parallelizable computation. The only challenges would be to efficiently construct $P$ and $R$ (which is probably not that hard) and, more importantly, the memory usage if $N$ is big (which unfortunately in my case it kinda is).


Set of all countably infinite strings over a finite alphabet >1 Is the set of all countably infinite strings over a finite alphabet that contains more than one letter countably infinite?

Take the alphabet $\Sigma = \{0,1\}$ and consider strings whose positions are indexed by $\mathbb{N}$ (also known as $\omega$-words).  There is a one-to-one correspondence between these strings and subsets of $\mathbb{N}$ given by $x_0x_1x_2\dots \leftrightarrow \{i\in\mathbb{N}\mid x_i=1\}$. Therefore, there are as many $\omega$-words as there are subsets of $\mathbb{N}$, and this is an uncountable number.

This holds for any countably infinite word length.


How to store set of long char strings to search for long char string key I have a set of several thousand strings of max length 1024 (containing all visible ASCII chars plus space) I need to store to make it fast to search for an exact match of a key.  What is the best algorithm to store the set and to search for a match?

One approach is to use a suffix array (or suffix tree).  That allows very fast searching for a match.

Given multiple words, there is a standard way to compute a suffix array (or suffix tree) associated with them: concatenate them, separated by some separator.  For instance, if the words are APPLE, CAT, and DOG, you obtain the string APPLE\$CAT\$DOG\$.  Then, compute the suffix array/tree of that single long string.


Can any finite problem be in NP-Complete? My lecturer made the statement

  Any finite problem cannot be NP-Complete

He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of solutions but I can't remember exactly what he said. I wrote down the note that I've quoted but still don't really understand.

Sudoku's are NP complete if I'm not mistaken. The clique problem is also NP-Complete and if I had a 4-Clique problem is this not a finite problem that is  NP-Complete?

If a finite problem is NP-complete then P=NP, since every finite problem has a polynomial time algorithm (even a constant time algorithm).

When we say that Sudoku is NP-complete, we mean that a generalized version of Sudoku played on an $n^2 \times n^2$ board is NP-complete.

Finally, the 4-clique problem, while not a finite problem (the input graph has unbounded size), is an easy problem which has a polynomial time algorithm.


Calculate the area of the shape created by multiple paths I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example:

Basics

4 separate paths (A,B,C,D) which are a collection of vertices (A1,A2,...)
Area desired is represented by green

Edge Cases

As shown with B, a path might have segments that don't contribute to a filled shape
As shown with C, a path might be completely enclosed by other paths and therefore should basically be ignored.
As shown with D, paths may create independent shapes
As shown with A and B, it should be a union of all the shapes

My first question is if an algorithm for this already exists. If it does, it would save me a lot of effort :). I tried searching around but I don't even know how to describe this problem concisely.
Assuming one doesn't exist for this exact purpose I have to move on to figuring it out myself. I'm assuming the right data structure for the job is a graph. I'm thinking I will add points for each intersection (highlighted in red) as I insert paths into the graph.
Then "all I need" is an algorithm for tracing around the outside of each shape because calculating the area of those irregular polygons will be simple. Does something like that already exist? My primary hangups when I think about how to do this are:

What vertex do I "start" at?
How do I account for multiple shapes (D as well as A,B,C)?
How do I account for the parts of shapes like formed by A1,A5,A5 where I'll be visiting that intersection point multiple times?

I'm not necessarily looking for a complete solution, I'd love thoughts on if you think I'm approaching this the best way so far and if you have any ideas/suggestions on how to achieve this.
Thanks in advance!

With the help from some of the hints on this post and elsewhere, I came up with a solution.
The Data Structure
The data structure is relatively simple. It is a collection of Nodes that are connected by Edges.

Each node stores the coordinates of where it lies in space and each segment is represented by two directional edges, one in each direction. Each intersection of line segments is broken up with a new Node. Note the coordinates of the intersections are left off the diagram but are included in the data structure.
The Algorithm
Find All Cycles

Pick any edge and choose the next edge that is closest to clockwise from the edge you entered the node on.

Record whether the angle between the connecting edges is a reflex angle (> 180 degrees) or not.

Record the series of nodes visited

Mark the edge as used

Follow that new edge to the next node and repeat until reaching the first node again.

At the end, the cycle will have the points that it is composed of and a count of reflex and non-reflex angles. If there are more reflex angles, it is considered to be an outside cycle and is thrown out. Otherwise, it is included in a preliminary list of polygons to include in the final result.
Repeat this cycle finding process until every edge has been used.
Filter Polygons
Filter out any resulting polygons that are entirely inside another. This can be done by testing only the first point of one polygon to see if it's inside another. That's because we know we will never have any intersecting polygons.
Calculate the Area of Each Remaining Polygon
At this point, we just need to calculate the area of each polygon and add them together for our solution.
Some Details
It's important to note that in the case where we get to a node and the only remaining edge is the returning edge, it counts as a 360 degree angle and therefore a reflex angle.
Also, it's important to note that each angle of each cycle must be counted towards the reflex and non-reflex count, including the first and last. Otherwise, a plus sign arrangement of simple paths (+) will result in a valid polygon.
Example
All of the cycles from my original example are represented here:

For more information on my process and a walk through of the algorithm, you can see my case study.


In the shor's quantum circuit, what is the transformation of the modular operating gates? I know different parts of this circuit, just I have a problem with that part that I circled in picture.
I want to know the function of that part.
If you have useful information about it, please share it with me.
Thank you so much.

It's a modular multiplication gate. It permutes the states such that, for all $k$ below $N$, state $|k\rangle$ becomes state $|k \cdot c \pmod{N}\rangle$ where $N$ is the number being factored and $c = b^{2^{2n-1}} \pmod{N}$ is a classically computed constant and $b$ is the base value chosen randomly at the start of the algorithm.


NP-hard proof with reduction from two known NP-hard problems As I understand, to show that a certain problem P is NP-hard we can reduce a known NP-hard problem, Q, to problem in P in polynomial time. To show that the problem P is NP-hard in strong sense, we can reduce a know NP-hard problem Q to problem P in pseudo polynomial time.
Is it possible to show that a certain problem P is NP-hard by reducing two known NP-hard problems Q and Q' to a problem in P?

If you can reduce one NP-hard problem to a problem $L$, then $L$ is NP-hard. If you can reduce a second NP-hard problem to $L$, then so what? You already know that $L$ is NP-hard. How could reducing more problems to $L$ make $L$ easier (e.g., not NP-hard)?

It's like saying, "If I have one million dollars, I'm rich. If I have two million dollars, am I still rich?"


Tarjan's Strongly Connected Component algorithm I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net):

On line 33 why is node.lowlink = min(node.lowlink, n.index) — shouldn't it be same as line 31: node.lowlink = min(node.lowlink, **n.lowlink**)?
Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by lowLink should be the SCC?
Is it ever true that after we recurse in line 30, n may not be in stack? If not and (1) is true we can simplify line 29-33 as follows:

if n.index == -1
   tarjanAlgorithm(n, scc, s, index)
if stack.contains(n)
   node.lowlink = min(node.lowlink, n.lowlink)

I went ahead and implemented the algorithm in Scala. However, I dislike the code - it is very imperative/procedural with lots of mutating states and book-keeping indices. Is there a more "functional" version of the algorithm? I believe imperative versions of algorithms hide the core ideas behind the algorithm unlike the functional versions. I found someone else encountering the same problem with this particular algorithm but I have not been able to translate his Clojure code into idomatic Scala.

Note: If anyone wants to experiment, I have a good setup that generates random graphs and tests your SCC algorithm vs running Floyd-Warshall

Here is the full pseudocode (© Algoritmy.net, MIT licensed).

index = 0

/*
* Runs Tarjan's algorithm
* @param g graph, in which the SCC search will be performed
* @return list of components
*/
List executeTarjan(Graph g)
Stack s = {}
List scc = {} //list of strongly connected components
for Node node in g
if (v.index is undefined)
tarjanAlgorithm(node, scc, s)

return scc

/*
* Tarjan's algorithm
* @param node processed node
* @param SCC list of strongly connected components
* @param s stack
*/
procedure tarjanAlgorithm(Node node, List scc, Stack s)
v.index = index
v.lowlink = index
index++
s.push(node) //add to the stack
for each Node n in Adj(node) do //for all descendants
if n.index == -1 //if the node was not discovered yet                  // <--- line 29
tarjanAlgorithm(n, scc, s, index) //search
node.lowlink = min(node.lowlink, n.lowlink) //modify parent's lowlink  // <--- line 31
else if stack.contains(n) //if the component was not closed yet
node.lowlink = min(node.lowlink, n.index) //modify parents lowlink     // <--- line 33

if node.lowlink == node.index //if we are in the root of the component
Node n = null
List component //list of nodes contained in the component
do
n = stack.pop() //pop a node from the stack
component.add(n) //and add it to the component                         // <--- line 40
while(n != v) //while we are not in the root
scc.add(component) //add the compoennt to the SCC list

1... On line 33 why is node.lowlink = min(node.lowlink, n.index) — shouldn't it be same as line 31: node.lowlink = min(node.lowlink, n.lowlink)?

The code works either way.  The two possibilities are:

I. n.index == node.index, which means the assignment will never change the value of node.lowlink, or

II. n.index < node.index, which means setting node.lowlink to either n.index or n.lowlink will cause node.index to be unequal to node.lowlink, guaranteeing that node will be part of the SCC containing everything on the stack back to the node with an index matching n.lowlink.

  2... Do we have to generate the components on line 40 in the while loop as we pop? Isn't it true that when the algorithm finishes, all the vertices grouped by lowLink should be the SCC?

No, that's not true.  The components of any particular SCC are not guaranteed to have the same .lowlink value, so you can't partition the vertices into SCCs that way.  The .lowlink values are used to determine when to pop the stack; the stack determines what is in an SCC.

  3... Is it ever true that after we recurse in line 30, n may not be in stack?

Yes, n may not be in the stack.  n could be a vertex belonging to a previously identified SCC.  There's a forward link to n obviously but there may be no back link from n or its SCC to the current SCC.


Is there any use case for the bottom type as a function parameter type? If a function has return type of ⊥ (bottom type), that means it never returns. It can for example exit or throw, both fairly ordinary situations.

Presumably if a function had a parameter of type ⊥ it could never (safely) be called. Are there ever any reasons for defining such a function?

One of the defining properties of the $\bot$ or empty type is that there exists a function $\bot \to A$ for every type $A$. In fact, there exists a unique such function. It is therefore, fairly reasonable for this function to be provided as part of the standard library. Often it is called something like absurd. (In systems with subtyping, this might be handled simply by having $\bot$ be a subtype of every type. Then the implicit conversion is absurd. Another related approach is to define $\bot$ as $\forall \alpha.\alpha$ which can simply be instantiated to any type.)

You definitely want to have such a function or an equivalent because it is what allows you to make use of functions that produce $\bot$. For example, let's say I'm given a sum type $E+A$. I do a case analysis on it and in the $E$ case I'm going to throw an exception using $\mathtt{throw}:E\to\bot$. In the $A$ case, I'll use $f:A\to B$. Overall, I want a value of type $B$ so I need to do something to turn a $\bot$ into a $B$. That's what absurd would let me do.

That said, there's not a whole lot of reason to define your own functions of $\bot\to A$. By definition, they would necessarily be instances of absurd. Still, you might do it if absurd isn't provided by the standard library, or you wanted a type specialized version to assist type checking/inference. You can, however, easily produce functions that will end up instantiated to a type like $\bot\to A$.

Even though there isn't much a reason to write such a function, it should generally still be allowed. One reason is that it simplifies code generation tools/macros.


Minimum-weight shortest-path tree How can we compute the shortest-path tree of minimum total weight for a given connected graph?

I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one shortest-path tree with different total weights.

The above picture shows one such example (where $a$ represents the starting vertex).

Is there a way to find the shortest-path tree of minimum total weight without inspecting every possible shortest-path tree?

Dijkstra's algorithm will not allow you to obtain such minimum-weight shortest-path tree due to its greedy nature: once it obtains the shortest path to a vertex, the algorithm never reconsiders this vertex again.

One possible approach to obtain such a tree is to apply a small extension to Bellman–Ford's algorithm. Whenever there is a tie in step 2 of the algorithm $-$ that is, whenever there is a tie between (1) a newly computed distance between the starting vertex $s$ and a vertex $v$, and (2) the current best shortest path between $s$ and $v$ $-$ compute how much weight each of the two shortest path candidates adds to the current tree (and keep the path that minimizes this value). The current tree is available in the predecessor array, which stores the tree as an array of parent pointers.

Applying the above solution, you are, in effect, checking all possible shortest paths, so I presume that the answer to your last question is no.


When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis I've been exploring the differences between Context Sensitive Analysis (CSA) and Context Insensitive Analysis (CIA), members of inter-procedural static analysis.  The problem I'm coming up against is when to use one over the other.

Namely, suppose the following context:

The input program is in Static Single Assignment form.  We have a machine that has no memory hierarchy.  All it can do is store things in registers.  We want host languages to support functions, including non-tail recursion.  Which is to imply, when we call a function, we need to save all variables live across the function into registers and then calculate space requirements to see if we have enough registers to execution the function.

To do so, we need to use both CIA and CSA.  Though I'm not entirely sure why that is the case.  I've speculated a few ideas:

reaching definitions require a tighter bound,
invalid paths through recursion could ruin analysis,
there is some dark magic here that I'm unaware of.

But ultimately, given the context, I'm not sure why we need both CSA and CIA to compute space requirements across function calls.

It's a tradeoff between accuracy vs running time.  CSA often provides more accurate (more precise) results than CIA; but it takes longer.  There's no hard-and-fast rule about when you must use one or the other; rather, you can use either, and you choose where you want to live on that tradeoff.


Lower bound of degree of polynomial approximating parity Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$

It is known [See e.g. Lemma 5 of this lecture note] that any polynomial $f(x_1,\dots,x_n) \in \mathbb{R}[x_1,\dots,x_n]$ of degree at most $\sqrt{n}$ must disagree with $\text{MOD}_2$ on at least a constant fraction of inputs.

  Is this true for a polynomial with degree $n^{0.5+\epsilon}$ for some small constant $\epsilon>0$ ? How about a polynomial with degree $o(n)$?

You can show a polynomial of degree $O(\sqrt{n\log n})$ can agree with parity on all but $o(1)$ fraction of the inputs. (In fact, this argument should work for anything of degree $\omega(\sqrt{n})$).

Let $S = x_1 + x_2 + \dots + x_n$. Note that $\text{MOD}_2(x_1, x_2, \dots, x_n)$ can be written as a single-variable function of $S$. By Lagrange interpolation, there exists a univariate polynomial of degree $O(\sqrt{n\log n})$ in $S$ (and hence in the $x_i$s) that agrees with $\text{MOD}_2$ on the interval $S \in [(n-\sqrt{n\log n})/2, (n+\sqrt{n\log n})/2]$. By the central limit theorem, this range of $S$ accounts for all but $o(1)$ of the $2^n$ inputs $(x_1, x_2, \dots, x_n)$.


CYK - finding the closest word accepted Let's say I have a context-free grammar G and a string S. The normal CYK algorithm outputs that s can not be build using G. How would I find the closest String S' that can be build using G?

Your problem has been solved by Myers, Approximately Matching Context-Free Languages. A more recent algorithm, together with many relevant pointers, is Rajasekaran and Nicolae, An error correcting parser for context free grammars that takes less than cubic time.


What is it called when you classify words into categories, but not by part of speech? I'm looking to classify words into type categories like sushi to food, baseball to sports, happy to emotions, panda to animals etc.

What is this type of classification called? I see lots of NLP-related articles discussing parts-of-speech classifiers. This isn't helpful.

I know any word has many possible categories. For example, panda could be classified as animal, mammal, Ailuropoda (it's genus), or even algorithms (as in, "Google Panda"). I'm open to any of the above to start. My preference would be colloquial rather than scientific (panda to animal).

Ideally it would return probability for different categories. For example, panda might return 0.8 for animal and 0.3 for bear and 0.1 for algorithm.

The name of the classification you are looking for is called Semantic field classification (https://en.wikipedia.org/wiki/Semantic_field). The sort of algorithm you are looking for falls under the category of Statistical Semantic.


Compute RTT in theoretical system This is problem from my Networks class. It wants us to compute the round trip time of a point-to-point network and I'm just not sure which information is pertinent. The question:

NASA    deployed    its latest  622Mbps point-to-point  laser   link    between Earth   and a
new lunar   base.   The distance    from    the Moon    to  Earth   is  approximately   385,000
km, and data    travels over    the link    at  the speed   of  light   3   x   10^8    m/s.

(a) Calculate the minimum RTT for the link

I'm not sure whether I should be using the 622 Mbps or the distance and speed of light. My initial thought was using distance and speed of light. Meaning, the minimum would be (385,000*1000)m /(3x10^8 m/s)*2  = 2.56666 seconds.

But if you use the 622 Mbps you can compute, for the minimum it would be quickest if you only sent one bit, and the other host immediately responded with one bit meaning that the RTT would be 2*(1/(622*1,000,000)) = 3.215 e-9 seconds.

To me it seems like it should be the former, but if the link is 622 Mbps why would it take longer?

EDIT: to clarify don't tell me which answer is correct, as it is homework. I would like to understand the concepts involved with why RTT is unrelated to Mbps.

Why would it take longer than a few nanoseconds to get a message to the Moon and back? Because physics. Nothing can go faster than the speed of light.

Instead of packets on a network, think of suitcases on the baggage reclaim belt at an airport. The number of suitcases the airport workers put on the belt each second is the data rate; the length of time it takes a suitcase to go all the way around the belt is the round-trip time.

Suppose the airport employs more staff to throw luggage around. They can now put, say, twice as many suitcases onto the belt every second, but the belt doesn't move any faster so each individual bag still takes the same amount of time to go around.  They've increased the data rate but not the round-trip time. Because they're putting bags onto the belt more quickly, but the belt itself isn't moving any faster, there will be more bags in transit on the belt at any time.

Suppose that, instead of hiring more staff, they make the belt move twice as fast.  Now, you don't get any more bags per second but each bag only takes half the time to go around. They've decreased the round-trip time but not the data rate. Because bags now get delivered to waiting passengers faster, but they only appear at the original rate, there will be fewer bags in transit on the belt at any time.

So, you see that data rate and round trip time are essentially independent. The data rate is how many bits you can send each second, and the trip time is how long each individual bit takes to reach its destination.  You should now be able to figure out what the round trip time is, and also answer more complicated question like, "How long does it take to get a gigabyte of data to the moon on this link, and receive an acknowledgment that the final packet arrived?"


Fast query on the number of elements in a quarter plane I have a scatter of 2D elements on a 2D plane.
I would like an efficient algorithm to prepare and query the number of points in a quarter plane (inclusive of boundary).
The quarter plane is defined by a point $(x,y)$. All elements $(x', y')$ where $x<=x'$ and $y<=y'$ are in the quarter plane.
For example

I have elements [(1,1), (2,2), (1,2), (3,2)],
My queries are [(1,1), (2,2), (3,3)]

The program should return [1,3,4].
This is for a past competitive programming challenge (WiFi Network problem in this competition)

A 2D Fenwick tree can solve this in $O(\log^2 N)$ time and $O(N^2)$ space for both update and query, when your coordinates are integers and $N$ is the size of the maximum coordinate.
Fenwick trees are nice for competitive programming because they have a really compact implementation, for example in C++:
typedef unsigned long long uw;
uw lsb(uw x) { return x & -x; }
uw  up(uw x) { return x + lsb(x); }
uw  dn(uw x) { return x - lsb(x); }

template<class T> struct Fenwick2D {
  uw n; std::vector<std::vector<T>> b;
  Fenwick2D(uw n) : n(n), b(n+1, std::vector<T>(n+1)) { }

  void increase(uw x, uw y_, T v) {
    for (; x <= n; x = up(x))
      for (uw y = y_; y <= n; y = up(y))
        b[x][y] += v;
  }

  T prefix_sum(uw x, uw y_) {
    T s = 0;
    for (; x >= 1; x = dn(x))
      for (uw y = y_; y >= 1; y = dn(y))
        s += b[x][y];
    return s;
  }
};

And this shows your example from the question:
int main(int argc, char** argv) {
    Fenwick2D<int> fw(4);
    fw.increase(1, 1, 1);
    fw.increase(2, 2, 1);
    fw.increase(1, 2, 1);
    fw.increase(3, 2, 1);
    std::cout << fw.prefix_sum(1, 1) << "\n";
    std::cout << fw.prefix_sum(2, 2) << "\n";
    std::cout << fw.prefix_sum(3, 3) << "\n";
    return 0;
}

This data structure is more general than your problem as well. In general it can increase any grid element $g_{x,y}$ by value $v$ (which decreases for negative $v$), and ask the value of the lower quadrant prefix sum $\sum_{i\leq x}\sum_{j\leq y} g_{i,j}$ for any $x, y$. Note that this means you can get area sums as well using 4 queries by the inclusion-exclusion principle.


Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally:

Let:

$P$ be a polygon consisting of points $\{x_1,x_2,...x_n,x_1\}$
$S$ be a subset of $P$, bounded by points $x_j$ and $x_k$:
$m$ be a number of extra points we can allocate

Then, we want to minimize the area of $P$, using the following means:

modifying the position of points $\{x_{j+1},...,x_{k-1}\}$
adding new points to the interval $(x_j,x_k)$

Here is a very example for $m =1$ (notice that the boundary points $x_j$ and $x_k$ aren't subject to being modified)

So far, the best I can do is a bruteforce solution. Basically try moving the point around in some discrete increments into various directions, then check if it makes sense (see that it does not create intersections within the polygon), and calculate the area. After that, I check which direction gave the best area, and I continue the process again until the area converges.

Obviously this is a flawed solution in that:

It does not guarantee anything, it is just trial and error
It is extremely computationally expensive
It gives rise to certain anomalies

My question is, could there possibly be a better approach, maybe even one that would guarantee an exact solution in polynomial time?

Try all possibilities for vertices $P,Q,R,S$ where $P,Q$ are adjacent and $R,S$ are adjacent (there are $O(n^2)$ possibilities).  For each such possibility, find the best way to add a point $T$ after $P$ and before $Q$, such that $T$ falls on the line segment $RS$.  This involves finding a point $T$ on the line segment $RS$ that maximizes the area of the triangle $PTQ$.  You should be able to do that in $O(1)$ time.  Repeat for each possible $P,Q,R,S$ and take the best one found.  This should yield an $O(n^2)$ time algorithm.

I don't know if it is possible to do better than $O(n^2)$ time.


When is conditional Kolmogorov complexity zero? It seems intuitive that conditional Kolmogorov complexity is only zero when the bitstrings are the same, and otherwise is greater than 0.  I.e. if $b_1 = b_2$, then $K(b_1|b_2) = 0$, otherwise $K(b_1|b_2) > 0$.

However, if that is the case, then we could break a long bitstring into many smaller, different bitstrings, and then use conditional Kolmogorov complexity to establish a lower bound on the long bitstring's Kolmogorov complexity.

E.g., original bitstring is $\mathcal{B}$.  It is broken into different, smaller bitstrings $b_1,b_2,\ldots,b_n$.  We then use conditional Kolmogorov complexity to establish a lower bound on $K(\mathcal{B})$, in the following way,

\begin{align*}
K(\mathcal{B}) &= K(b_1,b_2,\ldots,b_n) \\
&= K(b_1) + K(b_2|b_1) + \ldots + K(b_n|b_1,b_2,\ldots,b_{n-1}) +
 O(log(K(b_1,b_2,\ldots,b_n)))\\
&\geq n.
\end{align*}

The equality is not strict, there are errors involved, which may invalidate the argument.

As the bitstring length grows, we can continue to grow the lower bound $n$ arbitrarily large, since there are a greater number of distinct smaller bitstrings that can be used to construct the large bitstring.  This appears to violate Chaitin's incompleteness theorem, which states with a fixed axiomatic system there is a limit $\mathcal{L}$ above which we cannot prove $K(\mathcal{B}) > \mathcal{L}$.

What am I missing here?

The answer depends on whether your encoding is prefix-free or not, and in the latter case, on your universal Turing machine.

There are two variants of Kolmogorov complexity: one in which the set of programs form a prefix-free code, and one in which there is no such requirement. For the first variant, the Kolmogorov complexity is always positive. For the second variant, the universal Turing machine can do whatever it wants given an empty program (or indeed, any fixed program). You can arrange that $K(x_1|x_2) = 0$ for your choice of $x_1,x_2$, for example.


Show: "Checking no solution for system of linear equations with integer variables and coefficients" $\in \mathbf{NP}$ I've been struggling for a while trying to solve this problem:

Show that the following problem is in $\mathbf{NP}$:

  Check that a system of linear equations with $m$ integer variables and
  integer coefficients has no solution.

Let $L = \{\langle A, b \rangle\ |\ A \in \mathbb{Z}^m\times\mathbb{Z}^m\text{ and }Ax = b\text{ has no solution for }x \in \mathbb{Z}^{m} \}$

(please, feel free to correct if anywhere I'm wrong)

For showing that a language is in $\mathbf{NP}$ we have to construct a Turing Machine, indicating what we have chosen as certificate. If the TM is nondeterministic, then nondeterministically we pick a certificate and check the condition. If it is deterministic, we pass the certificate as one of the parameters (of the two parameters TM. The other parameter is, in this case, the pair $\langle A, b \rangle$).

I'm having trouble trying to choose the appropriate certificate.

My approaches:

1) Certificate: a vector $x \in \mathbb{Z}^{m}$, such that doesn't solve $Ax = b$. Issue: We would have to try every possible $x$ to show that $\nexists$ such vector for which solution may exist...

2) Certificate: Rank of $A$. if the $\mathrm{rank} A \neq m$, then the system has no solution and we $Accept$. Issue: doesn't necessarily mean that $x \in \mathbb{Z}^{m}$.

3) Consider $\overline{L} = \{\langle A, b \rangle\ |\ A \in \mathbb{Z}\times\mathbb{Z}\text{ and }Ax = b\text{ has a solution for }x \in \mathbb{Z}^{m} \}$.

Showing that the system has a solution seems easier than showing that there is no one. I guess the certificate has to be a vector $x \in \mathbb{Z}^{m}$, for which the $Ax = b$ is satisfied. Then, if I'm not mistaking, constructing a polynomial-time deterministic TM for $\overline{L}$ is straight forward. The thing is that this will show that $\overline{L} \in \mathbf{NP}$. This implies that $L \in$ co-$\mathbf{NP}$.

So showing that $L \in \mathbf{NP}$ would be equivalent to showing that co-$\mathbf{NP} = \mathbf{NP}$??

There is a polynomial time algorithm that determines whether a system of linear equations over the integers has a solution. The algorithm uses Hermite normal form, which can be computed in polynomial time. See lecture notes of Swastik Kopparty: Hermite normal form and finding integer solutions.

Your proof that your problem is in coNP is incomplete, since you haven't shown that the witness has polynomial size. Assuming you did manage to show it, all this implies is that the problem is in coNP, not that it is coNP-hard. There's absolutely no issue for a problem to be in both NP and coNP. Indeed, every problem in P is also in NP and coNP. If you can put a problem in both NP and coNP, then this suggests that it might actually be in P, though it is conjectured that $\mathsf{P} \subsetneq \mathsf{NP} \cap \mathsf{coNP}$. One problem which might lie in the middle is (a decision version of) integer factorization.


How to calculate the miss ratio of a cache I know how to calculate the CPI or cycles per instruction from the hit and miss ratios, but I do not know exactly how to calculate the miss ratio that would be 1 - hit ratio if I am not wrong. I know that the hit ratio is calculated dividing hits / accesses, but the problem says that given the number of hits and misses, calculate the miss ratio.

My reasoning is that having the number of hits and misses, we have actually the number of accesses = hits + misses, so the actual formula would be:

  hit_ratio = hits / (hits + misses)

So the miss ratio would be

  miss_ratio = 1 - hit_ratio

If my reasoning is correct, right?

What is the hit and miss latencies? Because I need them to calculate the mean access time using the hit and the miss ratios and the hit and the miss latencies (in cycles)...

Yes. The hit ratio is the fraction of accesses which are a hit. The miss ratio is the fraction of accesses which are a miss. It holds that
$$ \text{miss rate} = 1-\text{hit rate}.$$

The (hit/miss) latency (AKA access time) is the time it takes to fetch the data in case of a hit/miss.
If the access was a hit - this time is rather short because the data is already in the cache. But if it was a miss - that time is much linger as the (slow) L3 memory needs to be accessed.
The latency depends on the specification of your machine: the speed of the cache, the speed of the slow memory, etc.


Is this a correct description of Dijkstra's algorithm I am on a journey understanding Dijkstra's algorithm.

My familiarity with mathematical terms is not great, so I have put the algorithm into my own English. I understand this is not ideal, but this is part of my learning process.

What are the major areas of misunderstanding in the description below?

We maintain a list D of all the tentatively known shortest distances to nodes.

Each item in D comprises a node name, a shortest (yet known) distance and a "via" node, indicating the node the path arrives via.

ie. [{ node, tentativeDistance, via }, ...]

We start with a list G of all the nodes in the graph.

ie. [{ name, edges }, ...]

We use G to keep track of the nodes we have visited. Each time we visit a node we remove it from G. In this way we never visit a node more than once.

We pull a node N from G. At the start we pull the start node with cumulative distance of zero.

If this is the start node we add it to D.

We calculate the cumulative distance to it, given the node we have arrived via.  At the start we arrive via itself.

eg. if we arrived at node C via node B, we know that the shortest path to B is, say, 2 because we must have previously explored other options to arrive at B; if the cost of the edge from B to C is 1 the cumulative distance is 2 + 1 = 3.

We then review the unfollowed edges from every node that we have visited already (in D). This is akin to choosing which part of the advancing "wavefront" to advance from.

For each of the unfollowed edges if the cumulative distance to the destination node is shorter than any previously recorded distance for that node in D (or we do not yet have a distance for it) then we replace (or add) the entry for the node in D, together with the "via" value (the current node). In this way we build up a list of best-known distances to nodes.

We pick the new destination node with the shortest cumulative distance.

Again: in this way, we can be confident that when we arrive at a node, we have found the shortest path to it.

When we arrive at the destination node, or when we have visited all the nodes we stop, otherwise we repeat the edge-reviewing process described above.

Not bad. May I suggest a few improvements?

Distinguish between the algorithm (what you do) and the argument (the
proof of why it works).
Your D, which you say is a list, is better thought of as a
map/associative-array from Node to [distance, Node], where the former
Node is the predecessor of the latter.
Start the computation with {start-node -> [0, nil]} in D.
Define the graph G as a mapping Node -> Set of [distance, Node],
where the distance is the edge length from the former to the latter
node. This makes the iterative step easier to describe precisely.

The point of Dijkstra's algorithm is that the tentative distances turn out to be final. The way to prove this is to show that - given that it is true of D so far - it is true at the next step too. This is called the inductive hypothesis. Given that it is true of the initial D, which it is, it is true of all the Ds thereafter, including the final one.


unambiguous equivalent grammar There is a grammar G given:

    S->XaX
    X->aX|bX|eps

I just replied to the first question that was about showing that this grammar is ambiguous. The second question is to find an unambiguous equivalent grammar of this grammar given. I don't really know how to do it or from where to start. Can anyone help me?

Your language consists of all words over $\{a,b\}$ which contain $a$. This is a regular language, and so it has an unambiguous regular grammar - essentially a DFA - which is not so difficult to construct for this language. Regular grammars constructed from DFAs are unambiguous, so this would be an unambiguous grammar for the same language.


A basic question about recursive computation I was going through the following paper: http://www-formal.stanford.edu/jmc/recursive.pdf

In the last part of the second section (at the end of page 7) he speaks about the inadequacy of lambda notion for naming functions described recursively.

The right hand side of the following expression
$$\text{sqrt} = \lambda((a,x,\epsilon),(|x^2 -a|<\epsilon \to x,T \to\text{sqrt}(a,\frac{1}{2}(x+\frac{a}{x}),\epsilon)))$$ cannot serve as an expression of function because there would be nothing to indicate that the reference to $\text{sqrt}$ within the expression stood for the expression as a whole.
I did not get what it meant. Why should there be a further indication that the expression stood for whole? Please explain this point.

In pure untyped lambda calculus functions are anonymous. Generally, when you want to define a function recursively, you can simply have it "call" itself, for example:

if $n=0$ then $f(n) = 1$
if $n>0$ then $f(n) = nf(n-1)$.

In lambda calculus we don't have the same luxury, functions don't even have "names" in the first place, they are defined in terms of variable binding and variable substitution.
Still, there is a way to implement recursion, discovered by Haskell Curry, by using a particular lambda-term, called fixed-point combinator (if you are interested in details, any reasonable source on lambda calculus covers this aspect).
With the new notation, the authors are effectively introducing a mechanism to give names to functions, removing the problem entirely.


Are there pseudorandom number generators (PRNG) with no finite period? The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period?

For this question it is not necessary that it be practical or used in real-world implementations.

If the state of the PRNG is finite, then it has a finite period.  (By finite, I mean the same as we mean when we say that a finite-state automaton is finite: the set of all possible states is finite.  For instance, if the state always fits into $b$ bits, for some fixed value of $b$, then its state is finite.)

In practice, worrying about the period of the PRNG may be akin to arguing over angels on a pinhead.  A 256-bit state is large enough that a well-designed PRNG will never repeat within the lifetime of the universe.  Therefore, concerns about repetition are pretty much irrelevant for any reasonable, well-designed PRNG.

In practice, the real challenge is to make the PRNG unpredictable (or close enough for the application's purposes); ensuring it won't repeat is much easier, relatively speaking.


L-attributed definitions include all syntax-directed definitions based on LL(1) grammars I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following claim:

L-attributed definitions include all syntax-directed definitions based on LL(1) grammars.

What is the intuition or logic behind this statement?
In the later sections they show that L attributed grammars can be easily implemented by a DFS search algorithm of the parse tree (and hence easily by a predictive parser [recursive/non recursive]). $^\dagger$
Is it so that since LL(1) grammars can also be parsed by predictive parser and by the logic of $\dagger$, the authors make the claim?

L-attributed definitions are definition whose attributes can be evaluated in depth-first order (as they say in the first sentence).
The statement "L-attributed definitions include all syntax-directed definitions based on LL(1) grammars" is perhaps a bit subtle. It's not saying that the two sets of definitions are the same; rather, that syntax-directed definitions "based on LL(1) grammars" are a subset of L-attributed definitions.
That's true because the predictive parser based on the LL(1) grammar visits the parse tree in strictly depth-first order. This was already noted in Designing a Predictive Parser in Section 2.4 of the text book, which goes on to build a recursive-descent parser illustrating how this works.


Ford-Fulkerson pseudo-polynomial Can somebody explain please why Ford-Fulkerson Algorithm has pseudo-polynomial complexity? I understand that the complexity in this case strongly depends on the capacities of the edges of the network, since we have $O(|E|*f_{max})$, but why is the algorithm still not polynomial?

Lets recall that input for flow problems is a graph with capacities on their edges. Let $G(V,E)$ where $V$ denotes the vertex set of the graph and $E$ denotes the edge set. Let $f_{\text{max}}$ denote the maximum possible flow. It is an easy caluclation that input size is $\mathcal{O}(V+E \log (f_{\text{max}}))$ bits as  writing $f_{\text{max}}$ takes $\mathcal{O}(\log f_{\text{max}})$ bits. Since $f_{\text{max}}$ may be arbitrarily high (it depends neither on $V$ or $E$), this running time could be arbitrarily high, as a function of $V$ and $E$.

A algorithm is said to  have a polynomial runnning time if its runtime in input size in bits where as pseudo-polynomial runtime means runtime of the algorithm is polynomial in numeric value of the input (see Pseudo-polynomial time)


Automaton without variables and guards for queueing system Disclaimer: Assignment question.

I am trying to solve the below question, the condition is not to use guards and variables. Is it at all possible to do this?

My approach was to have 4 separate automatons, 1 for each of the three servers and 1 for the entire system(with states for 0, 1 and 2 customers in the system). But its not working for all the conditions.
Any help is appreciated.

One deterministic automaton is enough to model this system.

Here are the list of states and their meanings. The alphabet is $$\{\text{a_customer_comes},\text{a_customer_leaves_server_1},\\ \text{a_customer_leaves_server_2},\text{a_customer_leaves_server_3}\}.$$ (We assume the input events happen one at a time. Otherwise, the problem might be too ill-defined enough to have a unique answer or too complex to be done as an exercise.)

$q_{0,0,0}$ : the initial state. No customer present.
$q_{1,0,0}$ : 1 customer at server 1 and 0 customer at server 2 and 0 customer at server 3.
$q_{0,1,0}$ : 0 customer at server 1 and 1 customer at server 2 and 0 customer at server 3.
$q_{0,0,1}$ : 0 customer at server 1 and 0 customer at server 2 and 1 customer at server 3.
$q_{1,1,0}$ : 1 customer at server 1 and 1 customer at server 2 and 0 customer at server 3.
$q_{1,0,1}$ : 1 customer at server 1 and 0 customer at server 2 and 1 customer at server 3.
$q_{0,1,1}$ : 0 customer at server 1 and 1 customer at server 2 and 1 customer at server 3.

I will let you figure out the transitions.


Top N percent elements in a queue I implemented a queue using two stacks which gives me $O(1)$ en-queue time, $O(1)$ amortised time. Now suppose I want to find top $10\%$ elements in the queue at any time. How am I suppose to implement it.

For example: queue takes the element in this order
$$ \{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 \}.$$

Top $10\%$ elements means $10 \% $ of $20 = 2$.

Hence the answer will be $19$ and $20$.

The best way I can think of is to sort it and then calculate $N%$ of size of queue and return that many elements. This takes about $O (n \log n + k)$ time.

Is this the most efficient way? I came across this algorithm. It's a linear solution. It seems like an answer, however I would like to know your views.

You can implement this in O(klogk + n) time complexity.

Maintain an external min-heap while iterating the queue. The min-heap shall have at most k elements at a time.

Insert the first k elements in the min-heap. Thereafter compare the present queue element with the top of the heap. If the top is less than present value then delete the top element from the heap and insert this new present element.

At the end the heap shall contain top k elements in the queue.


How to prove that the subset sum problem is polynomially reducible to the knapsack problem I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete.
There are two parts to showing knapsack is NP-complete

knapsack is in NP
If I show that the subset sum problem is polynomially reducible to the knapsack.
Then since subset sum problem is known to be NP-hard. Knapsack is NP-Hard

Both 1) and 2) imply that Knapsack is NP-Complete

Is trivial as given any sequence of items we can verify the sum of their value
and weights in linear time. So the knapsack is in NP. Correct me If I am wrong here.

How do I approach 2)? I am not sure how to phrase the polynomial conversion
from the subset sum problem to the knapsack.

The subset-sum problem is a pair $(S,k)$ and a question whether there exists $S' \subset S$ such that $\sum_{s \in S'} s = k$.
The knapsack problem is a tuple $(w,v,W, V)$ that is weights, values, the knapsack capacity and the target value, and a question can you pick such a set of items $\mathcal{I}$ such that:

$\sum_{i \in \mathcal{I}} w_i \leq W$
$\sum_{i \in \mathcal{I}} v_i \geq V$

Hint: Given an instance $(S,k)$ of subset-sum, is there a way to set the weights and values of our items in the knapsack, so that these inequalities turn into a single equality related somehow to $k$?


A better upper bound to a recursive function it's my first answer here.

I do have an algorithm to calculate the factorial of a given number $n$ recursively, but without using any multiplication like the usual one, only sums are available.

I've ended up with an algorithm with a complexity function $T(n) = 1 + nT(n - 1)$.

Opening the recurrence relation ends up in:

$T(n) = 1 + n T(n - 1)$

$T(n) = 1 + n[1 + (n - 1)T(n - 2)]$

$T(n) = 1 + n + n^2 T(n - 2) - n T(n - 2)$

$T(n) = 1 + n + n^2[1 + (n - 2) * T(n - 3)] - n T(n - 2)$

$T(n) = 1 + n + n^2 + n^3T(n - 3) - n T(n - 2) - n^2T(n - 3)$

Because of the subtractions, I'm not able to reach good upper-bound for $T(n)$. Any tips ?

Before asking the question, I've managed to state that $T(n) \in \mathcal{O}(n^n)$. Which is 'loose' upper bound, but I'm neither able to figure out a tighter upper bound.

Solving your recurrence, assuming the base case $T(0) = 1$, we get
$$
\begin{align*}
T(n) &= 1 + nT(n-1) \\ &=
1 + n + n(n-1)T(n-2) \\ &=
1 + n + n(n-1) + n(n-1)(n-2)T(n-3) \\ &= \cdots \\ &=
1 + n + n(n-1) + \cdots + n(n-1)\cdots2 + n! \\ &=
n! \left(\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots + \frac{1}{n!}\right) \\ &=
n! \left(e - O\left(\frac{1}{(n+1)!}\right)\right) \\ &= e \cdot n! - O\left(\frac{1}{n}\right).
\end{align*}
$$
In particular, $T(n) = \Theta(n!) = \Theta(\sqrt{n}(n/e)^n)$.


Define a list using only the Hindley-Milner type system I'm working on a small lambda calculus compiler that has a working Hindley-Milner type inference system and now also supports recursive let's (not in the linked code), which I understand should be enough to make it Turing complete.

The problem now is I have no idea how to make it support lists, or whether it already does support them and I just need to find a way to encode them. I'd like to be able to define them without having to add new rules to the type system.

The easiest way I can think of a list of x is as something that is either null (or the empty list), or a pair that contains both an x and a list of x. But to do this I need to be able to define pairs and or's, which I believe are the product and the sum types.

Seems that I can define pairs this way:

pair = λabf.fab
first = λp.p(λab.a)
second = λp.p(λab.b)

Since pair would have the type a -> (b -> ((a -> (b -> x)) -> x)), after passing, say, an int and a string, it'd yield something with type (int -> (string -> x)) -> x, which would be the representation of a pair of int and string. What bothers me here is that if that represents a pair, why is that not logically equivalent to, nor implies the proposition int and string?. However, is equivalent to (((int and string) -> x) -> x), as if I could only have product types as parameters to functions. This answer seem to address this problem, but I have no idea what the symbols he uses mean. Also, if this does not really encode a product type, is there anything I can do with product types I couldn't do with my definition of pairs above (considering I can also define n-tuples the same way)? If not, wouldn't this contradict the fact that you cannot express (AFAIK) conjunction using only implication?

Also, how about the sum type? Can I somehow encode it using only the function type? If so, would this be enough to define lists? Or else, is there any other way to define lists without having to extend my type system? And if not, what changes would I need to make if I want to keep it as simple as possible?

Please keep in mind that I'm a computer programmer but not a computer scientist nor a mathematician and pretty bad at reading math notation.

Edit:  I'm not sure what's the technical name of what I have implemented so far, but all I have is basically the code I've linked above, which is a constraint generation algorithm that uses the rules for applications, abstractions and variables taken from the Hinley-Milner algorithm and then a unification algorithm that gets the principal type. For instance, the expression \a.a will yield the type a -> a, and the expression \a.(a a) will throw an occurs check error. On top of this, there is not exactly a let rule but a function that seems to have the same effect that lets you define recursive global functions like this pseudo-code:

GetTypeOfGlobalFunction(term, globalScope, nameOfFunction)
{
    // Here 'globalScope' contains a list of name-value pair where every value is of class 'ClosedType',
    // meaning their type will be cloned before unified in the unification algorithm so that they can be used polymorphically
    tempType = new TypeVariable() // Assign a dummy type to `tempType`, say, type 'x'.
    // The next line creates an scope with everything in 'globalScope' plus the 'nameOfFunction = tempType' name-value pair
    tempScope = new Scope(globalScope, nameOfFunction, tempType)
    type = TypeOfTerm(term, tempScope) // Calculate the type of the term
    Unify(tempType, type)
    return type
    // After returning, the code outside will create a 'ClosedType' using the returned type and add it to the global scope.
}

The code basically gets the type of the term as usual, but before unifying, it adds the name of the function being defined with a dummy type into the type scope so that it can be used from within itself recursively.

Edit 2: I just realized that I'd also need recursive types, which I don't have, to define a list like I want.

Pairs

This encoding is the Church encoding of pairs. Similar techniques can encode booleans, integers, lists, and other data structures.

Under the context x:a; y:b, the term pair x y has the type (a -> b -> t) -> t. The logical interpretation of this type is the following formula (I use standard mathematical notations: $\to$ is implication, $\vee$ is or, $\wedge$ is and, $\neg$ is negation; $\iff$ is equivalence of formulas):
$$ \begin{align}
  (a \to b \to t) \to t
  & \quad\iff\quad \neg (\neg a \vee \neg b \vee t) \vee t \\
  & \quad\iff\quad (a \wedge b \wedge \neg t) \vee t \\
  & \quad\iff\quad (a \wedge b) \vee t \\
\end{align}
$$
Why “a and b or t”? Intuitively, because pair is a function that takes a function as an argument and applies it to the pair. There are two ways this can go: the argument function can make use of the pair, or it can produce a value of type t without using the pair at all.

pair is a constructor for the pair type and first and second are destructors. (These are the same words used in object-oriented programming; here the words have a meaning that is related to the logical interpretation of the types and terms that I won't go into here.) Intuitively, the destructors let you access what is in the object and the constructors pave the way for the destructor by taking as an argument a function that they apply to the parts of the object. This principle can be applied to other types.

Sums

The Church encoding of a discriminated union is essentially dual to the Church encoding of a pair. Where a pair has two parts that must be put together and you can choose to extract one or the other, you can choose to build the union in either of two ways and when you use it you need to allow for both ways. Thus there are two constructors, and there is a single destructor which takes two arguments.

let case w = λf. λg. w f g           case : ((a->t) -> (b->t) -> t) -> (a->t) -> (b->t) -> t
  (* or simply let case w = w *)
let left x = λf. λg. f x             left : a -> ((a->t) -> (b->t) -> t)
let right y = λf. λg. g x            right : b -> ((a->t) -> (b->t) -> t)

Let me abbreviate the type (a->t) -> (b->t) -> t as SUM(a,b)(t). Then the types of the destructors and constructors are:

case : SUM(a,b)(t) -> (a->t) -> (b->t) -> t
left : a -> SUM(a,b)(t)
right : b -> SUM(a,b)(t)

Thus

case (left x) f g → f x
case (rightt y) f g → g y

Lists

For a list, apply again the same principle. A list whose elements have the type a can be built in two ways: it can be an empty list, or it can be an element (the head) plus a list (the tail). Compared with pairs, there's a little twist when it comes to the destructors: you can't have two separate destructors head and tail because they would only work on non-empty lists. You need a single destructor, with two arguments, one of which is a 0-argument function (i.e. a value) for the nil case, and the other a 2-argument function for the cons case. Functions like is_empty, head and tail can be derived from that. Like in the case of sums, the list is directly its own destructor function.

let nil = λn. λc. n
let cons h t = λn. λc. c h t
let is_empty l = l true (λh. λt. false)
let head l default = l default (λh. λt. h)
let tail l default = l default (λh. λt. t)

Each of these functions is polymorphic. If you work the types of these functions, you'll note than cons is not uniform: the type of the result is not the same as the type of the argument. The type of the result is a variable — it is more general than the argument. If you chain cons calls, the successive calls to build a list instantiate cons at different types. This is crucial to make lists work in the absence of recursive types. You can make heterogeneous lists that way. In fact, the types that you can express are not “list of $T$”, but “list whose first elements are of types $T_1,\ldots,T_n$”.

As you surmise, if you want to define a type that only contains homogeneous lists, you need recursive types. Why? Let's look at the type of a list. A list is encoded as a function which takes two arguments: the value to return on empty lists, and the function to compute the value to return on a cons cell. Let a be the element type, b be the type of the list, and c be the type returned by the destructor. The type of a list is

a -> (a -> b -> c) -> c

Making the list homogeneous is saying that if it's a cons cell, the tail has to have the same type as the whole, i.e. it adds the constraint

a -> (a -> b -> c) -> c = b

The Hindley-Milner type system can be extended with such recursive types, and in fact practical programming languages do that. Practical programming languages tend to disallow such “naked” equations and require a data constructor, but this is not an intrinsic requirement of the underlying theory. Requiring a data constructor simplifies type inference, and in practice tends to avoids accepting functions that are actually buggy but happen to be typable with some unintended constraint that causes a difficult-to-understand type error where the function is used. This is why, for example, OCaml accepts unguarded recursive types only with the non-default -rectypes compiler option. Here are the definitions above in OCaml syntax, together with a type definition for homogeneous lists using the notation for aliased recursive types: type_expression as 'a means that the type type_expression is unified with the variable 'a.

# let nil = fun n c -> n;;
val nil : 'a -> 'b -> 'a = <fun>
# let cons h t = fun n c -> c h t;;
val cons : 'a -> 'b -> 'c -> ('a -> 'b -> 'd) -> 'd = <fun>
# let is_empty l = l true (fun h t -> false);;
val is_empty : (bool -> ('a -> 'b -> bool) -> 'c) -> 'c = <fun>
# let head l default = l default (fun h t -> h);;
val head : ('a -> ('b -> 'c -> 'b) -> 'd) -> 'a -> 'd = <fun>
# let tail l default = l default (fun h t -> t);;
val tail : ('a -> ('b -> 'c -> 'c) -> 'd) -> 'a -> 'd = <fun>
# type ('a, 'b, 'c) ulist = 'c -> ('a -> 'b -> 'c) -> 'c;;
type ('a, 'b, 'c) ulist = 'c -> ('a -> 'b -> 'c) -> 'c
# is_empty (cons 1 nil);;
- : bool = false
# head (cons 1 nil) 0;;
- : int = 1
# head (tail (cons 1 (cons 2.0 nil)) nil) 0.;;
- : float = 2.

(* -rectypes is required for what follows *)
# type ('a, 'b, 'c) rlist = 'c -> ('a -> 'b -> 'c) -> 'c as 'b;;
type ('a, 'b, 'c) rlist = 'b constraint 'b = 'c -> ('a -> 'b -> 'c) -> 'c
# let rcons = (cons : 'a -> ('a, 'b, 'c) rlist -> ('a, 'b, 'c) rlist);;
val rcons :
  'a ->
  ('a, 'c -> ('a -> 'b -> 'c) -> 'c as 'b, 'c) rlist -> ('a, 'b, 'c) rlist =
  <fun>
# head (rcons 1 (rcons 2 nil)) 0;;
- : int = 1
# tail (rcons 1 (rcons 2 nil)) nil;;
- : 'a -> (int -> 'a -> 'a) -> 'a as 'a = <fun>
# rcons 1 (rcons 2.0 nil);;
Error: This expression has type
         (float, 'b -> (float -> 'a -> 'b) -> 'b as 'a, 'b) rlist = 'a
       but an expression was expected of type
         (int, 'b -> (int -> 'c -> 'b) -> 'b as 'c, 'b) rlist = 'c

Folds

Looking at this a bit more generally, what is the function that represents the data structure?

For a natural number: $n$ is represented as the function which iterates its argument $n$ times.
For a pair: $(x,y)$ is represented as a function which applies its argument to $x$ and $y$.
For a sum: $\mathrm{in}_i(x)$ is represented as a function which applies its $i$th argument to $x$.
For a list: $[x_1,\ldots,x_n]$ is represented as a function that takes two arguments, the value to return for the empty list and the function to apply to cons cells.

In general terms, the data structure is represented as its fold function. This is a general concept for data structures: a fold function is a higher-order function that traverses the data structure. There is a technical sense in which fold is universal: all “generic” data structure traversals can be expressed in terms of fold. That the data structure can be represented as its fold function shows this: all you need to know about a data structure is how to traverse it, the rest is an implementation detail.


Master theorem: $T(n)=10T(n/9)+n\lg(n)$ I am told to solve the recurrence
$$T(n)=10T(n/9)+n\lg(n)$$
using the Master theorem. I then try to use case 3. However, I am unable to show that for $f(n)=n\lg(n)$ then $10f(n/9) \leq cn\lg(n)$ for $c < 1$ and all sufficiently large $n$. Is it wrong to use case 3? Or does the Master theorem even apply?

Case 3 does not apply. Indeed:
$$
f(n) = n \log n \not\in \Omega(n^{\log_9 10}) = \Omega(n^{\log_b a}).
$$
However case $1$ applies since, for $0<c \le 0.01$
$$
f(n) = n \log n \in O(n^{1.04 - 0.01}) \subset O(n^{\log_9 10 - 0.01} ) \subseteq O(n^{\log_b a - c} ).
$$
This shows that $T(n) \in \Theta(n^{\log_9 10})$.


Partitioning bag of sets such that each set in a group has a unique element Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one element not found in any other set in that group. Formally, the criterion for a group $G = \{g_1, g_2, \dots \} \subseteq S$ is:

$$\forall i: \left(g_i \setminus \bigcup_{j\neq i} g_j\;\neq\;\emptyset\right) $$

The partition $P = \{\{s_1\}, \{s_2\}, \dots\}$ always satisfies this requirement, so there is always a valid solution. But what is the smallest number of groups needed? Is this problem feasible or NP-complete?

Another formulation of this problem is to partition a multiset of integers into groups such that each integer has a bit set in its binary expansion that no other integer in its group has set.

It is NP-hard. Here is a reduction from a variant of vertex cover:

Given a graph $G$ with $n$ vertices and a positive integer $k$ where $n+k$ is even, determine whether there is a vertex cover with size $k$.

This variant is also NP-complete.
Given an instance graph $G$ with $n$ vertices $v_1,\ldots,v_n$ and $m$ edges $e_1,\ldots,e_m$, as well as an integer $k$, we construct $nm+1$ elements $x_{11},\ldots,x_{1m},\ldots,x_{nm},y$. We define $U=\{x_{11},\ldots,x_{1m},\ldots,x_{nm},y\}$ for convenience. Also,

For each vertex $v_i$, we construct a vertex set $S_i=U\backslash\{x_{i1},\ldots,x_{im}\}$.
For each edge $e_j=(v_{i_1},v_{i_2})$, we construct an edge set $T_j=(U\backslash\{x_{i_11},\ldots,x_{i_1m},x_{i_21},\ldots,x_{i_2m},y\})\cup\{x_{i_1j},x_{i_2j}\}$.

We ask if $\{S_1,\ldots,S_n,T_1,\ldots,T_m\}$ can be partitioned into $(n+k)/2$ groups such that within each group each set has at least one element not found in any other set in that group.
If there is a vertex cover with size $k$, say without loss of genrality $\{v_1,v_2,\ldots,v_k\}$, then the partition can be $\{S_1,T_{c(1,1)}, T_{c(1,2)},\ldots\}, \ldots, \{S_k,T_{c(k,1)}, T_{c(k,2)},\ldots\}, \{S_{k+1},S_{k+2}\},\ldots,\{S_{n-1},S_n\}$ where $v_i$ covers $e_{c(i,1)}, e_{c(i,2)}, \ldots$ (if $v_i$ and $v_{i'}$ both cover an edge $e_j$, we arbitrarily allocate $T_j$ to one of the groups containing $v_i$ and $v_{i'}$.)
On the other hand, if there is a $(n+k)/2$-partition, we can always adjust it to the form above without increasing the number of groups, thus obtain a vertex cover with size at most $k$. First, we observe that

If a group contains at least two vertex sets, then it cannot contain any other set. We call such group a vertex group.
If a group contains exactly one vertex set $S_i$, we call it a mix group. Moreover, if this group contains at least two edge sets, then the edges corresponding to the edge sets in this group must all be incident to the vertex $v_i$. (If a group contains exactly one vertex set $S_i$ and one edge set $T_j$, and the edge $e_j$ is not incident to the vertex $v_i$, we call such group a bad group.)
If a group contains no vertex set, then there exist at most two vertices such that each edge corresponding to an edge set in this group must be incident to one of the two vertices. We call such group an edge group.

The adjustment is roughly described as follows:

We arbitrarily choose two bad groups $\{S_i,T_j\},\{S_{i'},T_{j'}\}$ and regroup them as $\{S_i,S_{i'}\},\{T_j,T_{j'}\}$. We repeat this process until there are at most one bad group.

If there is still a bad group $\{S_i,T_j\}$, suppose $e_j$ is incident to $v_{i'}$, then consider the group containing $S_{i'}$. There are two cases:

This group is a vertex group, say $\{S_{i'}, S_{i''}\}$. Then we regroup these sets to $\{S_{i'},T_j\}$, $\{S_i,S_{i''}\}$.
This group is a mix group. Then we simply move $T_j$ to this group.

After the adjustment above, there is no bad group any more.

For each group containing no vertex set, due to Observation 3, there are two vertices $v_i,v_{i'}$ such that each edge corresponding to an edge set in this group is incident to at least one of $v_i,v_{i'}$. For convenience, we denote respectively by $\mathcal{T}_i$ and $\mathcal{T}_{i'}$ the edge sets with corresponding edges incident to $v_i$ and $v_i'$ (one edge $e_j$ may be incident to both $v_i$ and $v_i'$, we arbitrarily allocate $T_j$ to one of $\mathcal{T}_i$ and $\mathcal{T}_{i'}$). Consider the group(s) containing $S_i$ and $S_{i'}$. There are four cases.

$S_i$ and $S_{i'}$ belong to the same group, then we regroup these sets to $\{S_i,\mathcal{T}_i\},\{S_{i'},\mathcal{T}_{i'}\}$.
The two groups are both vertex groups, say $\{S_i,S_{i''}\},\{S_{i'},S_{i'''}\}$. We regroup these sets to $\{S_i,\mathcal{T}_i\},\{S_{i'},\mathcal{T}_{i'}\},\{S_{i''},S_{i'''}\}$.
The two groups are both mix groups, we then simply move $\mathcal{T}_i$ to the group containing $S_i$, and $\mathcal{T}_{i'}$ to the group containing $S_{i'}$.
One is a mix group (say the group containing $S_i$) and the other is a vertex group (say $\{S_{i'},S_{i''}\}$). We then move $\mathcal{T}_i$ to the group containing $S_i$ and regroup remaining sets to $\{S_{i'},\mathcal{T}_{i'}\},\{S_{i''}\}$.

After these adjustments, there are only vertex groups and "good" mix groups. The vertices corresponding to the vertex sets in these "good" mix groups form a vertex cover.
As a result, the decision version of your problem is NP-complete.


Problem about getting a value of the hashed password Given a database with usernames and the first six bytes of their hashed passwords. A standard hashing function has been used for hashing.

admin 827ccb0eea8a

user c3981fa8d26e

operator 5f4dcc3b5aa7

guest 084e0343a048

The password of admin is 12345.
What value of the hashed password will be added to the database after the creation of the username operator with the password qwerty123?

How can I solve this problem? Any tips?

The problem asks to be creative about breaking hash attempt, well it is a big stretch even for simplistic example, but let's try.

You are given a password 12345 from user admin with 827ccb0eea8a hash, that is first 6-bytes of the hash.
A standard hashing function has been used - it means MD5. Why?

The construction of the task asks for preimage attack, it must be homemade breakable and possibly already hashed and shown online, otherwise it would not be possible to crack without substantial resources.
It cannot be salted, because the salt was not given in the task, but using salt is a wise thing to do - it prevents the rainbow tables attacks and in the case like here, you have a collection of hashes would be harder to recover in batches.
The MD5 is built-in into PHP and easily accessible in the most programming languages (MD5 implementations)

Try them until the match is found and then take the steps to hash your password.

Make the test of standard functions (like MD5, SHA256) of any combination of admin and 12345, it may be concatenated or xored, in fact it is not. First try out of lazy guess,
MD5(12345) =$\color{maroon}{\text{827ccb0eea8a}}\color{gray}{\text{706c4c34a16891f84e7b}}$
It tells that no salt or username was used, just plain password hashed with deprecated function. The other hashes are irrelevant at this point, but seeing the pattern, find simple MD5 of potential passwords until the first 6 bytes are like in the list.

After the scheme is known, the task is to produce the output from qwerty123, so MD5(qwerty123) =$\color{maroon}{\text{3fc0a7acf087}}\color{gray}{\text{f549ac2b266baf94b8b1}}$


Fast checking Matrix multiplication in mod 10 I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In other words, return the result of expression (A x B) mod 10 == C.

For example:

$\qquad A = \begin{bmatrix}
 0 & 5 & 8 \\
 1 & 4 & 9 \\
 2 & 3 & 3
\end{bmatrix}\qquad
B = \begin{bmatrix}
 3 & 5 & 0 \\
 1 & 2 & 6 \\
 3 & 7 & 0
\end{bmatrix}\qquad
C = \begin{bmatrix}
 9 & 6 & 0 \\
 4 & 6 & 4 \\
 8 & 7 & 8
\end{bmatrix}$

return: TRUE

If

$\qquad C = \begin{bmatrix}
 1 & 6 & 0 \\
 4 & 6 & 4 \\
 8 & 7 & 8
\end{bmatrix}$

return: FALSE, since the element C(1, 1) must be 9.

Time limit is 1s, pretty strict. Please gives me some idea how to solve the problem efficiently; is it possible time $O(N^2)$?

I got Accepted by using Freivald's algorithm as suggested by @David Richerby. Thank you very much !

I have not tested the brute-force solution using Coppersmith-Winograd algorithm yet. Will report in a couple of days, by the way I think it might not get Accepted but possibly will gain a fairly amount of points.

For those who want to check your implementation, submit your code on http://vn.spoj.com/problems/VMATRIX/. The problem statement is in Vietnamese, so here is the short description of input format:

  First line is number of testcase (the example gives 2 testcases)
  For each testcase:
  the first line is size of 3 matrices, N. In 20% testcase N <= 100.
  next N * N lines: matrix A
  next N * N lines: matrix B
  next N * N lines: matrix C

Output: YES or NO for the result.


3-dimensional matching approximation algorithm (implementation details) I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below:
How can I construct the maximum matching M_r in S_r in linear time in line 8?

$X, Y, Z $ are disjoint sets; a matching $M$ is a subset of $S$ s.t. no two triples in $M$ have the same coordinate at any dimension.

$
\text{Algorithm: unweighted 3-dimensional matching (2-approximation)} \\
\text{Input: a set $S\subseteq X \times Y \times Z$ of triples} \\
\text{Output: a matching M in S}
$

 1) construct maximal matching M in S;
 2) change = TRUE;
 3) while (change) {
 4)   change = FALSE;
 5)   for each triple (a,b,c) in M {
 6)     M = M - {(a,b,c)};
 7)     let S_r be the set of triples in S not contradicting M;
 8)     construct a maximum matching M_r in S_r;
 9)     if (M_r contains more than one triple) {
10)       M = M \cup M_r;
11)       change = TRUE;
12)     } else {
13)       M = M \union {(a,b,c)};
14)     }
15) }

[1] http://faculty.cse.tamu.edu/chen/courses/cpsc669/2011/notes/ch9.pdf, p. 326

We don't need the maximum matching, just one of cardinality $2$ if it exists.

Scan $S_r$ looking for a triple $T$ such that $\lvert T \cap \{a, b, c\}\rvert = 1$. If no such $T$ exists, then the maximum cardinality of a matching is clearly $1$. Otherwise, assume without loss of generality that $T = \{a, x, y\}$.

Scan $S_r$ again looking for a triple $U$ such that $T \cap U = \varnothing$. If no such $U$ exists, then every triple intersects both $\{a, b, c\}$ and $T$. For every $U \in S_r$, we have $\{a\} \subseteq U$ or $\{b, x\} \subseteq U$ or $\{b, y\} \subseteq U$ or $\{c, x\} \subseteq U$ or $\{c, y\} \subseteq U$.

There are several possibilities for a cardinality-$2$ matching $\{T_1, T_2\}$. There's an easy test for those of type $\{b, x\} \subseteq T_1$ and $\{c, y\} \subseteq T_2$. Similarly, $\{b, y\}$ and $\{c, x\}$. The only other types are the four like $\{a\} \subseteq T_1$ and $\{b, x\} \subseteq T_2$. To test for those, gather all triples of the form $\{b, x, z\} \in S_r$ and discard the ones in excess of three. Try each of the remainder against all possibilities containing $a$. The three $\{b, x, z\}$ candidates suffice because no triple containing neither $b$ nor $x$ intersects all three.


Algorithms computing if a number is a multiple of 3 When doing mental calculus one can do:

Given an integer k, sum all the digits (in base 10),
and if the result is a multiple of 3, then k is a multiple of 3.

Do you know of any algorithm working similarily but operating on binary numbers digits (bits)?

At first, I was thinking of using the ready made functions of my
language converting integer to ascii to perform the convertion from
base 2 to base 10, then apply the mental calculus trick. But of
course then I could also encode the base convertion 2 to 10 myself.
I have not done it yet, but I'll give it a try.
Then I have thought of euclidian division in base 2...

However I wonder if there are other means, algorithms.

What about a finite state automaton for the job?

Of course the magic is just computation modulo 3. Adding symbol $a$ behind string $x$ means the "binary value" of the string goes from $val(x)$ for $x$ to $2\cdot val(x)+a$ for $xa$. Consequently from state $p$ and symbol $a$ we move to state $2p+a \bmod 3$, for $p\in \{0,1,2\}$ and $a\in \{0,1\}$. Note $x\in \{0,1\}^*$ is a string, wheras $val(x)\in \Bbb{N}$ is its value as binary string.


Randomized String Searching I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m < n$.

I want to state an algorithm that runs in time $O(n)$ where we assume that arithmetic operations on $O(\log_2 n)$ bit numbers can be executed in constant time. The algorithm should accept with probability $1$ whenever $P$ is a substring of $T$ and reject with probability of at least $1 - \frac{1}{n}$ otherwise.

I think fingerprinting could help here. But I can't get it.

The Knuth-Morris-Pratt algorithm does this in linear time without any error.


Optimal meeting point I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point and to minimize the time/distance for everyone.

I'm looking for information on that problem, but I've only been able to find advanced paper on this problem.

My questions:

Is it part of a more general problem?
Is graphs the best way to implement it? (the nodes are the possible meeting points, the edges are the possible roads for example..) How do current programs work, for example using maps like Google Map?
Is it P or NP?

My difficulties to understand the problem and to find more informations about it

I know it's a bit vague, but I've got some difficulties because I don't know much about this kind of problems. I was just wondering one day "how to find the best restaurant in terms of distance to meet with some friends". I don't know what is mathematically the parameter that I should minimize to be "fair" (the sum of the distances of the $n$ individuals to the meeting point? The average?...).

Response to comment: (assuming that using graph is the best way to do it)

In input, we have a graph and we have the $n$ individuals (a list of $n$ vertices if we implement it with graphs, even if it means to add them to the graph), and in output, we get the optimal meeting point (i.e. the vertex which is at the minimal distance from all the $n$ individuals).

There are two kinds of minimizing in this sense,

the first is to minimize the sum of the distances.
the second is to minimize the maximum distance (finding a restaurant where the farthest friend is as near as possible).

In both cases it's not NP-Hard, since you can calculate all-pairs shortest path in $O\left(N^2\log\left( E+N \right)\right)$, sum up the distances from each restaurants to all friends and compare the sums.

Ps A special case is points laying on a line segment. The solution to the first type will be the restaurant dividing the vertices in two most-possible equal groups (has so many friends on its left as many friends on its right), the reason this works can be derived from the fact that median minimize absolute deviation.
The solution to the second problem is trivially the nearest restaurant to the middle point between the two farthest friends.

Ps2 In trees you can solve the second type using two DFSes to find the two farthest points and then choose the point in between them minimizing the distance to both of them.
The second type however, can be done in trees using a bfs traversal from leaves, counting the number of friends and distance to them in subtree of each node. Then a second bfs from the root of the tree summing all the numbers up.


Gauss-Newton algorithm implementation I am trying to implement a Gauss-Newton algorithm for non-linear optimisation. Unfortunately despite searching through the library and the internet I can't figure out quite how to use it in my case. As such I am hoping that I have come to the right place to ask for some assistance? Thank you to anyone willing to help me.

My problem consists of minimising a function $f(\vec x)$ where $\mathbb R^n \ni \vec x = (x_1, \dots ,x_n)$ and $f:\mathbb R^n\rightarrow \mathbb R$. Physically $f$ is a chi squared value $f=y-e(\vec x)$ where $y$ is the target value and $e(\vec x)$ is the test function evaluated at guess $\vec x$.

I begin by computing $f(\vec x+\delta \vec x)$ and  $f(\vec x)$. Here $\vec x+\delta \vec x=x_1+\delta x_1,\dots , x_n+\delta x_n$.  I then evaluate numerical derivatives using the following quotient formula,
\begin{equation}
\frac{\partial f(\vec x)}{\partial x_i} = \frac{f(x_1,\dots , x_i+\delta x_i,\dots ,x_n)-f(\vec x)}{\delta x_i}\qquad \forall i =1,\dots ,n
\end{equation}
I must then combine this into the Jacobian $\vec J$,
\begin{equation}
\vec J = \bigg(\frac{\partial f(\vec x)}{\partial x_1}\ \frac{\partial f(\vec x)}{\partial x_2} \cdots \frac{\partial f(\vec x)}{\partial x_n}\bigg)
\end{equation}
I can take the transpose of $\vec J$ denoted $\vec J^T$.

So far I can code the above (in C++). However The next part becomes confusing for me personally. In particular I do not know how to write the following matrix equation.
\begin{equation}
(\vec J \vec J^T)\delta \vec x = \vec Jf
\end{equation}
In fact I am not certain that this is the correct procedure?

Therefore, with numerical derivatives in place how can I obtain $\delta \vec x$ for the next iteration of the descent? Again many thanks for your time.

Solve the equation multiplying both terms of the equation for the inverse of the hessian matrix $\vec{J} \vec{J}^T$ on the left side:

$$
 \delta \vec{x} = (\vec{J} \vec{J}^T)^{-1} \cdot \vec{J}f
$$


Offline scheduling fully determined arbitrary jobs in multiprocessor setting Let $\mathcal{J} = \{J_1,...,J_n\}$ be a set of jobs with each $J_i = [a_i,r_i,d_i]$ where the job becomes available at its arrival time $a_i$, requires $r_i$ execution time and needs to be finished at its deadline $d_i$ (hard real time). Assume we have $m$ processors available.

Given the above, what scheduling algorithms are available to deal with this? I'm aware of a publication by Horn that gives a solution using flows; since that was in 1974 and flows are comparatively slow, I tried to find faster algorithms for this setting, but couldn't find any. The book on scheduling by Pinedo suggested in this answer on CS.SE mentions the setting and that it can be solved using flows, but unfortunately nothing else. Apart from these two sources, I have been unsuccessful.

Are there known algorithms to solve the above problem that are faster than flow networks on $\Theta(n)$ nodes?

I think it is going to be tough to find a more efficient algorithm than the one you already have.  You are getting close to requiring an online algorithm.

I think a lot is known about the online version of this problem.  Take a look at:

  Dertouzos and Mok: Multiprocessor On-Line Scheduing of Hard-Real-Time Tasks, IEEE T. Software Eng., 15(12):1497-1506, 1979.

It is known that least laxity first (also known as least slack first) scheduling is an optimal on-line greedy scheduling algorithm for the multiprocessor case only when all the $a_i$ are the same (basically: all the tasks arrive at the same time, but they have different execution times and deadlines.)  Dertouzos and Mok show there is no online algorithm for the case that the $a_i$ are not known a-priori.

What I don't know is whether there is some least-slack-first algorithm similar to list scheduling.  There must be a reference about this, but I haven't found it in the small amount I've looked just now.  Slack is a dynamic quantity.  At any time $t$ for any job $i$ it is the difference between $d_i -t$ and however much work is remaining to be done on job $i$.  The slack of a job starts at the value $(d_i - a_i) - r_i$ and must be monotonically non-increasing.  On imagines that one could take all the jobs, sort them by their initial slack value, and then greedily schedule them in that order, and that (for the case where the processors are identical, there are no precedence constraints, the jobs are all single-threaded, and arbitrary preemption and job migration are permitted and have no cost) you might be able to prove something concrete about it.


Convert non-integer decimal to octal I follow a course in Computer Architecture and I'm making exercises on number conversions. Now one of the questions asks me to convert 251.5625 to octal and hexdecimal base. No further info is given. Would this mean that I have to convert it and just ignore the point? Or what's the convention on something like this?

Every non-negative real number can be represented in any integer base $b \geq 2$ as a string of the form
$$
x_{n-1} \ldots x_0.x_{-1} x_{-2} \ldots,
$$
where $x_i \in \{0,\ldots,b-1\}$, and the string is interpreted as having the value
$$
x_{n-1} b^{n-1} + \cdots + x_0 b^0 + x_{-1} b^{-1} + x_{-2} b^{-2} + \cdots.
$$
For example, 251.5625 in base 10 is the number
$$
2 \times 10^2 + 5 \times 10^1 + 1 \times 10^0 + 5 \times 10^{-1} + 6 \times 10^{-2} + 2 \times 10^{-3} + 5 \times 10^{-4}.
$$
(You can extend this to negative numbers as well by allowing negation, e.g. -3.)

It is a basic result of arithmetic that every non-negative real number has a base $b$ expansion. In general, every number has infinitely many expansion: for example, 251.5625 can also be written as 0251.5625 or as 251.56250. If we don't allow leading and trailing zeroes then some numbers have a unique expansion, for example 0.33333…, and some numbers have two expansions, for example 251.5625 = 251.562499999….

A number is of the second form (has two expansions) if and only if it has a terminating expansion, that is one which is finite (for example 251.5625). The only number in base $b$ with this property are those of the form $N/b^k$ for integers $N,k \geq 0$. For example, 251.5625 = 2515625/104.

In your case, notice that 251.5625 = 4025/24. This shows that your number has a terminating expansion in any even basis, and in particular in base 8 (octal) and base 16 (hexadecimal). There are known algorithms to convert between bases, that you can find off the internet.

If you already know how to convert integers among bases, then you really also know how to convert non-integers, as long as they have a terminating expansion in the target base. To illustrate the method, consider the number 2.25. We want to convert it to base 4. Note that 2.25=9/4. Now 9 in base 4 is 214 (the subscript is how we indicate the base), and so 9/4 in base 4 is 2.14, since moving the decimal mark one digit to the left (from 21. to 2.1) is tantamount to dividing by the base (similarly, moving it to right corresponds to multiplying by the base).

Hopefully this theoretical information suffices for your problem.


Handwritten character recognition as characters are being traced I'm looking for an OCR technique (PCA or SVM or anything else) in a peculiar setting. I want to detect the motion of the finger so that if someone writes something in front of the camera in the air, I want to recognize the characters online (meaning as soon as they are written).

There is a paper "Using Mobile Phones to Write in Air". It basically uses the mobile sensors and machine learning to detect words. The Results show that English characters can be identiﬁed with an average accuracy of 91:9%.

There are some open source projects like "hand-gesture-detection" on Google code. I think you can use them as the start for your project.