Hamming distance necessary for detecting d-bit error and for correcting a d-bit error I am trying to understand what hamming distance of a code is needed to detect a d-bit error, or to correct a d-bit error.

This is what I have found around the web:

  If two codewords are Hamming distance $d$ apart, it will take $d$ one-bit
  errors to convert one into the other.

  To detect (but not correct) up to $d$ errors per length n of a codeword,
  you need a coding scheme where codewords are at least $(d + 1)$ apart in
  Hamming distance. Then d errors can't change into another legal code,
  so we know there's been an error.
  To correct $d$ errors, need codewords $(2d + 1)$ apart. Then even with $d$
  errors, bit string will be $d$ away from original and $(d + 1)$ away from
  nearest legal code. Still closest to original. Original can be
  reconstructed

I have seen in my other post that, in the image, the calculation of the bits that can be detected and correct is done using the reversed formula of the above statements 1. and 2:

If we have a hamming distance of $d$, we can detect $d - 1$ errors (inverse of the formula 1.), so to detect a $d - 1$ error, we need a hamming distance of d (same thing said in another way). So for example, if we want to know what is the hamming distance required to detect a 4 errors, we just have to apply the formula 1.

$4 = d - 1$

$4 + 1 = d$

We need a hamming distance of 5.

So to find the hamming distance required to correct $d$-bit errors, we have to apply the formula 1. $2d + 1$, where $d$ are the bit errors.

Am I correct?

If yes, could you explain me what the second part of the point 2. is saying:

  Then even with $d$ errors, bit string will be $d$ away from original
  and $(d + 1)$ away from nearest legal code. Still closest to original.
  Original can be reconstructed

By d-bit errors, we mean d number of errors, right?

The first step towards clarifying your confusion is forgetting about the formulas. You should be able to understand this material without looking at the formulas. You should even be able to develop the formulas on your own.

Now to the actual question at hand. Suppose we have a bunch of codewords, and every two are different in at least 10 positions. Suppose I send one codeword on the air, and an adversary corrupts (flips) $x$ bits. I claim that if he flips a small enough number of bits, then the receiver can detect that the adversary modified my codeword. The way she is going to do that is by noticing that what she got wasn't a codeword at all. If $x < 10$ then flipping $x$ bits, the adversary cannot reach another codeword, since by assumption any two codewords differ in at least 10 positions. So if the adversary flips $x < 10$ bits, the receiver will notice that the communication was corrupted on air. That's the meaning of "$d$-bit errors can be detected", where here $d = 9$.

Continuing the same scenario, the receiver isn't really interested in knowing whether some bits were flipped. Rather, she wants to know what the original codeword was. Suppose we can promise her that at most $y$ bits were flipped. When can she recover the original codeword? How is she going to recover the original codeword? Suppose that what she gets is the word $w$. She is going to look for the closest codeword $c$, and guess that the original codeword that was sent was $c$. When can we be sure that she is right?
Suppose that the original codeword was actually $o$. So the distance (number of different positions) from $o$ to $w$ is at most $y$ (since we allowed the adversary to flip at most $y$ bits). As $c$ is the codeword closest to $w$, the distance from $c$ to $w$ is also at most $y$. So the distance from $o$ to $c$ is at most $2y$. Since both $o$ and $c$ are codewords, either they are the same (and we win – the receiver found the original codeword), or $2y \geq 10$, since any two codewords differ by at least 10 positions. As long as $2y < 10$, this cannot happen. Reiterating, if $2y < 10$, then even if the adversary flips up to $y$ bits on air, the receiver can know what the original codeword was by looking for the codeword closest to the word she received. That's the meaning of "$d$-bit errors can be corrected", where here $d = 4$.

More generally, if the minimum distance of the code – the minimum distance between two codewords – is $D$, then the first argument will work as long as $d < D$, and the second as long as $2d < D$. Given $d$, the minimum value of $D$ satisfying $d < D$ is $D = d+1$, and the minimum value of $D$ satisfying $2d < D$ is $D = 2d+1$. That's where the formulas come from. But don't memorize the formulas. Understand where they come from instead.


Generate string with large Kolmogrov complexity Given $c$, can you generate a string $s$ with $K(s) \ge c$, along with a proof of that fact?

I think the answer is no except for small $c$, but I'm not sure.

No. This is basically Chaitin's incompleteness theorem.

Roughly, the theorem says that there exists a concrete constant $C$ (which is a function of your consistent set of axioms) for which no fixed string can be proven to have Kolmogorov complexity larger than $C$. The core idea is that if you could do it for every string, then you can write a program of size $\log n + O(1)$ to search for and eventually output strings with complexity $n$, which is a contradiction for sufficiently large $n$.


The use of binary search when determining whether a point lies inside a given convex hull In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says :

  For repeated queries with preprocessing allowed, we develop a special
  method that relies on the convexity of the polygon. Recalling Theorem
  3.5, the vertices of a convex polygon occur in angular order about any interior point. Find such a point O and consider the N rays from O
  that pass through the vertices of P. (Figure 4.8.) These rays
  partition the plane into N pie-shaped wedges. Each wedge is divided
  into two pieces by a single edge of P. One of these pieces is wholly
  interior to P, the other wholly exterior. Treating O as the origin of
  polar coordinates, we may find the wedge in which z lies by a single
  binary search, since the rays occur in angular order.

How would one do the binary search (assuming the convex hull's vertices are given in counter-clockwise order)?

So, the situation is that you have the vertices $\mathbf{v}_i$ of a polygon that defines a convex hull and a point $\mathbf{O}$ inside this polygon. Furthermore you have the vectors connecting $\mathbf{O}$ with each vertex of the polygon and the vertices are ordered. To construct a binary search algorithm that determines in which wedge the point $\mathbf{z}$ lies you have to find out on which side of a line connecting $\mathbf{O}$ and a given vertex $\mathbf{v}$ the point is.

Consider $\mathbf{r}_v$ to be the connecting vector from $\mathbf{O}$ to vertex $\mathbf{v}$. A normal vector $\mathbf{n}_v$ to $\mathbf{r}_v$ is simply given by

$\mathbf{n}_v = \left(\matrix{-{\mathbf{r}_v}_y \\ {\mathbf{r}_v}_x}\right)$.

Let us now project the vector $\mathbf{r}_z$ connecting $\mathbf{O}$ and $\mathbf{z}$ on the normalized $\mathbf{n}_v$:

$d_z = \frac{\mathbf{n}_v \mathbf{r}_{z}}{|\mathbf{n}_v|}$.

With the sign of $d_z$ we can now decide on which side of the line z lies.

Just draw down the situation and this construction and this will become obvious. There may be a more elegant way to do this but this approach will work.

You probably have to construct some more logic because the vertices actually are in a cyclic arrangement but that should not be too difficult.


The extension of a code is itself a code I'm reading Cover's "Elements of Information Theory" and I have a problem with the definition of uniquely decodable code.

  A code is said to be singular if there exist two elements that map to
  the same string. In other case it is said to be non singular.

  Let $C$ be a code. The extension of $C$ is the homomorphism $C^{*}$
  between $\chi$ and $D$ with respect to concatenation that is, $C(x_1
> \cdots x_n) = C(x_1) \cdots C(x_n)$.

  Let $C$ be a code. $C$ is uniquely decodable if its extension $C^{*}$
  is non-singular.

According to the last definition the extension of a code is itself a code but as it has domain $\chi^{*}$ where $\chi \subseteq \mathbb{R}$ (that last statement is mine).

How can I view the extension as a code?

Cover and Thomas are using here the following definition of a code: given a domain $D$ and an alphabet $A$, a code is a mapping from $D$ to $A^*$. That is, a code assigns every element of $D$ a word over $A$. The extension of the code is a code from $D^*$ to $A^*$ defined by concatenation.

For example, let $D = \{a,b\}$ and $A = \{0,1\}$, and consider the code $C$ given by $C(a) = 0$, $C(b) = 00$. Its extension $C^*$ is a function from $\{a,b\}^*$ to $\{0,1\}^*$ obtained by replacing each $a$ by $0$ and each $b$ by $00$. For example, $C^*(ab) = C(a)C(b) = 000$. Since $C^*(ba) = C(b)C(a) = 000$ as well, the code $C^*$ is singular.

A code $C$ is uniquely decodable if there do not exist two sets of words $x_1\ldots x_n$ and $y_1\ldots y_m$ such that $C(x_1)\ldots C(x_n) = C(y_1)\ldots C(y_m)$. This is exactly the same as saying that $C^*$ is non-singular, since the condition is completely equivalent to $C^*(x_1\ldots x_n) = C^*(y_1\ldots y_n)$.


n-polygon lattice datastructure? I'm trying to simulate a boardgame what can be played on a board with an arbitrary lattice, anything from triangles to heptagons to 37-sided regular polygons is allowed. Moreover the shape of the board is also arbitrary.

I need to represent this board in a data structure in which each tile has as its property a list of all its neighbouring tiles.

I was wondering if there is already some work done related to this that I might find helpful?

The way I'm trying to approach this problem is as follows: I first devise a coordinate system. Then I situate the virtual board within the coordinate system. Then I lay down the first tile and recursively lay down all neighbouring tiles until I cross the border. The approach is quite ugly and there is some uncertainty involved as I'm using angles and such to figure out the coordinates of each tile and it's all very messy. There must surely be a better way.

The board you want to draw is a planar graph whose faces (enclosed areas between edges) are the polygonal tiles: call this $G_\mathrm{b}$. The data structure you have in memory is a graph $G_\mathrm{m}$ whose vertices are the tiles and whose edges are the adjacency relation on the tiles. This graph is known as the dual of $G_\mathrm{b}$.
So, you need to compute the dual of $G_\mathrm{m}$ and use one of the algorithms for drawing planar graphs to draw that.

One possibe headache is that duals are not uniquely defined, as the Wikipedia article shows, so you might need to be careful to get the "correct" dual for your application. If you can't get that to work, another option would be to use a graph drawing algorithm to draw $G_\mathrm{m}$ and then obtain the board by using the perpendicular bisector of each edge.


sorting a sorted array that has been inc/dec by random numbers If given a sorted array of n distinct positive integers. And each element is incremented or decremented by a number between 0 and X. For positive integer X that is a function of n.

Formulate an algorithm that takes the inc/dec array and sort it. Make the run time O(n) when X is constant.

I am unsure with my solution. Firstly, I just choose an random number of buckets... 10. The proof seemed to work out. Is there a way to prove that using X(the variable from above) number of buckets will be better?

In addition, is there a way to utilize the fact the array has been sorted prior to being augmented?

My solution:

1.  Find the minimum and maximum of the array by iteratively going through the array

O(n)

2.  Create intervals for the k buckets (k = number of buckets)
int interval
int k = 10
interval = (Max – Min + 1)/k

3.  Assign each element to the bucket based on the interval
O(n)

4.  Sort each bucket
if there is ni elements in each ith bucket
the sorting using randomized quicksort S(ni) = O(nilogni)

5.  Combine all the elements
O(n)
Runtime Analysis:
•   The time to sort every bucket will be as follows:
•   We assume the elements are uniformly distributed. Thus n/k elements in each bucket.

Since k = n/10, T(n) = n log(10) = O(n)

Your algorithm doesn't work since you're analyzing it under some (suspect) random model, whereas the problem setters wanted a worst case guarantee. The worst case for you is that everything falls into the same bucket, and then you just get the usual $O(n\log n)$ guarantee.

Instead of your approach, I suggest trying to use the following observation:

  After sorting, each value moves at most $2X$ positions.

As an example of why this is useful, note that you can find the minimum of the array in time $O(X)$ by looking only at the first $2X$ elements.


How to reduce the number of crossing edges in a diagram? I am working on a diagram editor.
Diagrams display 2D shapes (nodes) connected with connectors (edges).

I'd like to add an operation that, given a selection of nodes, "disentangles" them: it repositions them to reduce the number of crossing edges, if possible
(and it's OK if the edges will have to be drawn with bend points).

So I want a graph algorithm that, given a (topological) graph embedding and a subset of its nodes, modifies the embedding (its topology) on only those nodes so as to minimize the number of crossing edges.

From reading about apex graphs and browsing Cabello and Mohar (2013), I suppose this problem is NP-hard.
So I'll be happy with a parametrized algorithm (e.g. on the number of crossing edges) that has a known, polynomial, time complexity for any given parameter value. This seems feasible, but I don't find it easy to come up with such an algorithm on my own.

Questions:

Where do I look for such an algorithm?
Does it exist?
In existing software?
Is there any significant practical experience with such an operation? (What looks good in theory may not be so good in practice, or vice versa.)

(I am not sure where best to ask this question: here, on StackOverflow, or MathOverflow?)

Computing the absolute minimal crossing number is, as you observed, $\text{NP-hard}$. The process of drawing the graphs should be at least as hard as that.
The problem posed in the question is actually harder and more involved than the above. You are considering graph nodes of a certain size and shape while also bounding the size (area) of the result. In addition, a not yet determined notion of aesthetics is desired. Obviously we want a heuristic for this, which does not use the absolute minimum in the general case. The number of nodes encountered in such an application are likely not huge in the average case. Drawing the minimal edge crossing version of the graph may be feasible for small sizes.
Resources:
You may be interested in the following resources, particularly with the first:

The documentation for a feature of the Graphviz package presents an algorithm that generates nice looking directed graphs: http://www.graphviz.org/Documentation/TSE93.pdf
It has multiple other features that may prove useful. The source code is located on their website under EPL. It also includes a page dedicate to the theory behind graph visualization.
For a fixed-parameter algorithm check a paper by Martin Grohe:
Computing Crossing Numbers in Quadratic Time
A tech talk given by Amina Shabbeer at RPI:
Preserving Proximity Relations and Minimizing Edge-crossings in Graph Embeddings
An example of an efficient probabilistic algorithm can be found in this paper by Julia Chuzhoy:
An Algorithm for the Graph Crossing Number Problem

There are plenty of other resources, too. These should help you get started.
Additional Thoughts & Observations:
Here is an idea to get around the issues concerning the shape and size of nodes. Given the graph (infinitely small nodes), expand each node while "pushing" or bending edges out of the way (ex. using splines while enforcing a limit on proximity). You need to do this with other edges and nodes that get in the way of it, which can start a chain reaction. Look into how an equilibriums can be efficiently computed (ex. molecular structures). If you cant get the shape of a node to the desired size, then scale the whole diagram.
A user might enjoy the results of a randomized algorithm. They could use your feature multiple times until they got something they liked. Avoid redundant computation in this case (no need to compute a crossing number again).


Truth value of a proposition I'm trying to write a function in Python that takes it argument as a Python list and returns a boolean value based on the truth vale of the proposition $E(x) \to \exists y \text{ s.t. } x=2y$, where here the proposition $E(x)$ means 'x is even'.

print(check_prop([-2,-1,0,1,2,3])) gives an output true

print(check_prop([-2,-1,0,1,3,4])) gives an output false

I don't quite understand how the truth value is true in the first case and false in the second.

The predicate whose truth value you're trying to check states the following:

  For every even number $x$ in the list, $x/2$ is also in the list.

This holds in the first case: the even numbers are $-2,0,2$, and indeed $-1,0,1$ are in the list, but not in the second case, since $4$ is in the list but $2$ isn't.


how does an object find the reference to its instance variables I'm trying to understand how instance variables for a given object are stored for easy access later on.

For some background, I understand that if you have a reference to an array it is very easy for a computer to access any particular item in the array with an efficiency of $O(1)$ by just multiplying the index provided with the size of each item and adding that to the address of the array.

However it is not always meaningful to store things with just an index and so this is where things like HashMaps can come in handy because they allow someone to store a particular value based on a key and retrieve it in the same $O(1)$ efficiency.

So now imagine that we have some class that has many many instance variables

class myClass {
    int a1;
    int a2;
    int a3;
    ...
    int a500; //or some other really big number
}

and I write some code such as

myObject is new instance of myClass;
myObject.a5 = 123;
myObject.a450 = 70;
//etc

So my questions is:

How does the the .a450...etc get turned into an address?  This type of access seems a lot more like the hashMap described above where a450 is a key that stores some corresponding value... however a hashMap really only attains that $O(1)$ access by careful maintenance of things such as the load factor.  And to achieve the proper load factor you need to have a certain amount of empty items.  There is also the issue that even though both hashMap and arrays have the same $O(1)$ access time... in practice the array will be much faster because there is no need to compute a hash function.  It seems like this would not be an appropriate way to manage objects in any given language because if you have hundreds or thousands of such objects, then the overhead of having a hashmap would be very wasteful.

Since the class is fixed in advance in C++-style languages, the offset to a5 or a450 is known in advance, in compile time. Each instance of the class contains a copy of each instance variable at a fixed location (relative to the address of the instance), so there is no "load factor" to talk about. So myObject.a5 translates to something like myObject[5].

Other programming languages such as python support dynamic addition of instance variables. In that case the instance variables are stored in a hash table, which as you mention has $O(1)$ amortized access time. (Perhaps some instance variables are stored in fixed locations, for the sake of optimization.)


Is something missing in this EXPLORE algorithm? It took me about a week to understand how does it works, but still, I'm wondering if it actually works!

I. The algorithm EXPLORE

EXPLORE (S:sommet, D:following vertices of vertex X, visited:TAB)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LIST ≠ 0
    selectionner i ∈ LIST
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
    ELSE LIST←LIST - {i}

II. running the algorithm

Then I tried on this Graph:

array of the following vertex of each vertex:

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
a & b,c,d\\
b & d,e\\
c & d,f \\
e & d,h \\
f & g,i \\
g & h, e \\
h & \emptyset\\
i & g,h \\
\end{array}

M: the visited tab
L: the given list, which is empty in the beginning

Explore (a,$\Gamma$,M)

M$\leftarrow${a}

L$\leftarrow${a}

$\Gamma(a) ∩ (X  \backslash  M)=bcd \ne0$

list $ \ \ \ \ \ \ \ $notvisited

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b}$ why do we add b to L??

$\Gamma(b) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d}$ why do we add b to L??

$$...$$

$\Gamma(e) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d,f,g,h}$ That seems normal on the aglorithm, it corresponds to

Else LIST = LIST - i

$$...$$

Until

$\Gamma(d)$

$L\leftarrow a$

which leads to the components we didn't searched for:

$\Gamma(a) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,c}$ Still, wher the hell does this e comes in the algorithm?

$\Gamma(c) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a}$ I'm okay with its disparition

$\Gamma(a) ∩ (X  \backslash  M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ L\leftarrow {\emptyset}$ I'm okay with its disparition

III. My ideas to make it works

if ever it doesn't work!

I wonder if something is not lacking in the algorithm, if we shouldn't add an Explore within the 'if' loop.

EXPLORE (S:sommet,  Γ, visited)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LISTE ≠ 0
    selectionner i ∈ LISTE
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
      **EXPLORE(j,Γ,visited)**
    ELSE LISTE←LISTE - {i}

This might be a bit too much, but I tried the best I could to condense it.  Unfortunately, Java doesn't allow one to write concise code...  So, here's breadth-first and depth-first traversal of a graph (I used JGraphT) library for graph implementation.  This should better illustrate the idea.

package tld.se.doodles;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultDirectedGraph;

public class GraphSearch {

    public static void main(String ...args) {
        DefaultDirectedGraph<Integer, DefaultEdge> graph =
                new DefaultDirectedGraph<>(DefaultEdge.class);
        int[][] vertices = {
            {1, 2}, {1, 3}, {2, 1}, {2, 3},
            {3, 5}, {3, 6}, {3, 4}, {4, 7},
            {5, 2}, {5, 6}, {6, 3}, {6, 7}
        };
        Arrays.stream(vertices)
                .forEach(pair -> {
                        graph.addVertex(pair[0]);
                        graph.addVertex(pair[1]);
                        graph.addEdge(pair[0], pair[1]);
                    });
        depthFirstTraversal(graph);
        breadthFirstTraversal(graph);
    }

    private static void depthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Depth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        dftHashed(start, graph, cache);
    }

    private static void dftHashed(
        Integer from, DefaultDirectedGraph graph, HashSet cache) {
        if (!cache.contains(from)) {
            cache.add(from);
            System.out.format("Visiting: %d%n", from);
            graph.<DefaultEdge>edgesOf(from).stream()
                    .forEach(edge ->
                             dftHashed((Integer)graph.getEdgeTarget(edge),
                                       graph, cache));
        }
    }

    private static void breadthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Breadth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        HashSet<Integer> firstGen = new HashSet<>();
        firstGen.add(start);
        bftHashed(firstGen, graph, cache);
    }

    private static void bftHashed(
        HashSet previous, DefaultDirectedGraph graph, HashSet cache) {
        cache.addAll(previous);
        HashSet<Integer> next = (HashSet<Integer>)previous.stream()
                .flatMap(vertex -> {
                        System.out.format("Visiting: %d%n", vertex);
                        return graph.<DefaultEdge>edgesOf(vertex)
                            .stream().map(graph::getEdgeTarget);
                    })
                 .collect(Collectors.toCollection(HashSet::new));
        next.removeAll(cache);
        if (!next.isEmpty()) bftHashed(next, graph, cache);
    }
}


Why are transcendental functions of large numbers inaccurate on computers? For instance, why is it hard to accurately compute sin(1e99)? I suspect it has something to do with rounding error.

There's nothing fundamentally hard about computing $\sin(10^{99})$.  You simply compute $x = 10^{99} \bmod 2\pi$, then compute $\sin(x)$.  (Why is this valid?  It's because $\sin(x)=\sin(y)$ if $x\equiv y \pmod{2\pi}$.)  It's not too hard to compute $x$ if you use a numerical representation that has enough digits of precision, and then to compute $\sin(x)$ using standard methods.

However, a standard double won't have enough precision to perform this computation.  It only has about 53 bits of precision; that's a lot less than the $99 \lg 10 \approx 329$ bits of precision you'd need to be able to distinguish $10^{99}$ from $10^{99}+1$. (A standard IEEE float cannot even represent values in excess of $3*10^{38}$). Of course, $\sin(10^{99})$ is very different from $\sin(10^{99}+1)$.  So, if you want to compute $\sin(10^{99})$, just stuffing $10^{99}$ into a float or double and then trying to invoke the $\sin(\cdot)$ function on that is not going to end well.

If you want to compute $x$ to at least $b$ bits of precision, you'll probably need a numerical representation that can represent $10^{99}$ to at least $329+b$ bits of precision (probably more than that, for intermediate values that arise during the modular reduction).  A float or double ain't gonna be enough for that.


k disjoint triangles with graph splitting to two distinct groups Please note that this question is different than this question.
The $k$-disjoint triangles problem is as follows:

Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?

An FPT algorithm is presented here (starting from slide 60). The algorithm uses color-coding and relies on dynamic programming to determine if a solution is highlighted (each vertex in the solution group is colored with a distinct color). The running time of the algorithm is $O^{*}((2e)^{3k})$.
Now, Let's assume that we get a group $X \subseteq V$ of vertices, and the problem changes: Are there $k$ vertex-disjoint triangles in $G$ where one vertex is from $X$ and the other two are from $V \setminus X$?
I need to find an algorithm whose running time is $O^{*}((2e)^{2k})$. I tried coloring all vertices from $X$ in a single color, but I couldn't find a way to avoid the duplicate choices of vertices from $X$. I also try to color each vertex from $X$ in a distinct color that is different from the colors of $V\setminus X$ but the running time is higher.
Can you propose a coloring method that will highlight a possible solution within the required complexity? Should I try something else?

Color the vertices in $V \setminus X$ with $2k$ colors at random. With probability $e^{-2k}$, the $V \setminus X$ vertices of your $k$ disjoint triangles will be highlighted.
Suppose without loss of generality that $X = [m]$.
Using dynamic programming, determine for each subset $S \subseteq [2k]$ and $i \in [m]$ whether there exist $|S|/2$ disjoint triangles using the colors in $S$ and vertices $1,\ldots,i$ of $X$. This takes time $O^*(2^{2k})$.


What precisely is infinite ambiguity in a grammar? From what I've read, an example of infinite ambiguity is usually given in a form of a loop:

$S \rightarrow aA \\
A \rightarrow B \\
B \rightarrow A \\
B \rightarrow b$

But a grammar is called ambiguous if there's more than 1 way to derive the input string ω. What if I then take this well-known ambiguous grammar:

$S \rightarrow SSS \\
S \rightarrow SS \\
S \rightarrow b$

and extend it with $S \rightarrow \epsilon$
so that for any member of $\left\{ b^n \middle| n \geq 0\right\}$ there's infinitely many ways to derive it? Does this make the grammar infinitely ambiguous?

From a comment by Sylvain:

A grammar is infinitely ambiguous iff there is a productive and accessible nonterminal $A$ s.t. $A \Rightarrow^+ A$. Nonterminals $A$ and $B$ fulfill this characterization in your first example, and so does $S$ in the second example when you add the rule $S \to \varepsilon$. I'll leave the proof of the characterization as an exercise.

   Consider that a parse tree of infinite size for a finite input sentence must repeat a nonterminal spanning the same interval in the input.


Prove finding k disjoint paths from n given paths in a directed graph is NP-complete Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node.

Prove that the given problem is in NP-complete.

I was able to prove that the problem is in NP. Hint is that we need to come up with a polynomial time reduction of the independent set problem to this problem prove that it is in NP-hard.

Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ with $|V|=n$ and of an integer $k$.

Construct the graph $H = (V', E')$ where $V' = V \cup \{ x_{u,v} \, : \, (u,v) \in E \}$ and $E' = V' \times V'$.

For each $u \in V$ let $v_1, v_2, \dots, v_h$ be the neighbors of $u$ in $G$ and define the path $P_u = \langle u, x_{u,v_1}, x_{u,v_2}, \dots, x_{u,v_h} \rangle$ in $H$.
Let $\mathcal{P} = \{P_u \, : \, u \in V\}$.

There is an independent set of size at most $k$ in $G$, if and only if there is a subset $\mathcal{P}'$ with $|\mathcal{P}'| \le k$ such that the paths in $\mathcal{P}'$ are pairwise vertex-disjoint.

More precisely, if $S$ is an independent set of $G$, then $\{ P_u \, : \, u \in S \}$ is a collection of pairwise vertex-disjoint paths in $H$ and, if $\mathcal{P}'$ is a collection of pairwise vertex-disjoint paths in $H$, then $\{u \, : \, P_u \in \mathcal{P}' \}$  is an independent set of $G$.


Confusion with analysis of hashing with chaining I was attending a class on analysis of hash tables implemented using chaining, and the professor said that:

  In a hash table in which collisions are resolved by
  chaining, an search (successful or unsuccessful) takes average-case time θ(1 + α),
  under the assumption of simple uniform hashing.

and

  The worst-case time for searching is θ(n) plus the time to
  compute the hash function.

These are quoted from out textbook, ITA. Here α is the load factor, which is equal to n/m where n is the total number of elements to be inserted to the hash table and m is the size of the hash table (which is a constant for each implementation).

My confusion arises from the thinking that

  θ(1 + α) = θ(α) = θ(n/m) = θ(n)

So I claimed that θ(1 + α) = θ(n), ie the average case and worst case time complexities are the same and the professor disagrees with me.

She asked me to find out by myself why I am wrong. I did some brainstorming and the only deduction I can make is that either I am wrong in assuming that m is a constant or asymptotic notations can't be used to compare between worst-case and average-case running time in this case. Please help me find what is wrong here. Also  I don't understand why θ(1 + α) is not written simply as θ(α) and also why the professor insists on the value of α being less than, equal to, or greater than 1

The reason that we are using $\Theta(1+\alpha)$ rather than $\Theta(\alpha)$ is that $\alpha$ could be very small. Imagine for example that the hidden constant in both $\Theta$s is one, and that $\alpha=0.000001$. There is a large difference between $1.000001$ and $0.000001$.

Regarding your wrong deduction, note that the first paragraph mentions average case and the second worst case. It's true that the average case is at most the worst case, but not the other way around.


What is the maximum number of indices one can create on a table with N columns? Say, I have a database table with $N$ columns. What is the (theoretical) maximum number of indices I can create on that table? For $N = 1,2,3$ it's easy enough to calculate the answer $(1, 4, 15)$, but is there any formula? Also, is there a "name" for this number?

I assume you mean the following: given $N$ columns, there are

$N$ single columns, giving $N$ different indices
$N(N-1)/2$ pairs of columns, and 2 ways to combine each pair, giving $N(N-1)$ different indices
$\frac{N(N-1)(N-2)}{2 \cdot 3}$ triples of columns, and $3 \cdot 2$ ways to combine each triple, giving $N(N-1)(N-2)$ different indices

and so on. This number doesn't have a (well-known) name, but the sequence does have its own OEIS entry:

  Eighteenth- and nineteenth-century combinatorialists call this the number of (nonnull) "variations" of n distinct objects, namely the number of permutations of nonempty subsets of {1,...,n}.

Various formulas are given to compute it, including a recurrence relation $a_n = n(a_{n-1} + 1)$ and the rather surprising $a_n = \lfloor{e \cdot n! - 1}\rfloor$.

One could argue that you can create more indices by taking into account that columns can be used in ascending and descending mode. For indices with more than one column, this even has an influence on which records are 'near' each other.


Ford-Fulkerson algorithm with asymmetric adjacency matrix Suppose that I have a bipartite graph $G=(A \cup B, E)$ and $A = \{1, 2, \dots, n\}$, $B = \{1, 2, \dots, m\}$.
After a virtual sink $s = 0$ and a source $t = n+1$ is included into the graph, I want to implement Ford-Fulkersen max flow algorithm.

To the algorithm, we need a symmetric adjacency matrix, therefore $O((n + m)^2)$ space.

However, in a bipartite graph, it is enough to use an adjacency matrix with $O(nm)$ space. But I could not figure out how to modify the algorithm so that it works with an asymmetric adjacency matrix.

Is there any way that Ford-Fulkersen max flow algorithm works in above scenario?

The algorithm doesn't need a symmetric adjacency matrix. It needs to keep track of a flow and a residual network. Both are supported on the edges of $G$ and their inverses. You can store them in roughly the same way you store your graph $G$, using the same amount of space (up to a multiplicative constant).


Datastructure for managing (abstract) sets I am looking for a datastructure to represent the complex relationships between a bunch of abstract sets. The "abstract" means that these sets are not defined by their elements, but by their relationship to each other. This means that for me a set is nothing more than a named thing with a relations to other named things in the same space. For two sets $A,B$ the relation can be

they represent the same set, i.e. $A=B$,
they are complementary, i.e. $\bar A=B$,
they are disjoint $A\cap B=\varnothing$ but not complementary,
they are overlapping, i.e. they are not equivalent but have a non-empty intersection,
one is a proper subset of the other set, e.g. $A\subset B$
essentially unknown, but maybe some of the former cases can be excluded.

Besides storing these relationships, I want to ask questions on the datastructure like

Are the sets $A$ and $B$ disjoint?
Name me a subset of $A\cap\bar B\cap \bar C$.
What is the relation between the sets $X$ and $\bar Y\cap Z$?

Also the datastructure should be updatable. There will be inserted new sets all the time which must be integrated in the structure correctly. There can be lots of sets and it is no option to explicitely store the relation between any pair of sets. Instead, some relations should be deducable by the query algorithms. For example, if we have $A\subset B\subset C$, then we will not store $A\subset C$ as this follows logically from the other two relations.

I thought about lots of tree like structures or cycle-free directed graphs. But maybe someone already developed exactly what I am looking for.

One more thing: I would prefer when the datastructure does note introduce big differences between sets and their complement. This means, asking whether $A\cap B$ is empty should not invoke vastly different algorithms than asking this for $A\cap \bar B$.

Update

To answer some comments, here are some more details on my intend.

You can think about this as a big (hyper-)graph problem, where the whole graph is too big to be stored but has much structure, so maybe can be stored very efficiently in another way. The nodes of the graph are sets. The (hyper-)edges are relations between the sets. The edges are colored to represent the six possible relation types from above. In this sense, the graph is an edge-colored complete graph. Note that the edge type unknown is very important to me!

To describe the queries in general, let me introduce the following notation: given a set $A$, we write $A^+=A$ and $A^-=\bar A$. The following queries should be supported as efficient as possible:

Given a sequence of nodes $A_i$ and a sequence of signs $s_i\in\{+,-\}$. Which of the following three options is true for $\bigcap_i A_i^{s_i}$: it is empty, there is a node representing a subset of this intersection, we do not know anything.
Given two sequences $A_i$, $B_i$ of nodes and two sequences $s_i$ and $r_i$ of signs. What kind of edge is between $\bigcap_i A_i^{s_i}$ and $\bigcap_i B_i^{r_i}$?

The last query seems trivial for the graph stored with all its edges. But as I said, the graph is probably too big to be stored in this naive way.

Of course, I never stated that for sets $A_i$ and signs $s_i$ my data structure must contain the set $\bigcap_i A_i^{s_i}$, but information can be deduced in other ways. For example, assume $A$ and $B$ are sets, but $A\cap B$ is not stored. But we have a set $C\subset A,B$. So we know that $A\cap B$ $-$ despite being not stored explicitely $-$ is not empty. If we lack any of these information, then we may conclude that "we do not know anything about $A\cap B$". The fact that $A\cap B$ is empty is stored by an edge between $A$ and $B$ signalling that these sets are disjoint.

Why I wrote hyper-edge instead of just edge? It might be necessary to store that $A\cap B\cap C=\varnothing$ but no two of these sets are disjoint. This cannot be deduced from any two set relation. So we may need edges involving more than just two sets.

One simple approach:
For each abstract set $A$ create a node. Let each node maintain a list of
1) complementary sets
2) disjoint sets
3) overlapping, i.e. they are not equivalent but have a non-empty intersection
4) proper subsets

For example, consider the following node

NODE: 123F65
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> propers
----

Assume that you have created a set $A$. Allocate a new node for this set and let $A$ point to this node.

 HASH TABLE
 ______________
 |A| |-> 123F65
 ______________

Then assume you add a new set $B$ with a property $A=B$. You don't create a new node, just make $B$ point to the same location $A$ points to, 123F65.

 HASH TABLE
 ______________
 |A| |-> 123F65
 |B| |-> 123F65
 ______________

Then assume you add a new set $C$ which is a proper subset of $B$. Create a new node for $C$ and make $C$ point to that node. Additionally add $C$ to to the list of proper subsets of $B$ in 123F65.

NODE: 123F65
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> [ C ]
----

NODE: 153F60
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> propers
----

HASH TABLE
 ______________
 |A| |-> 123F65
 |B| |-> 123F65
 |C| |-> 153F60
 ______________

So for example, if I want to find out if $A$ and $B$ is disjoint, I would check if $A$ is a subset of any $B$'s complementary or if $B$ is a subset of any $A$'s complementary. If yes then the answer is "disjoint", otherwise they are not disjoint or insufficient information.

Note that this data structure is just a kick-off. You may have to change it as you will ask different questions or you want to speed up queries.


Size of intersection of two acyclic DFAs A and B is O(|A|+|B|)? Acyclic DFAs recognize finite languages. For more info, see this Wikipedia page : https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton

To explain that the product of two DFAs $A$ and $B$ could lead to a result of size $O(|A|.|B|)$ in the worst case, most examples make use of DFAs containing cycles (those cycles are responsible in creating |A| copies of B in the result) like in this example :

As they are much more simpler than standard DFAs, I am wondering if the product operation (and more specifically union/intersection operations) of two acyclic DFAs $A$ and $B$ could result in a DFA of size $O(|A| + |B|)$ in the worst case ?

According to the article "State Complexity of Union and Intersection of
Finite Languages" here :
http://toc.yonsei.ac.kr/~emmous/papers/dlt07.pdf
the authors say that the size of the DFA resulting from the product of two acyclic DFAs $A$ and $B$ remains in $O(|A|.|B|)$ only if the alphabet used is of variable size that depends on the size of the input DFAs. Thus, they conclude that this upper bound is $unreachable$ if the alphabet is of fixed size.

Does it mean that given a fixed size alphabet (e.g. $\sum=\{a,b\}$) and two DFAs $A$ and $B$ defined on $\sum$ , there is still the possibility that the intersection of $A$ and $B$ could result in a DFA of size $O(|A| + |B|)$ in the worst case ?

I would appreciate any counter-example, proof or reference to a paper dealing with this problem.

Many thanks, Luz.

Lemma 4 and Lemma 8 in your paper show that even for a fixed size alphabet, there are infinitely many finite languages with minimal DFAs $A,B$ of sizes tending to infinity such that the minimal DFAs for the intersection and union languages has $\Omega(\min(|A|,|B|)^2)$ states.


Hashing algorithm for millions of variable length strings (URLs) The goal is to distribute approximately 100 million variable length strings, average length 100 characters, uniformly among 100 million buckets. Perfection not required, just no egregious clumping. The strings are URLs. They tend to begin much the same way and end much the same way (e.g. h t t p:// or w w w. and  ".c o m", ".e d u", "a s p x" and so forth) and show their greatest variation in the latter half of the string, except for the final few characters.

What's a good algorithm that would accept the string and the number of slots as inputs, and return a number between 0 and SlotCount-1, and satisfy the uniform-distribution requirement?

Any string hashing algorithm designed for ASCII text should work fine. Take a look at the Wikipedia article, consider if the set could be manipulated by an adversary to create pile-ups (algoritmic vulnerabilities). If that isn't an issue, at strchr and partow several "classical" hash algorithms are given and compared. Get a subset of your data and use the parameters suggested there for your own comparison. And please tell us the results.


How to transpile generic functions into language that do not support generics? Currently, I am developing a transpiler for my own language, however, I find difficulties to transpile generic functions. For example, how would you translate the following Java-like code in to C?

interface Comparable<T> {
    boolean compare(T that);
}

class Person implements Comprable<Person> {
    public string name;
    public boolean compare(Person that) {
        return this.name.compareTo(that.name);
    }
}

// The generic function
<T extends Comparable<T>> boolean isSorted(T[] xs) {
    for(int i = 1; i < xs.length(); i++)
        if(xs[i-1].compare(xs[i]) > 0)
            return false
    return true
}

My current solution is to use Javascript prototypes. So, the code above would be translated into the following Javascript (workable in Google Chrome):

class Person { }

Person.prototype.compare = function (that) {
    return this.name.localeCompare(that.name);
}

function isSorted(xs) {
    for (var i = 1; i < xs.length; i++)
        if(xs[i-1].compare(xs[i]) > 0)
            return false;

    return true;
}

However, Javascript prototype suffers performance issue (I tested it myself), so I am looking for other ways to translate generics without using prototypes. That is why I'm looking for example on how to translate that into pure C.

Note: You might also translate it to any language you like, as long as you did not use generics.

When compiling to a target language without generics, there are two main strategies.

Monomorphization: if you have a generic function, and it's instantiated with types $T_1\ldots T_n$ throughout your program, you make $n$ copies of the function, with the concrete type replacing the generic variable. This tends to result in fast but large code, since there's lots of duplication.
Boxing: you can "box" the generic variables behind some sort of reference type, and cast to and from this type when entering and exiting your generic function. The guarantees of the source language ensure that these casts are always safe. For example, in C you probably want to use void*.

If you're looking for resources, generics are known as "parametric polymorphism" in the Programming Languages literature, so that might help your search.

If you're compiling from a Java-like OO language, you'll also need to attach a VTable to your objects: a table of pointers to their methods, you get Java's dynamic dispatch (i.e. the method of an object depends only on its runtime type, not it's compile-time type).

Having "bounded polymorphism" with option 2 (i.e. the T extends Comparable<T>makes this a little more tricky, since you need to come up with some sort of boxed representation that lets you find your Comparable methods. You could do a dynamic lookup to find such methods, but this is slow. I'd search around for how to compile bounded polymorphism, you'll probably find a better answer.


polynomial reduction & co np complete I would like to know how we can demonstrate these two problems :

$A \leqslant_p B$ implies  $\overline A \leqslant_p \overline B$
The complement of 3-SAT is co-NP-complete

For the first one, since $A \leq_p B$, there must exist a function $f \in \operatorname{FP}$, such that $x \in A$ if and only if $f(x) in B$ for an arbitrary word $x$. We can prove that $f$ is also a reduction from $\overline A$ to $\overline B$ as follows: Let x be an arbitrary word.
\begin{align}
x \in \overline A &\iff\\
x \notin  A &\iff\\
f(x) \notin B &\iff\\
f(x) \in \overline B&\\
&\qquad\square
\end{align}

Now for the second part, we know that 3-SAT is NP-complete. For a given language $A \in \operatorname{co-NP}$, let $B = \overline A$. Clearly $B \in \operatorname{NP}$ and hence, there is a reduction from $B$ to 3-SAT. As proven above, the same reduction is a reduction from $A$ to the complement of 3-SAT.


Proving that a preorder traversal of a rooted tree can be performed in linear time Definition:
Let $T(V, E)$ be a rooted tree with root $r$.
If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$.
If $\lvert V \rvert > 1$, let $T_1, T_2, \dots, T_k$ denote the subtrees of $T$ from left to right. The preorder traversal of $T$ first visits $r$ and then traverses the vertices of $T_1$ in preorder, then the vertices of $T_2$ in preorder, and so on until the vertices of $T_k$ are traversed in preorder.
Question:
How does one prove, using the above definition, that a preorder traversal of a rooted tree $T(V, E)$ can be computed in $O(\lvert V \rvert)$ time? Since $T$ is a tree, $\lvert E \rvert = \lvert V \rvert - 1$, and so showing that a preorder traversal algorithm simply visits the vertices and edges of $T$ a constant number of times and does constant work on each visit would do it. Obviously this is true, but how does one prove this formally?

You can prove that formally by using structural induction. The structure of the proof is as follows:

Observe that a preorder traversal of a tree with $1$ vertex requires constant time.

Then, assume that a preorder traversal of a tree with up to $i \ge 1$ vertices can be performed in time at most $c \cdot i$, for a suitable constant $c$, and show that the preorder traversal of a tree $T$ with $i+1$ vertices requires at most $c \cdot (i+1)$ time. Here you use the induction hypothesis and the definition of the traversal. In particular, notice that the subtrees of $T$ that are rooted in the children of the root have at most $i$ vertices.


Hash size: Are prime numbers "near" powers of two a poor choice for the modulus? Cormen et al.'s "Introduction to Algorithms" says the following about the division method hash function $h(k)=k \text{ mod } m$:

  A prime not too close to an exact power of 2 is often a good choice for $m$. For example, suppose we wish to allocate a hash table, with collisions resolved by chaining, to hold roughly $n=2000$ character strings, where a character has 8 bits. We don't mind examining an average of 3 elements in an unsuccesful search, so we allocate a table of size $m=701$. The number $701$ is chose because it is a prime near $2000/3$ but not near any power of 2.

The book, however, does not explain what it means by "near". Is $701$ preferrable over, say, $661$ because $661-512<701-512$? I do not understand how this is relevant to the modulo function involved in the calculation of $h(k)$.

If a string of 8 bit bytes is interpreted as a large integer, and you calculate the value modulo $2^{24}-1$ then the first, fourth, seventh byte etc. are all hashed to the same value, which means the hash will not be well distributed.


Book CS:APP, using bit set and bit clear Okay so I'm going through a book CS:APP.
I'm in chapter 2. And problem 2.13 talks about how the Digital Equipment VAX computer used bis (bit set) and bic (bit clear) instead of Boolean operations AND and OR.
Both instructions take a data word x and a mask word m. They generate a result z consisting of the bits x modified according to the bits of m. With bis, the modification involves setting z to 1 at each position where m is 1. With bic, the modification involves setting z to 0 at each position where m is 1.
Now you're given x and y. And you're allowed to use bis and bic to recreate x | y. And x ^ y.
Now I have already tried looking at the answers to understand what's going on. But I don't understand it.
If I literally look at explaination for bis and bic I would say bis just copies the mask and leaves x unused. And for bic it goes opposite of m, but also without using x. If I try to interpret it differently I end up with questions like what does bic do (for example) when m is 0?
The answers are for x | y: bis(x, y) where y becomes m... so a relatively simple answer.
And for x ^ y (xor): bis(bic(x, y), bic(y, x)) where y and then x becomes m
So basically anything that could clarify what's going on here would be much appreciated!
And aside from this question, I also would like to ask if this is the right place for questions about a specific CS book? Because I'm teaching myself and don't have a teacher or someone to ask questions to and seeing with the previous exercise I also had a question it's possible that I might get a lot. But I can't find anything when searching on CS:APP (Computer Systems: A Programmer's Perspective) and yeah don't know where else to turn to. The book was recommended through teachyourselfcs.com if anyone was wondering.

If $z=\mathrm{bis}(x,m)$ then
$$
z_i = \begin{cases}
x_i & \text{if } m_i = 0, \\
1 & \text{otherwise}.
\end{cases}
$$
This is exactly bitwise OR.
If $z=\mathrm{bic}(x,m)$ then
$$
z_i = \begin{cases}
x_i & \text{if } m_i = 0, \\
0 & \text{otherwise}.
\end{cases}
$$
This is bitwise AND of $x$ and the bitwise complement of $m$.
In order to see how $\mathrm{bis}(\mathrm{bic}(x,y),\mathrm{bic}(y,x))$ computes bitwise XOR, we just need to compute the truth table:
$$
\begin{array}{c|c|c|c|c}
x & y & \mathrm{bic}(x,y) & \mathrm{bic}(y,x) & \mathrm{bis}(\mathrm{bic}(x,y),\mathrm{bic}(y,x)) \\\hline
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 & 0
\end{array}
$$
Another way of seeing this is replacing $\mathrm{bis}(x,y)$ with $x \lor y$ (read: $x$ or $y$) and $\mathrm{bic}(x,y)$ with $x \land \lnot y$) (read: $x$ and not $y$):
$$
(x \land \lnot y) \lor (\lnot x \land y),
$$
which is one of the standard formulas for XOR. In C, it would look as follows: (x & ~ y) | (~x & y).


Determining if match is possible I have a list of patterns with each pattern containing one or more wildcards. For example:

abc*
a*
*a*z*
*z

Wildcard (*) matches one or more characters. For example, any input string starting with 'a' would match a pattern a*.

How can I determine if there exists an input string that would match all of the provided patterns?

The language-theoretic answer:

Convert each regexp to a DFA, then use the product construction to take the intersection of their languages. Check whether the resulting DFA accepts any word (i.e., whether its language is non-empty).  This might take exponential time in the worst case.

The pragmatic answer:

Every pattern has the form $\alpha \texttt{*} \beta \texttt{*} \gamma$, where $\alpha,\gamma$ are (possibly empty) strings of letters (without wildcards), and where $\beta$ is a (possibly empty) pattern (i.e., a string of letters and wildcards).  Let the patterns be $\alpha_i \texttt{*} \beta_i \texttt{*} \gamma_i$ for $i=1,2,\dots,n$.  Find a string $A$ so that each $\alpha_i$ is a prefix of $A$; if no such string exists, output "NO" and terminate.  Find a string $C$ so that each $\gamma_i$ is a prefix of $C$; if no such string exists, output "NO" and terminate.  Find a string $B$ that matches $\texttt{*} \beta_i \texttt{*}$ for each $i$; this can always be done.  Finally, output "YES" and the string $ABC$.

This is your exercise, so I'll let you figure out how to find each of $A$, $B$, and $C$ -- it's not hard.


Why does decreasing the gap size in Shell sort never undo previous sorts? I came across this sentence in the Wikipedia article on Shell short, which states that

  If the file is then k-sorted for some smaller integer k, then the file remains h-sorted.

I've seen this claim in other texts like Lafore as well, but I can't wrap my head around why it's true.  Of course I can't find a counterexample, but why must it be so?

Here is an argument that I find a bit easier to understand than the ones I've seen online. It's not super rigorous, but I think it could be made so. To start with, the claim that you ask about can actually be made stronger and still be true. From Sedgewick and Wayne's Algorithms:

  when an h-sorted array is k-sorted, it remains h-sorted

That is, we don't even need to assume that $k$ is less than $h$. Now, what does it mean that the array is $h$-sorted? Let us first define:

An $h$-inversion of two elements $x_i$ and $x_j$, where $i < j$, is an inversion $inv(x_i,x_j)$ for which $j-i=h$.

Here, $i$ and $j$ are indices. Simply put, an $h$-inversion is an inversion between elements that are $h$ indices apart in the array. Then we can define:

An $h$-sorted array is an array with no $h$-inversions.

If we accept these definitions, we only need to show that $k$-sorting the array does not increase the number of $h$-inversions. We will do so by looking at what might happen when we swap two elements $x_i$ and $x_{i+k}$ during a $k$-sort. But first, let's adopt the following notation:

Let $x_i|$ and $x_{i+k}|$ denote the elements with index $i$ and $i+k$ before the swap, while $|x_i$ and $|x_{i+k}$ denotes the elements with index $i$ and $i+k$ after the swap.

Then, because we only swap the elements $x_i$ and $x_{i+k}$ if $x_i > x_{i+k}$, we have

$ |x_{i+k} = x_i| > x_{i+k}| = |x_i$.

The equalities are obvious because the left hand and right hand sides really refer to the same element, before and after the swap. The notable thing is the inequality, which we will be using soon.

To keep things easy to visualize, let us look at two elements that are to the right of both $x_i$ and $x_{i+k}$. More specifically, the elements $x_{i+h}$ and $x_{i+k+h}$, with $h>k$.

$$
\left\{\ldots, x_i, \ldots, x_{i+k}, \ldots, x_{i+h}, \ldots, x_{i+k+h}, \ldots\right\}
$$

Since the array starts out $h$-sorted, we have

$x_i| < x_{i+h}$ , and
$x_{i+k}| < x_{i+k+h}$.

After the swap we have,

$|x_i < x_{i+h}$, because $|x_i < x_i|$, as established previously. Thus, no new inversion has been introduced involving indexes $i$ and $i+h$.

And for $x_{i+k}$ and $x_{i+k+h}$ we have either

$|x_{i+k} < x_{i+k+h}$, in which case no new inversion is introduced involving indexes $i+k$ and $i+k+h$,

or, and this is key,

$|x_{i+k} > x_{i+k+h}$, in which case a new $h$-inversion $inv(x_{i+k},x_{i+k+h})$ has been introduced. However, since $x_{i+k+h} < |x_{i+k} = x_i| < x_{i+h}$ and $x_{i+k+h}$ is $k$ positions to the right of $x_{i+h}$, we know that $x_{i+h}$ and $x_{i+k+h}$ will be swapped later in the $k$-sort, eliminating the $h$-inversion.

Thus, after the full $k$-sort, any such $h$-inversions introduced by the sort will have also been resolved by the sort.

We have only specifically looked at elements to the right of both $x_i$ and $x_{i+k}$, but very similar arguments can be made for elements to the left of both, or even with one element sitting in between (when $h<k$). I won't go into those cases here however, because this is already a long post.


How many random walks to start from each node? Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of neighbors).

A random walk ends when it returns to the initial node or when the walk takes 3 steps.
If we start random walks from each node on this graph, should we start equal number of walks from each node? If so, nodes with small degrees will often return to where they started, and we will not learn big portions of the network. This is because small degree nodes are neighbors of small degree nodes more often, so there will not be many paths to walk on.

I believe there should be a way to decide on the number of walks to minimize computational costs.

If you consider given graph as a Markov chain, you can compute the steady-state distribution. With it, you can compute the mean-reccurence time $M_j$ (expected time to return to the starting node). See Mean recurrence time

$\pi_j=1/M_j$

If for some node $n_j$, the probability of going to each neighbour is equal to $1/out\_deg(n_j)$, then you can compute $\pi_j$ in constant time.

This does not assume, you stop after three steps (why do you actually need this?). From here you could do some experiments with damping factor $d$. Damping factor $d$ is the probability you end the walk at each step. Damping factor You can combine these two aproaches to get to your estimate.

-edit-

So here goes. Given an undirected graph $G=(V,E)$ you can find the stationary distribution of the corresponding Markov chain $M$ with transition matrix $P$ as follows:

$\pi_i=deg(v_i)/|E|$

where $deg(v_i)$ is the degree of vertex $i$, $|E|$ is the number of all edges in graph $G$ and $\pi_i$ is the $i$-th component of vector that satisfies:

$\lim_{k->\infty} P^k=1\pi$

Note that $\pi$ is unique if the Markov chain is irreducible and aperiodic.

Irreducibility essentially means, you can get from every vertex $i$ to every vertex $j$. If the graph is not connected, you can use the same approach on the connected components of the graph.
Aperiodicity means that greatest common divisor of cylce lengths in the Markov chain. This means that if you have at least one paper which was written by three authors (in one component), the condition is trivially satisfied.

Mean recurrence time is the computed by the formula above.


What are the basics of CS i should know,before I start my journey into machine learning I am myself a non-cs graduate and would love to be a machine learning engineer.

I have learned to code and know the basics of Machine learning as well. Now I would like to know what "basics of CS" I should learn to be completely job ready.

I sometimes have difficulties reading CS documentations and don't know how programs and computers work in background, I am also naiver on topics like memory management, operating systems, networking, electronics stuff like microprocessor, compiler design etc. Are these all necessary for my transition to AI? If they are, would you please recommend me a short learning path or books or videos. I hope I wouldn't need to go deep in these areas. Thanks

Computer science is a very broad subject area, and many of its sub-disciplines have little or no overlap with others. For example, knowing the basics of operating systems design, compiler design or microprocessor design are unlikely to help you make progress in machine learning (although each one is an interesting topic in its own right).

Machine learning is a sub-topic of artificial intelligence, so the most closely related disciplines are other sub-topics of artificial intelligence such as pattern recognition, data mining, knowledge representation and natural language processing. Some knowledge of the theory of data structures and algorithms would also be useful. Outside of computer science itself, you will also need some knowledge of mathematical topics such as probability, statistics and mathematical optimisation.


What is wrong with this conditional proof of P=NP? I have recently thought up the following proof that L=P implies P=NP.

  Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL. But then NL is contained in P, which means that NP is contained in P and therefore P=NP.

By the efficient market hypothesis, I suspect this proof is flawed. I am however unable to determine the exact nature of the error. Can someone point it out?

Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL.

You haven't shown that NP$\,=\,$NL. The only method you've derived to show that $x\in A$, is to nondeterministically "guess" a witness $y$ and use the deterministic logspace algorithm to verify it. However, $y$ itself may be polynomially long, whereas your NL machine can only guess logarithmically many bits: your NL machine doesn't have enough space to store the witness, so you don't have an NL algorithm.

Also, note that we already know that witnesses to NP-complete problems can be verified in a complexity class smaller than L. Fagin's theorem says that NP is exactly the set of problems that can be defined in the existential fragment of second-order logic. This is equivalent to saying that you can verify a polynomial-length witness using first-order logic. FO is strictly weaker than L, since first-order logic can't solve simple logspace problems like telling you if your witness string contains an even number of $1$s.


Is (a+b)* and (ab)* same in finite automata? Regular language of (a+b)* and (ab)* are:
(a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...}
(ab)* =   { ε, a, b, aa, ab, ba, bb, aaa, ... }

I am new to Finite automata and this simple notion is confusing me!
I didn't find (a+b)* = (ab)* in rules of regular expressions.

The regular expressions $(a+b)^*$ and $(ab)^*$ represent languages according to the semantics of regular expressions. Formally, the language $L[r]$ corresponding to a regular expression $r$ is defined as follows:

$L[\emptyset] = \emptyset$.
$L[\epsilon] = \epsilon$.
$L[\sigma] = \sigma$ for $\sigma \in \Sigma$.
$L[r_1+r_2] = L[r_1] \cup L[r_2]$.
$L[r_1r_2] = L[r_1] L[r_2]$, where $L_1 L_2 = \{ w_1w_2 : w_1 \in L_1, w_2 \in L_2 \}$.
$L[r^*] = L[r]^*$, where $L^* = \bigcup_{n \geq 0} L^n$, and $L^n$ is defined recursively by $L^0 = \{\epsilon\}$ and $L^{n+1} = L^n L$.

Two languages over the same alphabet are equal if they are equal as sets, that is, if they contain the same words. In your case, you haven't specified the underlying alphabet $\Sigma$, so I'm assuming that $\Sigma = \{a,b\}$.
Now that you have all the definitions, you can check for yourself whether $L[(a+b)^*]$ equals $L[(ab)^*]$.


Invertability of Karp reductions Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$.

I am interested in polynomial-time invertability of Karp reductions between natural NP-complete problems.

  Is it true that every Karp reduction $f$ is also polynomial-time invertible (i.e. $f^{-1}$ is polynomial-time computable)?

To clarify, Is there a Karp reduction $f$ between two natural NP-complete problems where its inverse $f^{-1}$ is not known to be polynomial-time computable?

Natural problem means that the problem is not an artificially made up problem to answer the question (or similar ones) and people are interested in the problem independently (defined by Kaveh).

P.S. It is known that all known Karp reductions between natural NP-complete problems are injective (or can easily made injective).

YES if $\mathrm{P}\neq \mathrm{NP}$ and the $3$-$\mathrm{SAT}$ problem satisfies your requirement (when being reduced to other complete ones). In short, this is the equivalent statement of your conjecture.

Unconditionally, every $\mathrm{NP}$ problem not necessarily complete can be reduced to $3$-$\mathrm{SAT}$ by a reduction $f$ which is poly-time invertible. And composition $f \circ g$ of efficiently invertible $f$ and $g$ is also efficiently invertible. Therefore, if somehow we prove that $3$-$\mathrm{SAT}$ problem satisfies your requirement (when being reduced to other complete ones), then your conjecture holds.

When reducing to $3$-$\mathrm{SAT}$, simply append dummy clauses to the $3$-$\mathrm{SAT}$ instance. These dummy clauses just encodes the original instance. And of course, these are trivially satisfiable with brand-new dummy variables.

For example: suppose $x=x_1x_2\dots x_n$ is the original instance and your $3$-$\mathrm{SAT}$ instance already has $k$ variables, do the following:

for each original bit $x_i$:

if $x_i=0$, add dummy clause $x_{k+1}\lor \lnot x_{k+1}$ if $k+1$ is even, otherwise add dummy clause $x_{k+2}\lor \lnot x_{k+2}$
if $x_i=1$, add dummy clause $x_{k+1}\lor \lnot x_{k+1}$ if $k+1$ is odd, otherwise add dummy clause $x_{k+2}\lor \lnot x_{k+2}$
$k$ := $k + 1$

NO if $\mathrm{P} = \mathrm{NP}$. This is because if so, a sparse language can be $\mathrm{NP}$-complete rendering hopeless a poly-time injective reduction (from a non-spare language to it).
Your conjecture is impied by the much stronger isomorphism conjecture. That is why many attempts to partially resolve that conjecture (e.g. by deduce it from weaker statements like yours) all fail up to now.


Why can't edit distance be solved as L1 distance? Given two strings $x$ and $y$ over the alphabet $\Sigma$ one defines the edit-distance $\text{ed}(x,y)$ as the minimum number of substitutions, insertions and deletions of characters required to transform $x$ into $y$.

If $m = \max ( \text{len}(x),\text{len}(y) )$ then padding with appropriate zeroes on the smaller string one can define $x$ and $y$ as both being elements of $\Sigma^m$. Now both $x$ and $y$ are vertices of the cube $\Sigma^m$.

Now isn't $\text{ed}(x,y)$ the shortest distance between $x$ and $y$ in this cube graph? Why isn't edit distance found by finding shortest paths in this cube?

Consider the two strings 01010101 and 10101010. They have distance 8 on the cube but their edit distance is 2.


Mapping spherical coordinates onto faces of an icosahedron I'm looking for an algorithm which takes spherical coordinates (say lat-long) and identifies which face of an icosahedron a ray moving in that direction would intersect.
My end goal here is to explore various cartographic map projections from a sphere onto an icosahedron (ex: Gnomic, Fuller Dymaxion, Snyder equal-area). All of these begin with the problem of identifying which face of the icosahedron a given coordinate belongs to and then mapping a standardized spherical triangle onto a standardized flat triangle.

The approach in your comment certainly works, and is probably your best bet.
If you think of the Platonic solid centred at the origin, then the coordinates of a a point located at the centre of each face is equal (up to normalisation) to those of a vector normal to the face. So you can, in principle, take a point on the sphere, search all the faces and find the face/normal whose dot product with the coordinates of the point is greatest.
This is surprisingly efficient on modern hardware, because it can use vector instructions effectively.
Do be careful about the fact that the Earth is not spherical. I don't know how these cartographic map projections deal with this (it may not matter with paper maps), but I imagine you would use the normal to the ellipsoid rather than the coordinates of the point on the ellipsoid.
Interestingly, mapping a normal vector to an octahedron is a particularly interesting case because an octahedron can be unfolded into a square. This is such an important problem that there are even survey papers on the topic.


Psuedorandom Generator Classification There are several pseudorandom number generators that we have no known polynomial time algorithms for inverting (finding the initial seed). Is it correct to say that inverting these generators is an NP problem?

NP contains decision problems. Problems with a yes or no answer. Finding $x$ such that $g(x) = y$ for some given pseudo-random generator $g$ and output $y$ isn't a decision problem. It's a function problem.
You can turn this into decision problem by asking whether the $i$'th bit of $x$ is 1 instead. Then you can still find $x$ by just asking this question once for every bit.
Now this problem of deciding on the $i$'th bit is trivially in NP. Speaking informally, every problem that has efficiently verifiable proofs is in NP. $x$ is just such a proof. You can quickly check it's $i$'th bit. And you can quickly check that $g(x) = y$.


Carry-free multiplication operation In long-multiplication, you shift and add, once for each $1$ bit in the lower number.

Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication, the addition does not carry. Essentially you bitwise-xor the shifted numbers.

Like so:

$$
  \left[\begin{matrix}
    &&p_n & ... & p_i & ... & p_2 & p_1 \\
    &&q_n & ... & q_i & ... & q_2 & q_1 & \otimes\\
    \hline\\
    &&q_1 \cdot p_n & ... & q_1 \cdot p_i
      & ... & q_1 \cdot p_2 & q_1 \cdot p_1\\
    &q_2 \cdot p_n & ... & q_2 \cdot p_i
      & ... & q_2 \cdot p_2 & q_2 \cdot p_1\\
    &&&&&&&...\\
    q_i \cdot p_n & ... & q_i \cdot p_i
      & ... & q_i \cdot p_2 & q_i \cdot p_1 & \stackrel{i}{\leftarrow}
      &&{\Huge{\oplus}} \\
    \hline \\
    \\r_{2n}& ... & r_i
      & ... &r_4& r_3 & r_2 &r_1 & =
  \end{matrix}
  \right]
$$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.

Followup: Shift-and-or multiplication operation

Your operation is multiplication of polynomials over $GF(2)$, i.e., multiplication in the polynomial ring $GF(2)[x]$.

For instance, if $p=101$ and $q=1101$, you can represent them as $p(x)=x^2+1$, $q(x)=x^3+x^2+1$, and their product as polynomials is $p(x) \times q(x) = x^5+x^4+x^3+1$, so $p \otimes q = 111001$.

If $p,q$ are $r$ bits long, this polynomial multiplication operation can be computed in $O(r \lg r)$ time using FFT techniques, but in practice this may not be a win unless your polynomial is extremely large. There is also a Karatsuba-style algorithm, whose complexity is something like $O(r^{1.6})$, as well as other options.  The situation is somewhat analogous to integer multiplication, in that many of the same fast algorithms can be applied, but not identical.

See, e.g.,

Wikipedia on Fast multiplication algorithms for large inputs.  These methods are described in terms of multiplying two integers, but they can be transposed to apply to polynomial multiplication.
Polynomial Multiplication, Karatsuba and Fast Fourier Transform
When is FFT multiplication of arbitrary-precision polynomials practical?.  Richard Fateman, March 14, 2006.
Can you save time in multiplying polynomials by encoding them as integers?.  Richard Fateman, January 15, 2005.


When can we assuredly say that a function is little o of some other function? I'm trying to determine a function $f(x)$ that is $O(f)$ but not $o(f)$ and also not $\Omega(f)$. Note the $f$ used in the asymptotic notation is not the same as $f(x)$.

Originally I thought of $f(x)=\log(x), O(x)$ but I am not convinced that $o(x)$ is invalid for this function.

Previously I thought it was, because I could always come up with some constant $c$ that would bring the function $x$ below $f(x)$. However, I could say the same for $o(2^x)$ because surely there is some infinitesimally small constant that I can find that will put $2^x$ below $f(x)$ at a given value $x$. Any advice in this matter?

Your example doesn't work, since in fact $\log x = o(x)$. However, the function $\phi$ below is $O(x)$ but not $o(x)$ or $\Omega(x)$:
$$
\phi(x) = \begin{cases} x & \text{if $\lfloor x \rfloor$ is even}, \\ 1 & \text{if $\lfloor x \rfloor$ is odd}. \end{cases}
$$


Hungarian Assignment Algorithm Implementation I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows:

S(0) <- appropriately sized matrix filled with 1's
for k=1 to 10 do:
    S(k) = Y*S(k-1)*X^T + Y^T*S(k-1)*X
    k++
Apply Hungarian assignment algorithm on similarity matrix S.

where X^T means the transpose of the matrix X.

Basically, given two graphs G1, G2 (not necessarily the same # of vertices), create their adjacency matrices X and Y. Then, do this iterative process 10 times, and then apply the Hungarian assignment algorithm. The result would be a similarity matrix where entry (i,j) represents a real number between 0 and 1 that gives how "similar" vertex i is of G1 to vertex j of G2.

My question is: how would this algorithm be implemented? I looked up the algorithm on Wikipedia, and the explanation seems as though all entries in S would be integers, but what is expected is real numbers between 0 and 1.

The article you linked assumes that the reader knows how to apply the Hungarian algorithm on a similarity matrix because they have note in the introduction to Section 3 that Zager et. al. used the Hungarian algorithm for this purpose in the paper here.

Furthermore, there is no requirement in the Hungarian algorithm that necessitates integral entries; neither the Wikipedia article and this slide deck mention any requirement for the entries to be integers.  Authors may use integer values for examples because they're easy to work with, but that does not mean the algorithm requires them.


How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time? The real problem I am facing is the following.

INSTANCE: I have sets $N:=\{1,\ldots,n\}$ and $K:=\{1,\ldots,k\}$ and matrix $a_{ij}>0$ for all $i\in K$ and $j\in N$.

QUESTION: I need to find a subset $S$ of $N$ of size as small as possible and partition the set $K$ into $|S|$ disjoint sets $K_j$ whose union equals $K$ such that for all $j\in S$, I have $$\sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,$$ for all $i\in K_j$.

Example:

Given $n=k=3$ and the matrix
$$
\begin{bmatrix}
0.6 & 2.7 & 1.2\\
1.3 & 2.6 & 0.8\\
1.5 & 0.4 & 0.6
\end{bmatrix}.
$$

In this example, $S$ should be equal to $S=\{1, 2\}$ and $K_1=\{3\}$ and $K_2=\{1,2\}$.

I noticed two facts:

If there exists some $j\in N$ such that $a_{ij}\geqslant 1$ for all $i\in K$ then $S=\{j\}$ and $K_j=K$; and
If there exists some $i\in K$ such that $a_{ij}<1$ then $S=\emptyset$.

My question:
Is it possible to solve this optimization problem in polynomial time (at least with approximation algorithm)?

The first thing I tried to do is to transform it into a known problem and then applied a known algorithm for that. I thought about transforming it to a set cover or bin packing but I failed and also I do not think that this is interesting.

The problem I tried to formulate.

I have sets $N:=\{1,\ldots,n\}$ and $K:=\{1,\ldots,k\}$ and matrix $a_{ij}>0$ for all $i\in K$ and $j\in N$. Also, I have $n$ disjoints  sets $K_j\subset K$ for each $j\in N$, (I added $K_j$ as inputs because I could not formulate it otherwise.)

Finally, I get this:
$$
    \begin{align*}
      & {\underset{S}{\text{minimize}}}
      & & |S|\\[3pt]
      & \text{subject to}
      & & \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in
S,i\in K_j,\\[3pt]
      & & & S\subseteq N.\\
    \end{align*}
$$

Thanks.

Even the decision version of this problem, in which we try to determine simply if there exists any feasible solution, is NP-hard by reduction from Exact Cover.  (The optimisation version, where we seek a feasible solution that minimises $|S|$, is clearly at least as hard as this.)

The single-row, single-column matrix containing the value 0.5 is an example of an input for which there is no feasible solution.  Here's another:

$$
\begin{bmatrix}
0.2 & 4\\
3.1 & 3\\
5 & 0.6
\end{bmatrix}.
$$

Building a "Choose at most one" gadget

First, notice that if the maximum value in some row $a_i$ is $x > 0$, and this row contains (at least) two copies of $x$, say at $a_{ij}$ and $a_{ij'}$, $j' \ne j$, then $S$ cannot contain both $j$ and $j'$, since if it did then one of the following two cases must arise, each of which leads to a contradiction:

$i \in K_j \cup K_{j'}$: Suppose w.l.o.g. that $i \in K_j$.  But then $\Sigma_{m \in S, m \ne j}{a_{im}} \ge a_{ij'} = x = a_{ij}$, contradicting the requirement that $\Sigma_{m \in S, m \ne j}{a_{im}} \le a_{ij} - 1$.
$i \notin K_j \cup K_{j'}$: Then suppose $i \in K_p, p \notin \{j, j'\}$.  But then $\Sigma_{m \in S, m \ne p}{a_{im}} \ge a_{ij} + a_{ij'} = 2x$, and since $x$ is maximal in row $i$, the highest that $a_{ip}$ could be is clearly $x$, so we must be violating the same inequality as before.

Thus we can choose some maximum value that is safely higher than the sum of all non-maximum values in the row, and use copies of this maximum value to enforce that at most one of those columns is included in $S$.

We can turn this "choose at most one" constraint into a "choose exactly one" constraint by using any positive value less than 1 as the "non-maximum" value.  That's because every row $i$ belongs to some part $K_j$ of the row partition, and if $a_{ij} < 1$ then the RHS of the inequality becomes negative for row $i$, so there is no way to satisfy it: thus at least one $j$ must be forced into $S$ such that $a_{ij} \ge 1$.

So, to ensure that exactly one of the columns in some set $T \subseteq N$ is forced into $S$, create a row $a_i$ as follows:

Set $a_{ij} = n+1$ for each $j \in T$.
Set $a_{ij} = 0.5$ for every other $j$.

Thus the reduction from Exact Cover is straightforward: there is a row for each element, a column for each set, with $a_{ij} = n+1$ whenever set $j$ includes element $i$ and $a_{ij} = 0.5$ otherwise.  Both directions ("Input EC instance is a YES-instance $\implies$ constructed instance of OP's problem is a YES-instance", and "Constructed instance of OP's problem is a YES-instance $\implies$ input EC instance is a YES-instance") are clear.


Minimum area of tarp to cover a carpet This problem takes place on a coordinate plane. I need assistance in creating the algorithm to solve this problem. I am solving this problem in java if you are interested.
I have 1 carpet and 2 tarps.
The 1 tarp covers the carpet (note in some scenarios it may not cover it at all).
The second tarp will cover the remaining area of the carpet, however, this is where it gets tricky. The tarp cannot be a special shape or tilted, meaning the tarp HAS to be rectangular. I am given the inputs of the lower left and top right corners of both the 1st tarp and the carpet. As of now, I have calculated the visible area of the carpet after the first tarp has been placed, the overlapping (non-visible) area of the tarp, and the areas of both the carpet and 1st tarp.
So basically what I am saying is, given a rectangle C (the carpet) that intersects the rectangle T1 (tarp 1), find another rectangle T2T2 (tarp 2) such that the area of T2T2 is minimal.
Below is a picture of some test cases I drew up:

*Excuse my messy handwriting

Cutting to the chase, what I need is help with is developing an algorithm that would satisfy all of the above test cases, given the lower left and top right coordinates of both the first tarp and carpet. Note I am going to be writing this in Java and I currently have an area function and visible area of the carpet function.

Sorry if I was a little unclear on what I am asking, leave a comment and I'll be happy to clarify.
 Note: this is not a homework problem, as many of you may think. This is merely an interesting scenario of another programming problem I had.

To solve this, consider what happens when exactly $k$ corners of $C$ lie inside $T_1$, for $k\in \{0,1,2,3,4\}$, where $C\setminus T_1$ denotes the area of $C$ not covered by $T_1$:

If $0$ corners of $C$ lie in $T_1$, then $T_1$ doesn't cover any corner of $C$. So any rectangle covering $C\setminus T_1$ must cover all corners of $C$, so the smallest of these rectangles is $C$ itself.
If exactly $1$ corner of $C$ lies in $T_1$, the $C\setminus T_1$ contains $3$ corners of $C$ and the smallest rectangle covering this area is again $C$ itself.
If exactly $2$ corners of $C$ lie in $T_1$, then $C\setminus T_1$ is a rectangle, so the smallest rectangle covering it is itself. More precisely, this is the rectangle with as corners the two intersection points of the edges of $C$ and $T_1$ and the two corners of $C$ not covered by $T_1$.
If $3$ corners of $C$ lie in $T_1$, then $4$ corners of $C$ lie in $T_1$, so $k$ cannot be $3$.
If $4$ corners of $C$ lie inside $T_1$, then $C$ is fully covered by $T_1$, so the smallest rectangle covering the remainder has area $0$.

So, to determine the size of the smallest rectangle covering $C\setminus T_1$, we simply count the number of corners of $C$ inside $T_1$, apply the proper case and we're done.


Understanding the definition of endless sets In a course on theoretical computer science we have to prove if sets are endless. I have two problems with the exercise:

I don't understand exactly, what an endless set is (I find it very hard to understand, maybe because of the "endless")
I don't know, how I can prove that the given sets are endless

The definition given is this:

  A set $X$ is called endless set, if there is a endless family of sets $\{X_n\}_{n=0}^{\infty}$ with
  $... \in X_3 \in X_2 \in X_1 \in X_0 \in X$.

Can someone explain in simple words what an endless set is?

Defining endless sets, you probably assume that you don't have the Axiom of regularity.

A set is endless when it doesn't contain only simple elements, it has to contain an other set among his elements, and this other set has again to contain an other set and this third set has to contain an other set, etc..

For example, a set verifying $M = \{M\}$ is endless because it contains an other set ($M$) which contains an other set (still $M$) which contains an other set ($M$), etc.. You can take $X=X_0= X_1= ... = M$ as infinite family.

A counter example is $M = \{42\}$; $M$ doesn't contain any set. $M= \{42, \{12\}\}$ is also a counter example because $M$ contains a set ($\{12\}$) but this set doesn't contain any set.


NFA to accept strings where the third AND the third-last element are b Alphabet is {a,b}, the third element from the start must be "b" (e.g: aab..., abb...) and the third-last element must also be "b" (e.g: ...baa, ...bbb). I can do them separately but at the same time I don't know where to start. Help please.

Hint. If $A$ is the alphabet, a regular expression for your language is $AAbA^*bAA \cup AAbAA \cup AbbA \cup bAb$.


Regular expression for string with substring 010 and ending with 01 How can one design a regular expression for given string in title ?

Also how can we draw DFA of that regular expression?

I've tried many expressions but couldn't succeed, please help.

The regular expression would be like $(0 + 1)^*010(0 + 1)^*01 + (0 + 1)^*0101$.
Transformation of a regular expression to a DFA has a well-defined algorihtms, and you can find them in the resources.


Algorithm to extract the subgraph of all nodes with degree at least four I have an undirected graph represented by a list of nodes and a list of edges. What I need to produce from this is a list of nodes and edges representing a new graph containing only the nodes which have degree of at least 4. I think I've developed an algorithm. It uses an object called Node, which can store an integer for the degree of the node and a list of that node's neighboring nodes.

For each node in the graph create a Node object in $O(|V|)$ time and store in a list.
Traverse the list of edges in $O(|E|)$ time. While doing so update my list of nodes with their appropriate degree and neighbors.
Search the list in $O(|V|)$ time and find the node with smallest degree. If >4, return. If <4, visit the node's neighbors, reduce their degrees by one, and remove this node from their list of neighbors. Then remove this node from the graph, in worst case $O(|V|)$ time.
Repeat step 3. At worst $O(|V|)$ times.

If anyone is wondering, I'm doing this for a Civilization-esque game I'm making. I want to be able to separate cities that are part of major trade routes from minor ones.

Now, I think this algorithm is correct, but I'm not happy with its running time. If I'm not mistaken, it's $O(|V|^2)$, correct? Is there a way to make this more efficient?

The object you are trying to find is known in graph theory as the 4-core. Batagelj and Zaveršnik give a simple linear time algorithm for finding the $k$-core for any given $k$.


Assumptions when selecting an algorithm or data structure As I understand it the nature of data access (sequential or random) will determine the optimal algorithm/data structure to use when manipulating data.

What other assumptions need to be checked before selecting an algorithm or data structure for the manipulation of data?

You can categorize data structures by their need of memory or processing power. Each rated for writing or reading purpose. Some data structures are optimized for searching, some only for fast storing.

Ask yourself how many data you're going to store.
If it's a lot, you have to choose the right algorithm, if not it doesn't really matter.

Another question could be, do you need a growing data structure or just a ring buffer for example.

Regarding data manipulation with algorithms, there is a bunch of considerations to make.
With growing data, how much does memory usage, processing power, external storage capacity and access times grow?
The big O notation would be a term to refer to.
Here too, it's important if your 'manipulation' is reading, searching or writing?

You will find an algorithm or a data structure out there for every use case.


Quotient of languages, regular quotient and their closedness Left quotient is defined as below at this link:

Left quotient of $L1$ by $L2$:
$L1\backslash L2:= \{u\in \Sigma^*|vu\in L1$ for some $v\in L2 \}$

Wikipedia defines it as follows:

$L_1\backslash L_2=\{w|\exists x((x\in L_1)\wedge (xw\in L_2))\}$

Q1. I feel both definitions differ. Which one is correct?
Also first link says:

It can be shown that the families of regular, context-free, and type-0 languages are closed under quotient (both left and right) by a regular language. The family of context-sensitive languages does not have this closure property.

whereas wikipedia says:

The quotient of a regular language with any other language is regular.

Q2. I again feel both differ especially in case of regular quotient with CSL. Which one is correct?

All sources agree on the definition of right quotient: $L_1/L_2$ is the set of words which can be extended by a word in $L_2$ to become a word in $L_1$. In other words, $w \in L_1/L_2$ if there exists $x \in L_2$ such that $wx \in L_1$.

If $L_1$ is regular and $L_2$ is any language then $L_1/L_2$ is regular.

For many classes of languages, if $L_1$ belongs to the class and $L_2$ is regular then $L_1/L_2$ also belongs to the class. Examples of such classes include context-free languages and r.e. languages, but not context-sensitive languages. This is definitely the case for languages closed under homomorphism, inverse homomorphism, and intersection with a regular languages. Context-sensitive languages are only closed under $\epsilon$-free homomorphism, which is not enough here.

The left quotient is defined similarly, but we extend the word on the left instead of on the right. The notation is $L_1\backslash L_2$, but authors vary on which part is played by which language. One possible convention (used by Wikipedia) is that we are interested in words which can be extended on the left by a word in $L_1$ to become a word in $L_2$. Another convention (used by your link) reverses the roles of $L_1,L_2$. The alternate notations $L_1 L_2^{-1}$ and $L_2^{-1} L_1$ mentioned in your link are unambiguous. Note how the Wikipedia notation makes a bit more sense here: $L_2^{-1} L_1 = L_2 \backslash L_1$ per the Wikipedia notation, but not per the notation in the link.


What does it mean to isolate a field in a word? I have been reading in the 'computer organization and design' book and I encountered this section:

what operations isolate a field in a word

I know that the answer is logic operations and shift instructions from the book but.
I want to know what does it even mean to isolate a field

Consider an 8-bit word whose contents can be described as follows:

Bits 0–2 encode some value $x$.
Bits 3–4 encode some value $y$.
Bits 5–7 encode some value $z$.

Each of these different values is known, in this context, as a field. You can think of it as a field in some form.

Isolating a field out of a word means extracting just the value of the field. For example, denoting the entire word $w$, here is how we can isolate each of the fields:

$x$: AND $w$ with the mask $7$ (which is $111$ in binary).
$y$: Right-shift $w$ by 3 positions, and AND the result with the mask $3$.
$z$: Right-shift $w$ by 5 positions.

In C, you could implement these as follows:

x = w & 7;
y = (w >> 3) & 3;
z = w >> 5;


finding all cyclic substrings of a string I have been stuck on this problem for a while now; any help would be appreciated.

Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For example, "abbccbbadad" has 3 because "bb" is composed of 2 "b"s, "cc" is composed of 3 "c"s, and "adad" is composed of 2 "ad"s.

My solution uses hashing and currently runs in n^2 time, which is fine because the length of the string is <= 5000. However, my program uses n^3 space. I am confident that a solution requiring n^2 space and n^2 time will pass. Is there a more efficient solution?

Any algorithm that runs in $O(n^2)$ time can access at most $O(n^2)$ different memory locations during the course of its execution.  Thus, if you replace memory with a hashtable (instead of accessing address $a$, access the hashtable at key $a$), you obtain an algorithm with expected running time $O(n^2)$ and space $O(n^2)$.  If you care about theoretical proofs, you can use a balanced binary search tree instead of a hashtable and obtain a worst-case time bound of $O(n^2 \log n)$ time and $O(n^2)$ space.


Can quantified renamable Horn formulas be identified using the same procedure as unquantified formulas? Definition: A renamable Horn formula is a Boolean formula that can be transformed into a Horn formula by flipping the polarity of every instance of one of more of its variables.

Example:

$\qquad (x_1 \lor x_2 \lor x_3)\land (\lnot x_1 \lor \lnot x_2 \lor  x_3)$

This formula is renamable Horn because flipping the polarity of $x_2$ and $x_3$ produces the Horn formula

$\qquad (x_1 \lor \lnot x_2 \lor \lnot x_3)\land (\lnot x_1 \lor x_2 \lor \lnot x_3)$

Can I extend the test procedure for identifying renamable Horn formulas, as described in the Harry Lewis paper "Renaming a Set of Clauses as a Horn Set", to quantified formulas?

The paper states: Let $S$ be a set of clauses, say $S = (C_1 ..... C_m)$, where each $C_i = (L_{i1} .... , L_{il})$. Then
define $S^*$ to be the set of clauses

$\qquad \bigcup_{i=1}^m \bigcup_{1\leq j <k\leq l} ((L_{ij}, L_{ik}))$.

Then $S$ is renamable-Horn if and only if $S^*$ is satisfiable.

Is this procedure applicable to quantified Boolean formulas also?

Yes.  The quantifiers can be ignored for the sake of the test since a quantified Horn formula is syntactically identical to an unquantified one except for the quantifiers.  That is, a quantified Horn formula still consists of only of clauses with zero or one positive literals.  The test only determines whether any combination of polarity flips could produce a Horn formula.

In order for the test to be useful for quantified formulas, it only remains to show that a quantified formula can be renamed and remain equisatisfiable with the original formula.

For unquantified formulas renaming a variable leaves satisfiability unchanged because a solution to the renamed formula is the same as a solution to the original formula except that the renamed variable has its value negated in compensation for the polarity change.  The same is true for existentially quantified variables in a quantified formula, and for the same reason.  For universally quantified variables, observe that the universal quantifier already requires satisfiability to survive a polarity flip because any solution has to encompass both true and false values for any universally quantified variable.  That is, $\forall x(x)$ and $\forall x(\lnot x)$ offer the same solution constraint; the clause must be satisfied with $x$ taking both the true and false values.


Color coding to get an FPT algoirthm for k disjoint triangles The k-disjoint triangles problem is as follows:

Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
Output: Are there $k$ vertex-disjoint triangles in $G$?

An FPT algorithm is presented here
(starting from slide 60). The algorithm uses color-coding and relies on dynamic programming to determine if a solution is highlighted (each vertex in the solution group is colored with a distinct color). The running time of the algorithm is $O^∗((2e)^{3k})$.
I`m trying to understand the running time of this algorithm using dynamic programming (method 2). why is it   $O^∗((2e)^{3k})$?

The dynamic programming algorithm goes over all subsets of $[3k]$ whose size is a multiple of 3, in nondecreasing order of size. For each such non-empty subset, it goes over all $O(n^3)$ triplets of vertices, and for each one, it performs a single table look-up. Therefore the running time is $O^*(2^{3k} n^3)$, where $O^*$ hides $\operatorname{poly}(k)$ factors which are needed to manipulate indices.


How to bound a running time equation? I simply need a standard way to find the upper and lower bound of a running time equation (please no shortcuts that only work for this specific problem)....

Example: $T(n)=\frac{c}{5}(4^{\left \lfloor \log_{4} (2n^{2}) \right \rfloor +1}-1)$

I think I understand how to put it in $\Theta$, $\Omega$, and $O$ after I get the bounds....  But I can't figure out a standard way to find the bounds for the running time of an algorithm (it's all unrelated or obscure shortcuts) for any given formula.  Any help out there?

EDIT: Apparently it might be thought I am asking for a specific number for each bound.  I am not, I'm looking for how to find the equation that the bound gives....  For instance, on a problem (not this one), a bound might be $3^\frac{\ln a}{\ln n}+1$ for a certain bound....  The actual problem says to show your work putting the equation into $\Theta$ by bounding it on the upper and lower bounds.  I need to know how to show work for that on this and similar problems.  Make more sense?

Every function is big $\Theta,\Omega,O$ of itself, so you can already put your result in big $\Theta,\Omega,O$ notation. Using $4^{\log_4 (2n^2)} = 2n^2 = \Theta(n^2)$, you can also write $T(n) = \Theta(n^2)$; I'll leave you the details.