Random file access in a block based file format I am writing a program to store, retrieve and delete "blocks" of data of varying sizes.

The way it currently works is by keeping a database storing the locations of the blocks and the locations of free space in the file.

The file is split into pages such that in each page there are no two free chunk spaces next to each other (During a delete operation, any free chunks which are adjacent are merged into one bigger chunk)

The problem with this is that I am seeing horrible IO performance when removing a bunch of blocks and inserting new ones of different sizes (blocks range from 1k to about 200k and may be written anywhere in the file provided they fit in an existing free chunk in the file. If no such free chunk is found, a new page is created at the end of the file).

Can anyone suggest a way to improve on this, or maybe point me in the right direction?

A starting point for this would be the heap management algorithms, start perhaps here. I remember Knuth in his Art of Computer Programming has a detailed discussion, I believe in volume 1. The algorithms described are good for RAM, adding in the non-uniform access of rotating disks will be quite a challenge...

Isn't it much simpler to use a database and blobs? Your time is valuable too...


Asymptotics of a function that decreases as n increases A homework assignment asks me to state the complexity in Big-O notation of the function
$$f(n) =  7n – 3n \log n + 100000 $$

I graphed this function and decreases all the way down to zero nearly its entire lifespan.
Therefore I concluded that the complexity is bounded by a constant and has the complexity $O(1)$.

Is this correct?

Also out of curiosity, what is the Big-Omega of this function is? The best it could ever run is also O(1).
What about Big-Theta? I'm having trouble getting my head around these.

If you use suitable definitions, you'll find that your function is in

$O(2^n)$,
$O(n^4)$,
$o(1)$ and
$\Omega(-n^2)$,

among many others. It's likely that the question (implicitly) asks for sharper bounds; I'll leave that for you to figure out.


Time complexity of a triple-nested loop Please consider the following triple-nested loop:

for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

The statement here is executed exactly $n(n+1)(n+2)\over6$ times. Could someone please explain how this formula was obtained? Thank you.

You can count the number of times the innermost for loop is executed by counting
the number of triplets $(i,j,k)$ for which it is executed.

By the loop conditions we know that: $1 \leq i \leq j \leq k \leq n$ . We can reduce it to the following simple combinatorics problem.

Imagine $n+2$ boxes of red colour placed in an array from left to right.
Pick any 3 boxes from the $n+2$ boxes and paint them blue.
Form a triplet $(i,j,k)$ as follows:

$i$ = 1 + number of red coloured boxes to the left of first blue box.
$j$ = 1 + number of red coloured boxes to the left of second blue box.
$k$ = 1 + number of red coloured boxes to the left of third blue box.

So, we just need to count the number of ways of picking 3 boxes from $n+2$ boxes which is $n+2 \choose 3$.


Find largest and second largest elements of the array So here is a HW problem I have been working. On I was wondering if anybody could give me a hint of what I am doing wrong. I don't want to be given the answer just hints and advice on how to solve it.

I am given this simple algorithm that finds the greatest value and the second greatest value in a array.

  If A[1] < A[2],
        largest = A[2], Second = A[1]
    else
        largest = A[1], Second = A[2];
    For i in range 3 to n {
        If A[i] > largest {
         second = largest;
        largest = A[i];
        }
        else
            if A[i] > second
                second = A[i]
    }

My first task was to find the number of comparisons it makes not in big-oh terms. So I said 2n-3 because it has one in the beginning and worst case
the largest element is in the first two elements of the array A so from
index 3 to n it has two comparisons. So 1 + 2(n-2) = 2n - 3 comparisons.

My second task was to develop an algorithm that would use less comparisons. So I broke it down with divide and conquer and said this.

 // start is the first index inclusive
        // finish is the last index inclusive
        // A is an array of elements
        function getGreatestAndSecondGreatestValue(A, start, finish) {
            T[] // T is an array of size 2
            if(finish - start == 1) {
                if(A[start] > A[finish]) {
                    T[0] = A[start]
                    T[1] = A[finish]
                } else {
                    T[0] = A[finish]
                    T[1] = A[start]
                }
                return T
            }

            Array1 = getGreatestAndSecondGreatestValue(A,start, start + floor((last-first)/2))
            Array2 = getGreatestAndSecondGreatestValue(A, start + ceil((last-first)/2), finish)
            return merge(Array1, Array2);
            // The greast value will be in the 0th index of the array returned and the second
            // greatest value will be in the 1 index of the array.
        }

        // this merges two arrays keeping the greatest value on the left side of the new array and
        // keeping the second greatest value on the right side of the array
        function merge(Array1, Array2) {
            MergedArray[] // array that will hold the merged results
            if(Array1[0] > Array2[0]) {
                MergedArray[0] = Array1[0]
                MergedArray[1] = max(Array[1], Array2[0])
            } else {
                MergedArray[0] = Array2[0]
                MergedArray[1] = max(Array1[0], Array2[1])
            }
            return MergedArray
        }

For example this say we had the array

[1,4,5,2,7,9,10,19]

then is divides it

[1, 4, 5, 2] [7, 9, 10, 19]

then when it reaches a length 2 is places the highest value in index 0 for arrays the size 2

[4, 1] [5, 2] [9, 7] [19, 10]

I would then proceed to merge these

[5, 4] [19, 10]

[19, 10]

Then the greatest value is 19 and the second greatest was 10.

I then proceeded to find the number of comparisons with recurrences.

T(n) = 2T(n) + 2

There are n leaf nodes because $ 2^{log_{2}(n)} = n $ where $ log_{2}(n) $
is the height of the tree. There are then n - 1 internal nodes so n + n - 1 is 2n - 1. 2 is added to every node so then it would be 4n - 2.

For some reason after using a divide and conquer algorithm I am getting a higher number of comparisons and I am not sure why. Could somebody give me some advice on why this didn't work?

Here I present an optimal solution minimizing the number of comparisons.
The thing to take advantage of is the first step of the original algorithm:
if A[1] < A[2],
    largest = A[2], second = A[1]
else
    largest = A[1], second = A[2]

We can get the largest and second largest of sets of two in one comparison!
So the first thing we should do is divide our array into $n/2$ pairs of two. Namely:
$$p_1 = (a_1, a_2), p_2 = (a_3, a_4), \ldots, p_i = (a_{2i - 1}, a_{2i}), \ldots, p_{n/2} = (a_{n-1}, a_n)$$
For every pair $p_i$, we can determine it's largest and second largest value in one comparison. We'll call these $p_i.L$ and $p_i.S$ respectively. So it takes $n/2$ comparisons to determine all of thee values for every pair.
Let's call the overall largest and second largest elements $\mathbb{L}$ and $\mathbb{S}$ respectively. We know that $\mathbb{L}$ will be among the $\{p_i.L\}$'s because it will be the largest of these. We also know $\mathbb{S}$ will be among $\{p_i.L\} \setminus \mathbb{L}$ or it could be the second largest value in the pair that $\mathbb{L}$ came from.
An example: Let our original array be:
$$A = [1,4,5,2,7,9,10,19]$$
We then break it up into pairs:
$$P = [(1,4)(5,2)(7,9)(10,19)]$$
We then know $\mathbb{L}$ will be in:
$$W = \forall i.\; \{p_i.L\} = \{4, 5, 9, 19\}$$
So now we just need to find three values: $W.\mathbb{L}$ (this will be $A.\mathbb{L}$), $W.\mathbb{S}$ (this could potentially be $A.\mathbb{S}$) and $p_i.S$ where $p_i$ is the pair that $W.\mathbb{L}$ came from (this could also potentially be $A.\mathbb{S}$).
From our example we see $A.\mathbb{L} = W.\mathbb{L} = 19$. We then see $A.\mathbb{S}$ is either $W.\mathbb{S} = 9$ or $10$ (from the pair containing $W.\mathbb{L}$), and it is $10$.
So this turns our problem of $A$ into a subproblem of size $n/2$, $W$. Then we can run the original algorithm on this subproblem and do some extra comparisons to get $A.\mathbb{S}$ and this totals about $\approx 1.5n$ comparisons. But we can do better!
We use recursion on this subproblem instead of just using the original algorithm. So the algorithm looks like this, and will return the indices of the $A.\mathbb{L}$ and $A.\mathbb{S}$. (assume $n = 2^k$ and this is 1-indexed). The algorithm will modify the input array so we will assume $A$ to be a copy of the input.
L_and_S (array of length n):
  Let A = copy of input
  // base case
  if n == 2:
    if A[1] > A[2]:
      return (1, 2)
    else:
      return (2, 1)

  // recursive case
  Let W be new array length n/2 (keeps track of largest elements)
  Let M be new array length n/2 (keeps track of swaps)
  for i in 1 ... n/2:
    // swap larger element into first position of pair
    // set M[i] to 1 if pair was swapped, else 0
    // move larger element into W
    if A[2*i - 1] < A[2*i]:
      temp = A[2*i - 1]
      A[2*i - 1] = A[2*i]
      A[2*i] = temp
      M[i] = 1
    else:
      M[i] = 0
    W[i] = A[2*i - 1]

  // now recurse on W
  (j, k) = L_and_S(W)
  // map back from W to A
  j_swap = M[j]
  k_swap = M[k]
  j = 2*j - 1
  k = 2*k - 1
  if A[j + 1] > A[k]:
    k = j + 1
    k_swap = 0 - j_swap
  return (j + j_swap, k + k_swap) // account for the swap

We can run through the example above:
L_and_S([1,4,5,2,7,9,10,19]):
  // do n/2 comparisons
  A = [4,1,5,2,9,7,19,10]
  W = [4,5,9,19]
  M = [1,0,1,1]
  (j, k) = L_and_S([4,5,9,19]):
             // do n/4 comparisons
             A = [5,4,19,9]
             W = [5,19]
             M = [1,1]
             (j, k) = L_and_S([5,19]):
                        // do 1 comparison (5 > 19)
                        return (2,1)
             (j_swap, k_swap) = (1, 1)
             (j, k) = (3, 1)
             // do 1 comparison (9 > 5)
             k = 4
             k_swap = -1
             return (3 + 1, 4 - 1) = (4, 3)
  (j_swap, k_swap) = (1, 1)
  (j, k) = (7, 5)
  // do 1 comparison (10 > 9)
  k = 8
  k_swap = -1
  return (7 + 1, 8 - 1) = (8, 7)

We see overall this takes $n/2 + n/4 + 1 + 1 + 1 = 9 = n + 1$ comparisons! These are comparisons of the array elements, ignoring the base case comparison in the beginning.
The exact recurrence relation for number of comparisons is the following (assume $n = 2^k$):
$$\begin{align}
  T(2) & = 1\\
  T(n) & = T(\frac{n}{2}) + \frac{n}{2} + 1\\
  & = 1 + \sum_{1}^{\log_2 n - 1} \frac{n}{2^i} + 1\\
  & = \log_2 n + \sum_{1}^{\log_2 n - 1} \frac{n}{2^i}\\
  & = \log_2 n + n - 2\\
  & = n + \log_2 n - 2
\end{align}$$
So we get the total number of comparisons in the worst case is $n + \log_2 n - 2$, which is pretty good. In fact, this is a lower bound! (see here) If you include the base case comparison it adds another $\log_2 n$ to the comparisons. Here's a table for the first few $n$:
$$\begin{array}{|c|c|}
\hline n & n + \log_2 n - 2 & 2n - 3 \\
\hline 2 & 1 & 1 \\
\hline 4 & 4 & 5 \\
\hline 8 & 9 & 13 \\
\hline 16 & 18 & 29 \\
\hline 32 & 35 & 61 \\
\hline 64 & 68 & 125 \\
\hline 128 & 133 & 253 \\
\hline 256 & 262 & 509 \\
\hline 512 & 519 & 1021 \\
\hline 1024 & 1032 & 2045 \\
\hline
\end{array}$$

Implementation of the code in python can be found here, with test cases at the bottom.


Is there a meta text processing concept in CS? I understand that text processing could be done in various ways on top of operating systems:

Shell utilities for processing a file (and/or a file name): tr, sed, awk, perl, mv and others
text editors for processing a file (and/or or a file name): nano, Vim, Emacs and others; whether CLUI/TUI/GUI and whether for "plain" or "rich" text
Possible shell builtins: such as compgen to to generate auto-completion matches for specified commands and possibly others

I further understand that generally all of these programs can be empowered by what I can name "meta text processing" implementations such as regex and serialization (for example; JSON key-value pairs).

Is there a meta text processing concept in CS (and what might be a practical example besides regex and serialization)?

I am hoping to find theory regarding text processing, or computer data processing. I don't expect an answer such as "you could use YAML instead JSON".

You should look into Theory of Automata, Languages and Computation:
These are the theoretical foundations of scanning, parsing and processing text (and furthermore constructing formal languages and grammars).

Components of the theory, are, for example:

Pushdown automaton
Context free grammars
Parsing techniques such as recursive decent, LL or SLR parsing.

Classical introductory textbook on this subject is "Introduction To Automata Theory, Languages, and Computation" by John E. Hopcroft,Rajeev Motwani and Jeffrey D.Ullman.


What's the point of Indirect Addressing? Indirect addressing allows you to reference memory locations, larger than the operand limit of a CPU.

i.e

1 | ADD 2 3
2 | #2
3 | *32000
...
32000 | #5

This will add memory location 2 and 3, 3 points to location 32000, so when it's evaluated, the effect is:

1 | ADD 2 32000

Even though 32000 may exceed the operand size limit.

My question is, why do this?

Why not simple have this:

1 | ADD 2 3
2 | #2
3 | #5

It saves time wasted on extra references to memory and space in memory.

Indirect addressing is possible without instructions that implement it explicitly. These instructions exist for our convenience, and not just for reaching a position that doesn't fit the address space of a direct addressing instruction (although this will become quite natural if your program is big enough): that's how we implement subprograms and arrays, for instance.


Buses in a processor I understand what address buses and data buses and control buses do, but...

Why does data not go to the keyboard controller, or come from the VDU output controller?

There are two main methods of doing IO (both obviously have variants, and both are often combined, some control information using the first method and the majority of the data using the second).

One is communicating directly from the processor with the IO-device.  In that case there is a data bus between the processor and the device.
The other is going through memory. The processor write (or read) in memory at well known addresses and the device either monitor the memory accesses or use the first method to know that it has to process the data.

In my experience, keyboard controllers are often using the first method and display controllers are often using the first method for control information (which display mode for instance, or the well known address where to find the information to display) and the second method for the information to display (represented either as character code or as a bitmap)


Prove correctness of recursive algorithm I have this java function:

public int foo(ArrayList l, int n)
{
  if(n <= 1)
    return l.get(0);

  if(l.get(0) < l.get(1))
    l.remove(1);
  else
    l.remove(0);

  foo(l, n-1);
}

So I figure to show that the algorithm is correct I would use an induction proof. However what I am not so sure about is how to go about doing the proof. Will I fist need to derive some sort of mathematical formula for this function and prove that?

Generally, you should follow the instructions given by @vonbrand to carry out a mathematical induction proof for a recursive algorithm. Now I would like to show you more hints.

Playing with a small test case, we know that we should prove the following theorem:

   Theorem: The function foo always returns the minimum value of the original list $l$.

To carry out a mathematical induction on the size $n$ of list, we go through the following three steps:

Base Case: $n = 1$. In this case, you obtain $l[0]$ which is trivially the minimum. (Note that foo throws an exception for case $n = 0$.)
Inductive Hypothesis: Suppose that the theorem holds for $2 \le n \le k$.
Inductive Step: Consider $n = k + 1$. You should prove that (This is left as an exercise) $$\min(\text{modified list } l' \text{ by the `if/else` statement and of size } k ) = \min(\text{original list } l \text{ of size } k+1).$$


Mapping reducibility vs. Turing reducibility Let $A$ and $B$ be two languages. If $A \le_{m} B$ ( reducible by mapping ) then I know that if $B$ is decidable so is $A$ and if $B$ is recognizable so is $A$. And  if $A \le_{T} B$, then if $B$ is decidable so is $A$. But I can't say the same thing for recognizability which  I can see by example when  $A \equiv L_{\phi}$ ( the empty language ) and if $B \equiv A_{TM}$ ( acceptance language ). I know this is because of the fact that we assume the orcale to decide $B$ while proving $A \le_{T} B$. Why is it so that we assume the oracle to decide and not recognize $B$ while comparing relative difficulty of two two languages ? Sorry for vague terminology of relative difficulty, I have not yet begun reading about complexity theory and hierarchies and for now only have a vague idea about it.

You can define a notion of reducibility which will ensure that if $A$ reduces to $B$ and $B$ is recognizable then so is $A$. The definition allows an oracle call to $B$, but the semantics are different: if the contents of the oracle tape are in $B$ then the machine continues, and otherwise it gets stuck (never halts).

The problem with this definition is that it is pretty weak. While the other property (with recognizability replaced by decidability) still holds, it never helps you that $B$ is decidable. Compare this with mapping reducibility: there you are using the full power of decidability.

Still, the definition could be useful. Assuming you aren't the first to come up with this idea, the only conclusion is that this definition doesn't lead to a nice enough theory. It's also possible that you came up with a nice concept which you could develop to a nice theory. A third possibility is that a theory has been developed, but I am unaware of it.


Does $20n$ belong to $O(n^{1-\epsilon})$ for some $\epsilon > 0$? I am quite new to master theorem and I would like to ask the following question for $$()=4(/4)+20.$$
If there is a constant value like $20n$ does it affect the equation?
Would the equation look something like this for test case 1:

Is $f(n) = 20n \in O(n^{log_ba-\epsilon}) \in O(n^{\log_4^4-\epsilon}) \in O(n^{1-\epsilon})$ for some $\epsilon > 0$?

Big O notation hides constant factors. In particular, for every constant $C > 0$,
$$
f \in O(g) \Longleftrightarrow Cf \in O(g).
$$
In particular, for any $\epsilon > 0$,
$$
20n \in O(n^{1-\epsilon}) \Longleftrightarrow n \in O(n^{1-\epsilon}).
$$
This follows directly from the definition of big O. Indeed, suppose that $f \in O(g)$. Then there exist $N,A>0$ such that $f(n) \leq Ag(n)$ for all $n \geq N$. This implies that $Cf(n) \leq ACg(n)$ for all $n \geq N$, and so $Cf = O(g)$. Similarly, if $Cf = O(g)$ then the same argument shows that $f = C^{-1} C f = O(g)$.


Does a byte contain 8 bits, or 9? I read in this assembly programming tutorial that 8 bits are used for data while 1 bit is for parity, which is then used for detecting parity error (caused by hardware fault or electrical disturbance).

Is this true?

A byte of data is eight bits, there may be more bits per byte of data that are used at the OS or even the hardware level for error checking (parity bit, or even a more advanced error detection scheme), but the data is eight bits and any parity bit is usually invisible to the software. A byte has been standardized to mean 'eight bits of data'. The text isn't wrong in saying there may be more bits dedicated to storing a byte of data of than the eight bits of data, but those aren't typically considered part of the byte per se, the text itself points to this fact.

You can see this in the following section of the tutorial:

Doubleword: a 4-byte (32 bit) data item

4*8=32, it might actually take up 36 bits on the system but for your intents and purposes it's only 32 bits.


Boolean Functions Implemented by Multiplexers Electrical engineers often use multiplexers to implement Boolean functions. What is the correct technical term for this model of computation? Is it Decision Tree model or is there another name?

I think there is no specific name for it, just several methods, c.p. this website
Note that it's quite simple to e.g. implement all 2-input logic functions with a 4 input
 1 output mux, by connecting the inputs to the address/select lines, and applying the constants 0/1 to the data inputs. (This actually transforms the MUX into a Lookup table (LUT))


Proving following regular expressions equal to one another? How would I go about proving the following two regular expressions are equal to one another:

( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)*

I can "see" why they are equal to one another because the second ( a + b )* is a redundant term as the expression will always have an ab together. But how can I formalize this and show, in general, that this is true ?

Convert both regular expressions to a DFA, compute the symmetric difference of the two DFA's using a product construction, and then check whether the result accept the non-empty language.  Each of those steps is described here on this site.  See also Does this regular expression equal this automata? for a very similar question.


Maximum waiting time between events such that k events are not missed I've been given some homework on dynamic programming and I'm having trouble to find the suboptimal recurrence. Let me copy the statement:

In a given motorcycle training circuit, the number of riders is becoming increasingly large. As such, a new set of stricter rules is being enforced.

Lap times last exactly a minute, and they are booked for the full minute.
If we use a free lap time slot, we must wait x seconds until we can use another.

We are given a list {s1,s2,s3,...,sn} of the free slots starting time and we want to practice at least m minutes, at minimum. Find the maximum x that allows this.
Example:
With the list {00:00:00,00:10:03,00:14:00} and an m = 2 we can impose a maximum wait time of 00:14:00 - 00:01:00 = 00:13:00 = 1560s because we only need to lap two times, and we can do so with the first and last slot.

So I tried hard and came up with this recurrence:
$$X[i,m] = \max_{1 \leq j \leq i}\ (\min\ (X[j,m-1],\sum_{k=j}^{n-1}abs(s_{k+1} - s_k)))$$
Where X[i,m] means "the maximum distance that I can pick in the subset $\{s_1,s_2,...,s_i\}$ so that I lap at least m times".
Then it's only a matter of applying dynamic programming. However, I'm not convinced that this solution is correct, because no matter how hard I try to make an algorithm out of it (using a matrix $X_{im}$) I can't come up with a good solution looking at the right bottom corner value (where i = n and m = laps requested).
Any ideas or hints?
Thank you.

The solution was using a binary search on the time between laps and since every checking of the value is linear time, computing the solution is cheap. Thank you anyway.


Producing an algebric equation from a graph I'm writing a computer game and one of my game's objects must follow a movement path that is very similar to the following graph.

The bold lines are the Y and X axis. In order to be able to code this movement thought I need the algebric equation that translates to this graph. For example f(x) = x^2.

Is there any mathematic technique I could use to obtain the algebric from of this function?

We can start from $\sin(x)$ which has a nice regular graph. To avoid negative values you can simply use the absolute value $|\sin(x)|$. This produces a graph similar to your but with constant height.

To decrease height as $x \to \infty$ we want to multiply that function by something that decrements. For example $\frac{1}{1+|x|}$ goes to $0$ as $x \to \infty$ and is symmetric. So $\frac{1}{1+|x|}|\sin(x)|$ is something similar to what you want with a maximum height of $1$.

If you multiply by a constant $A$ you "set" the maximum height to $A$. If you want to change the width of the bumps you can simply multiply the argument of the $\sin$ function, for example $\frac{A}{1+|x|}|\sin(2x)|$ will have maximum height $A$ and a width that is half the width of the normal $\sin$, while using $\sin(x/2)$ would produce a bump that is twice the width of the normal $\sin$.

See this wolfram alpha's graph for an example result.

You can also change the degradation of height by setting a different power for the $|x|$. For example using $\frac{1}{1+x^2}$ you'd have a faster drop to $0$, while using $\frac{1}{1+\sqrt{|x|}}$ would produce a slower change in height.


Is any sudoku solver an SAT solver? I have recently created a sudoku solver using C#, which outputs the solution to a sudoku after a reasonable amount of time in many cases. I have used the basic sudoku SAT-reduction (i.e. x111 meaning this is true if column 1, row 1 is filled by 1). The method I have done this does not take in a large clause of variables, but implicitly solves a large proposition (which can be generated) for each puzzle.

Due to the lack of universality, that it can't take in any clause for any other np-complete puzzle, does this still count as an SAT solver? And are there multiple ways of reducing sudoku into SAT (i.e. could you have many different ways of having that large proposition)?

Edit: the way I have created the sudoku solver is by representing each cell by 9 variables, which are classes in the solution. The program converts the user's input into a Boolean proposition made specifically for sudoku (i.e. obeying all sudoku constraints). It then solves the proposition. Due to the fact that sudoku has been reduced to SAT and solved, I'm wondering if the program counts as an SAT solver (to which I believe the answer is no, because it won't take any propositional formula and solve it). However, I also want to know of the 'uniqueness' of sudoku is in a way lost when converted to SAT, because 'real' sudoku problems only have one solution, but as far as I know, SAT only wants to know if there is a possible solution or not.

Your program is not a SAT solver.    A SAT solver takes as input a SAT formula and outputs whether it is satisfiable or not.  Your program doesn't take as input a SAT formula, so it isn't a SAT solver.

Yes, there are multiple ways of reducing Sudoku to SAT.

With standard Sudoku puzzles, we are promised that there exists exactly one valid solution.  With SAT, there might be 0, 1, 2, or more satisfying assignments, and we are asked to determine whether there exists 0 satisfying assignments or 1+ satisfying assignments.  Valiant and Vazirani considered the following problem: given a SAT formula with the promise that it has either 0 or 1 satisfying assignments (not more than 1), determine whether it has 0 satisfying assignments or 1 satisfying assignments.  They showed a randomized polynomial-time reduction showing that this problem is at least as hard as SAT (specifically, there is no polynomial-time algorithm for this problem either, unless NP=RP).

More generally, we could ask about the following problem: given a SAT formula with a promise that it has exactly 1 satisfying assignment, find the satisfying assignment.  This problem is the analogue of Sudoku (where we're given a Sudoku puzzle with the promise that it has exactly 1 valid solution, and we're asked to find that solution).  It follows from Valiant and Vazirani's result that this problem is at least as hard as SAT under randomized polynomial-time reductions; if you could solve this problem in polynomial time, you could solve SAT in (randomized) polynomial time.  So, the promise that a SAT formula has exactly 1 valid solution doesn't make it any easier to find the solution.

Further reading: UniqueSAT and UnambigousSAT at https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT, https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem, https://cstheory.stackexchange.com/q/1639/5038, Unique SAT complexity clarification, Proof of SAT is randomly reducible to UNIQUE-SAT, https://cstheory.stackexchange.com/q/22093/5038.


Taking mod $2$ with LTF gates Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates?

I do not mean that the input is the infinite set of positive integers. Think of the input as coming on a single wire carrying a non-negative integer.

This is impossible. For large enough $n$, all your threshold gates will be "saturated", that is, they will have the same output on all large enough $n$, and in particular won't be able to distinguish between $n$ and $n+1$.


Finding the best N length combination between M items Lets say I have a few million random items. Each item has 6 attributes: Type, Cost, Strength, Stamina, Agility and Intelligence. Type is one of 4 different possibilities, the other 5 are various numbers

Now I must produce a set of 4 items where the inputs are X (the maximum cost of all items) and Y (one of the latter 4 attributes that is favored) so that

Each of the types is present exactly once
The total cost must be below a certain amount (X)
The attribute determined by Y must be the highest among all possible combinations

Currently I'm doing this in a brute force manner, just trying every single combination and comparing it to the current best result but its very time consuming. I was wondering if anybody knows of an algorithm or something that would cut down the execution time?

This problem is similar to Knapsack Problem and it is NP-Complete. You may find its proof in here


Is the following language is a context free grammar language? The question is to determine whether L is a context free grammar language, what do you think?

Consider the word $w = 0^n1^n0^n \# 0^n1^n0^n \in L$ for a sufficiently large value of $n$.

By the pumping lemma for context-free languages, we know that if $L$ is context-free then there are$a,b,c,d,e = \Sigma^*$, with $|bcd| < n$ and $|bd|>1$ such that $w=abcde$ and, for every $i \ge 0$, $a b^i c d^i e\in L$.

Notice that neither $b$ nor $d$ can contain $\#$, as otherwise setting $i=0$ would show that $a c e \not\in L$.

If $c$ contains $\#$, then $b,d \in 0^*$ and $a b^i c d^i e$ is a word of the form $0^n 1^n 0^{x + i|b|}\#0^{y+i|d|} 1^n0^n$ with $x+|b|=n$ and $y+|d|=n$.  If $|b|>0$ you can make the first part of the word (before $\#$) end with more than $n$ zeros by picking $i=2$, resulting in a contradiction. Otherwise $|d|>0$ and you can make the second part of the word (after $\#$) start with less than $n$ zeros by setting $i=0$.

If $c$ does not contain $\#$ then $b$ and $c$ either both precede or both follow the unique occurrence of $\#$ in $w$. If they precede $\#$, pick $i=2$. If they follow $\#$, pick $i=0$.
In this way the first part of the word becomes longer than the second (and hence not in $L$).


Has there been any more progress on P vs. PSPACE compared to P vs. NP? I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown for P vs. NP but have not been shown for P vs PSPACE, so that there is hope that certain proof techniques might resolve P vs PSPACE even though they cannot resolve P vs NP? And are there any non-trivial results that say that if P = PSPACE then there are implications that do not necessarily hold under P = NP? Or anything else non-trivial in the literature that suggests it's easier to prove P != PSPACE than it is to prove P != NP?

This doesn't really answer your question, but there is a result that under a restricted form of time travel (yes, time travel), it holds that $P=PSPACE$. I'll remark that the result is nontrivial, given the restrictions on the model.
See this explanation by Scott Aaronson.


Is this concatenation of two FA done right? $r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$
Details:
Consider these two FA
$FA_1$

$FA_2$

if $r_1,r_2$ and $r_3$ are regex for $FA_1,FA_2$ and $FA_3$ respectively where
$r_1=(a^*b)^*$
$r_2=(a+ba)^*bb(a+b)^*$
then, mathematically, $r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$
But $r_3$ turns out different when I actually concatenate $FA_1$ and $FA_2$ and use the new transition table (given below) for $FA_3$ to generate its regex ($r_3$) and the $TG_3$ (given below) and then simplify, $r_3$ becomes $(a+ba)^*bb(a+b)^*$ which is the same as $r_2$ (i.e. $r_1$ not prefixed). and since $r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ can't be simplified into $r_2=(a+ba)^*bb(a+b)^*$
I am convinced that the problem is in the concatenation/transition table,
especially with the circular references to $x_1$ and $y_1$, which i don't completely get. That also would mean $TG_3$ iswrong.

The Transition Table:

$TG_3$

Now, it'd be very tedious to explain how i created the transition table, it's easier to figure out by looking at it. but key point i can't quite grasp the "$x_1$ and $y_1$ being connected" part
Sidenotes:
 - This is the only way to concatenating two FA that i know of. I am on a distant learning platform and it's quite low quality material, so links to proper methods are appreciated.
 - If you use another method, please keep in mind that the transition table, regex and the TG and all required
 - The TG looks like an FA to me (barely know the difference) but the site i used to generate it says it's a TG. what's the difference?

You can think of the concatenation of the languages defined by the two automata as the language of the automaton that can be obtained by connecting all final states of the first (in the example, just $x_1$) with the starting state of the second ($y_1$), by an empty transition, and then making them non-final.

A transition table can then be used to convert the NFA just generated into a DFA, which is what you did.

In this case, $r_1r_2$ is indeed equivalent to $r_2$, and this is completely normal. A transition graph represents a transition function, which is part of an automaton. If you minimize $TG_3$, what you get is exactly $FA_2$, which confirms the equivalence.


Analyzing a randomized algorithm for finding an approximate median of an array I'm given an array $A$ = ($a_1, a_2, \cdots a_n$), where n is uneven. For an element $a_i$ we denote its position in the array with $p(a_i)$. This element would be an $ε$-approximate median of the array, if after we sort it, the following inequality holds:

$$\frac12 ((1 - ε) × n) < p(a_i) \leqslant \frac12 ((1 + ε) × n)$$
For example, the array $1,2,\cdots,9$ would have $4,5,6$ as $\dfrac13$-approximate medians.

My task is to analyze the following randomized algorithm, which finds an $ε$-approximate median of the array in constant time:

  Choose $2k + 1$ elements of the array $A$: $b_1, b_2, \cdots, b_{2k+1}$, where each element is chosen uniformly randomly and independently of all the others (it is possible for an element to repeat). Using the algorithm for finding a median of an array in linear time (QuickSelect) output the median of the array the elements $b_1, b_2, \cdots, b_{2k+1}$ form.

I'm also given the following two random variables:

$K$: number of elements in $b_1, b_2, \cdots, b_{2k+1}$, which are smaller or equal to the $\dfrac12 ((1-ε)×n)$-biggest element in the original array
$A$.

$G$: number of elements in $b_1, b_2, \cdots, b_{2k+1}$, which are bigger than the $\dfrac12 ((1+ε)×n)$-biggest element in the original array $A$.

What I have to do is find the best possible upper bounds for
$$P(K \geqslant (1 + ε) E(K))$$
and
$$P(G \geqslant (1 + ε) E(G)),$$
where $E(K)$ and $E(G)$ are the expected values for the random variables. I also have to find a bound for the probability the algorithm will be successful, which depends only on $k$, not on $n$, $E(K)$ or $E(G)$.

What I have done so far: I computed the expected values for the two random variables. I believe they are binomially distributed, so for example for $K$ I have $2k + 1$ events each with probability $\dfrac12(1-ε)$ to happen, so
$$E(K) = (2k + 1) × \dfrac12 (1 - ε).$$
$E(G)$ turns out to be the same. Then I tried computing the two upper bounds, mentioned above with the Markov, Chebyshev and Chernoff inequalities:

Markov:
$$P(K \geqslant (1 + ε) E(K)) \leqslant \frac1{1 + ε},$$
Chebyshev (might be false):
$$P(|K - E(K)| \geqslant εE(K)) \leqslant \frac{\operatorname{Var}(K)}{ε^2 × (E(K))^2} = \frac{1}{ε(2k + 1)},$$
Chernoff:
$$P(K \geqslant (1 + ε) E(K)) \leqslant \exp\left( -\frac13 ε^2 E(K) \right).$$
Are these correct? If they are, am I correct that Chebyshev is the best one? How do I continue with finding the probability of success of the algorithm?

Thank you :)

As suggested in the comments, the Chernoff bound is the best one because it gives better bounds as the input grows. We can again use this same Chernoff bound to determine a lower bound for the probability of success for the algorithm. This turns out to be $1 - 2 * \exp\left( -\frac13 ε^2 E(K) \right)$ as we have to subtract from $1$ the probabilities $P(G \geqslant (1 + ε) E(G))$ and $P(K \geqslant (1 + ε) E(K))$ because those are exactly the cases, where the algorithm fails to output the desired $ε$-approximate median.


Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem? Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges.
In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells.
(i.e., $|x| = O(n^2)$ or $|x| = O(m \log n)$).
Now I want to study the lower bound and the upper bound on the time/space complexity with respect to the number of vertices $n$. Suppose we have found the upper bound is $O(f(|x|))$ and lower bound $\Omega(g(|x|))$. Since $m = O(n^2)$ and $m = \Omega(n)$, we can only conclude that
$$O(f(|x|)) = O(\max\{f(n^2), f(m\log n) \}) = O(f(n^2\log n))$$
and
$$\Omega(g(|x|)) = \Omega(\min \{g(n^2), g(m\log n)\}) = \Omega(g(n\log n))$$
The gap become larger. It is not tight even $f = g$.
Is there way to solve my confusion?
Now I define the graph problem as a pair $(L', O)$ where for every instance $x'$ of $L'$, it is only encoded by the  number of vertices, $O$ is an oracle whose valid input is a pair of vertices $(u,v)$, it returns 1 if $uv$ is an edge in the graph and it returns 0 otherwise. Can I solve my confusion by using this model? (However it seems that $|x'| = O(\log n)$ which is very small.)

I will try to lift some of the confusion you have.
Let $G$ be some graph, with $n$ vertices and $m$ edges. Then what is $|G|$? Lets say we encoded it as adjacency matrix, so it takes up $n^2$ space. Therefore, $f(|G|)=f(n^2)$ and $g(|G|)=g(n^2)$. There won't be a "gap" here.
What about if we encode it with $m\log(n)$ space? then we would have $|G|=m\log(n)$ and thus $f(|G|)=f(m\log(n))$ and $g(|G|)=g(m\log(n))$.
So what went wrong with your calculations? The difference here is that you used max once and min once to represent the same quantity. You probably did this to "give a bound" only, but notice the following interesting thing: why would we want max? we can always encode the graph in the smallest way possible, so essentially $|G|=\min \{n^2,m\log(n)\}$. Substitute this and get $g(|G|)=g(\min \{n^2,m\log(n)\})$. In the same way, $f(|G|)=f(\min \{n^2,m\log(n)\})$.
Notice I didn't give the bounds in terms of $\Omega$ and $O$, but we could. In any case, the transition $g(\min \{n^2,m\log(n)\})=\Omega(g(n\log(n)))$ is not strict, since there are many times that $\min \{n^2,m\log(n)\}> n\log(n)$. The same goes with the transition $f(\min \{n^2,m\log(n)\})=O(f(n^2)))$ (making this a min automatically made the bound better).
I hope this helped you understand a bit more how the bounds behave with respect to the size of the graph and its different encodings.


sort array with some of the elements in a known range Let $A$ be an array of n elements. We know that $n - \lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$ (the other $\lfloor \sqrt n \rfloor$ elements may or may not be in the range). I need to sort the array in $\Theta (n)$.
I thought of partitioning the array to 3 subarray:

elements smaller than $\sqrt n$
element in range $\sqrt n$ to $n\sqrt n$
element bigger than $n\sqrt n$

the first and last subarrays can be sorted with insertion sort in $O(n)$ because there are at most $\lfloor \sqrt n \rfloor$ elements in those arrays. The second array have between $n - \lfloor \sqrt n \rfloor$ to $n$ elements in range $\sqrt n$ to $n\sqrt n$ so using counting sort will run in $O(n\sqrt n)$. Using bucket sort where each bucket has all the elements in subrange with n integers each bucket can be sorted with counting sort in O(n) and  there are $\sqrt n$ buckets so the sort will also take $O(n\sqrt n)$.
My problem is how to sort that second array in $O(n)$? I assume it is something to do with the amount of buckets or maybe the subrange of each bucket, as sorting the second array costs $O(number\_ of\_buckets * O(number\_of\_elements\_in\_bucket + number\_of\_integers\_in\_range))$

Using radix sort, the second subarray can be sorted in $\Theta(log_{b}(n\sqrt n)(n + b)$ where $b$ is the base with which the numbers are represented. If $n$ is chosen  as the base, radix sort sort the array in $\Theta(log_{n}(n\sqrt n)(n + n)) = \Theta(\frac{3}{2}(n + n)) = \Theta(n)$. Now all 3 subarrays can be sorted in $\Theta(n)$ thus the array is sorted in $\Theta(n)$


Complexity of Simon's Problem In reading the Wiki article on Simon's Problem, the article states that it takes exponential time(in the classical version) to discover the secret string S that is inside the black box. Why is this black box problem not considered to be a one way function and are there any cryptographic primitives based on the hardness of discovering the secret string S. Thank you!

A one-way function is a function $f$ such that $f(x)$ is easy to compute, but given $y$ in the range of $f$, it is hard to computer a preimage of $f$. Notice that there is no black-box involved. The idea is that $f$ "looks like" a black box that applies $f$ in the sense that you can apply $f$ but cannot do much more, and in particular cannot invert $f$ (or even learn anything about the inverse).

The goal of cryptography is to come up with cryptographically secure algorithms. There is no place for a black box there. That said, when constructing protocols from primitives, we often treat the primitives as black boxes with certain properties. In some cases we can actually show that this point of view isn't general enough - we show that given one primitive as a black box, another primitive cannot be constructed, though perhaps such a construction is possible given access to the code of the first primitive.


Logical equivalence and equality Let be $F=(A\land B)$ and $G=\neg(\neg A \lor \neg B)$. Which of the following statements are correct

$F=G, F\equiv G, \neg F=\neg G, \neg F\equiv\neg G$?

Is there a difference?

Equality is a syntactic notion, equivalence is a semantic notion. Two expressions are equal if they are the same expression — in other words, an expression is only equal to itself. Two logical expressions are equivalent if they have the same truth value in every interpretation.

Two equal expressions are always equivalent, but the converse doesn't hold. For example, $A \equiv \lnot\lnot A$ but $A \neq \lnot\lnot A$.


If $\log xy=\log x+\log y$ then why multiplication is harder than addition? Someone told me that the $\log$ function was introduced to make the calculation easier. If we have to calculate $xy$, we can calculate instead $\log x+\log y$ since $\log xy=\log x+\log y$. How this can make the calculation easier? Maybe from a mathematician point of view but what about a computer scientist's point of view?

If it makes the calcualtion easier then why people do not use it to simplify the complexity of the multiplication algorithms?

From my own thinking, this transformation makes the calculation more difficult. How can we calculate the $\log x$ and $\exp x$ functions in a computer?

Am I right? Any suggestions please? Thank you for your time.

Logarithms were used to make computation easier at a time when computers were not available.  Even in the twentieth century, when mechanical machines became available to do arithmetics with much precision, they remained so expensive, and often cumbersome, that most people did not use them. The mechanical hand held calculator doing the four arithmetic operations did not appears before the end of the second world war
(this machine, called the Curta, was actually designed in a concentration camp, which saved some lives).
Since most calculations did not require too much precision, many people simply used slide rules, or tables of logarithms. The typical cartoon of a scientist or engineer whould show him with the slide rule in his front pocket.

I am old enough that I did not have hand calculators at school (computers still used more space than my classroom). What I
had was a slide-rule, which is based on logarithms. It did not give a
very high precision (at best something like $10^3$, i.e., 3 decimal digits),
but it was invaluable to do problems in physics.  Numbers were read
directly on the slide rule, that essentially can add lengths.

For more précision, we would use tables stored in books. That gave 4
digits, plus one with interpolation (as I recall). We also has direct
table for logarithms of trigonometric functions.

This was well organized, and the cost of computing logs and
exponentials with the tables was nothing compared to the savings of
not doing multiplications by hand. It was actually free, with direct
reading of graduations, on the slide-rule.

This was not a mathematician viewpoint, but a physicist viewpoint,
or that of any person having to do much calculation involving
multiplications, such as astronomers, or people mapping the land
(which probably took several centuries).

I did not check, but I would guess that numerical algorithmic design
at the time must have been much influenced by the idea of minimizing
translation to and from logarithms. I would guess we were told in class to be careful about that.

Considerable effort was also spend in building very precise tables. By
hand, of course, at least until mechanical arithmetic machines became available. According to wikipedia, despite a large number of earlier prototypes, the calculator industry did not start before the middle of the 19th century.

This all started with the invention of logarithm by John Napier at the
beginning of the seventeenth century. His contact with astronomer
Tycho Brahe who was at the time mapping very accurately the motion of
celestial bodies (so that Kepler and Newton would have the data for
the work that made them famous), and other such person, may not have
been foreign to his invention of this most remarkable computation
tool.

The fact that logarithms can make multiplication easy was certainly
one very important factor in the development of science and
technology for nearly 3 centuries.
But not knowing exactly who used it and when, I cannot make a more
precise statement.


How to prove the emptiness of intersection of two context free languages is undecidable? Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.

Do you maybe have a book or paper I should investigate?

A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.

The following is a proof taken from this note by Rob van Glabbeek.

Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.

Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem.
Given a set $d_1,\cdots,d_n$ of dominos where, for $i=1,\cdots,n$, the top string of $d_i$ is $w_i$ and the bottom string of $d_i = x_i$. Consider the context-free grammars

$$W\to w_1Wd_1\mid w_2Wd_2\mid\cdots\mid w_nWd_n\mid w_1d_1\mid w_2d_2\mid\cdots\mid w_nd_n$$
and
$$X\to x_1Xd_1\mid x_2Xd_2\mid\cdots\mid x_nXd_n\mid x_1d_1\mid x_2d_2\mid\cdots\mid x_nd_n.$$

Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.


Decrease space complexity, how will time complexity increase? I have a problem whose lower bound of problem complexity is proven to be $O(n+m)$ (n < m) and I also come up with an algorithm whose time complexity is $ O(n+m)$, space complexity is $ O(n)$. (All on deterministic turning machine)

If there exists an algorithm that uses O(1) space to solve the same probelm, what will be its lowest time complexity?

To ask in another way, if space complexity decrease from O(n) to O(1), what at least time complexity will increase from O(n+m)?

It depends on the problem.  There's no general rule.

The running time could be as low as $O(n+m)$: for some problems, there exists an algorithm with running time $O(n+m)$ and $O(1)$ space.  (Think about finding the maximum of an array with $n+m$ elements, for example.)

The best possible running time could also be as arbitrarily large.  For instance, think of analyzing connectivity in graphs: given a graph and two vertices $s,t$, determine whether there's a path from $s$ to $t$.  Let $n$ denote the number of vertices and $m$ the number of edges in the graph.  There is a simple algorithm with running time $O(n+m)$ and space complexity $O(n)$, namely, depth-first search.  However, there is no known algorithm whose running time is polynomial in $n$ and $m$ and that uses only $O(1)$ space.

See also https://cstheory.stackexchange.com/q/4556/5038 and https://cstheory.stackexchange.com/q/832/5038 for more technical details on this.

Terminology nitpick: problems have a complexity; algorithms have a running time.  the complexity of a problem is the running time of the best algorithm for that problem.


Is selecting some of the sets such that their intersection is of size k NP-hard? Given collection of sets S1,...,Sn and a positive number k. Is the problem of selecting some of the sets such that their intersection is of size k NP-hard?

So far, I tend to believe it is so I tried to find a reduction (unsuccessful so far),
I have tried is to replace intersection by union (which is equivalent if we take the complementary sets).

I've also tried to dualize the problem and view a values as representing sets where they appear (unfortunately this transformed problem is not equivalent Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones)

I don't know if this problem is of interest for the reduction but it is the closest hard one I've found
http://www.ic.unicamp.br/~eduardo/publications/ipl12.pdf

As you suggested, the problem is equivalent to selecting sets with union of given size $k$. It is not easier than selecting given numbers (say, $m$) of sets with union of given size $k$, since we could add different auxiliary elements $a_S^{(0)},\ldots,a_S^{(n)}$ to each set $S$ and ask for a union of size $m(n+1)+k$, where $n$ is the size of the original universe. Now it is not hard to show the later problem is NP-hard because of a reduction from X3C (exact cover by 3-sets).


Computing a histogram with the number of extant values not known in advance (This may be more fitting for CSTheory, I'm not sure.)

I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for the following problem:

Unknown-Number-of-Bins Histogram

Inputs:

An array of integers $a$, of length $n$.

Outputs:

An array of integers $\text{bins}$ of length $m <= n$.
An array of unsigned integers $\text{counts}$, also of length $m$.

Output Requirements:

For every $i \in \{0...m-1\}$ it must be the case that

$\bigl|\bigl\{ j \in \{0...n-1\} \mid a_j = \text{bins}_i \bigr\}\bigr|$
$ = \text{counts}_i$

In other words, $\text{bins}$ and $\text{counts}$ constitute a histogram of $a$, with one bin for every unique value in $a$.
It is not required for $\text{bins}$ or $\text{counts}$ to be sorted.

Other Notes:

Complexity is considered as a function of both $n$ and $m$.
Low time complexity is required both asymptotically and for relatively low values of $m$ - but it is not required for low values of $n$.
No hiding monstrosities in the $\mathop{O}(\cdot)$ constants please! This should be usable in practice.
A parallel(izable) approach? You are most welcome :-)
Low space complexity is a plus.
Deterministic algorithms preferred, and barring that, go easy on those coin flips.

Clearly, there are many way to go about this, some very straightforward, e.g. "sort the input, then build a sorted histogram in a single pass", in $\mathop{O}(n \log{n})$ time. Of course I'm interested in something better....

Often, in order to improve a sorting-based algorithm from $O(n\log n)$ to $O(n)$, one can use hash tables. In this case, you would use a hash table of size $O(n)$. Each entry of the hash table would store an integer and its count. The entire algorithm would now run in expected time $O(n)$.


Optimal covering of 2D matrix elements given spatial constraints I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction.

I've generalized and reduced the problem to this:

Given an $M \times N$ matrix with elements in $\{0, 1\}$, cover all the $1$ elements according to the following rules:

"Marking" an element covers that element as well as the elements directly above and below
A maximum of $\frac{N}{2}$ elements can be marked in any row of the matrix

while minimizing the number of $1$ elements that are covered by an adjacent element but not marked itself.

For example,

Let $M = N = 4$ and consider the following matrix:

$$
\begin{bmatrix}
1 & 0 & 1 & 1\\
0 & 1 & 1 & 0\\
1 & 1 & 1 & 1\\
0 & 0 & 0 & 1
\end{bmatrix}
$$

Because $N = 4$, only 2 or less elements may be marked per row.

An optimal solution is as follows, where marked elements are shown in red, and elements that are covered but not marked are shown in blue.

$$
\begin{bmatrix}
\color{red}{1} & 0 & \color{blue}{1} & \color{red}{1}\\
0 & \color{red}{1} & \color{red}{1} & 0\\
\color{red}{1} & \color{red}{1} & \color{blue}{1} & \color{blue}{1}\\
0 & 0 & 0 & \color{red}{1}
\end{bmatrix}
$$

In this solution, there are three $1$ elements that are covered but not marked (in blue).

For this problem, I need an actual assignment of the marks for each row, not just the final minimum cost.

The spatial relationship between neighboring elements initially led me to think about the problem in terms of a graph, so I tried setting it up as a minimum-cost maximum-flow problem, but I couldn't figure out how to model the flow graph.

Then I started looking into set-covering and ILP, but I'm not sure how to specify the rule about the relationship between vertical neighbors as a constraint.

Yes, this can be expressed as an instance of integer linear programming and then solved with an ILP solver.  I don't know if there's a better way (for instance, I don't know if the problem is NP-complete).

We'll define zero-or-one variables $x_{i,j}$ and $y_{i,j}$, with the intention that $x_{i,j}=1$ means that cell $(i,j)$ of the matrix is marked and $y_{i,j}=1$ means that cell $(i,j)$ is covered.  Let $A$ denote the matrix.  Then we have constraints to ensure that all 1's in the matrix are covered: $y_{i,j} \ge 1$ for all $i,j$ such that $A_{i,j} = 1$.  Also, we have constraints to ensure that the $x$'s and $y$'s are related appropriately:

$$y_{i,j} \ge x_{i,j} \qquad y_{i,j} \ge x_{i-1,j} \qquad y_{i,j} \ge x_{i+1,j}$$

$$y_{i,j} \le x_{i-1,j} + x_{i,j} + x_{i+1,j}$$

To impose the requirement that at most $N/2$ cells are marked in each row, add the constraints

$$\sum_j x_{i,j} \le N/2.$$

Finally, notice that $y_{i,j}-x_{i,j}$  is $1$ if cell $(i,j)$ is covered but not marked, and $0$ otherwise.  Therefore, the objective function is:

$$\sum_{i,j} y_{i,j}-x_{i,j}$$

Now feed this to an ILP solver, and let it do what it can to try to solve it.


Difference between Bayesian Networks and Dynamic Bayesian Networks I'm studying Bayesian networks and want to clarify a couple of things with people who are more knowledgable in the area than me.

As far as I understand it, a Bayesian network (BN) is a directed acyclic graph (DAG) that encodes conditional dependencies between random variables. The graph is drawn in such a way that the the distribution (dictated by a conditional probability table (CPT)) of a random variable conditioned on its parents is independent of all other random variables. I'm assuming that, by definition, both the structure (nodes and edges of the DAG) and the entries of the CPT in a BN assumed to be fixed in time.

Now, I'm wondering about the distinction between BNs and Dynamic BNs (DBNs), specifically, where the dynamic term in a DBN arises from:

Does this mean that the structure AND conditional dependencies between variables are time-varying? If so, is a BN with a fixed structure (DAG) but time-varying probabilities also considered a DBN (does this type of 'DBN' have a name)?

I'm not sure if what I've said is correct. Please let me know if I went wrong anywhere or if there is a better way of thinking about this.

A DBN means that your model is replicated over each time discrete time step t, called slice. Variables of each slice can be connected together, as well a from previous slice to a latter slice (in this precise direction only). The probability tables and links remain the same in each slice if the model is stationary, which is the default case (otherwise they are a function of t).

In a 2TBN (2-step Timeslice Bayesian Network), there are links only between the previous and current slices.

For more information c.f. section 3.2 of http://journal.frontiersin.org/article/10.3389/fncom.2014.00131/full


Why is `map insertionsort` not to equal to`map mergesort`? In the type theory podcast ep. 3, Dan Licata claims that the fact that for every input, insertionsort and mergesort give the same result does not imply that the result would be equal when used as higher order functions as arguments to a third function, i.e. map insertionsort does not have to equal map mergesort.

He explains this by "because you don't know that, as functions, insertionsort and mergesort are equal" but I still don't get it.

Why is this the case? A counter example would be great!

It has to do with the axiom of extensionality, i.e. whether you accept it for functions or not.

The statement of this axiom with regard to functions is
$$\forall f,g:A \to B,\ ((\forall x:A ,\ f\ x = g\ x) \Leftrightarrow f = g).$$
Informally it means that if two functions are equal point-wise, then we consider them equal.

Syntactically merge-sort and insertion-sort are not equal, but if we don't care about their time and memory complexities (I mean if care only about their results) we can accept the axiom of extensionality and consider them equal. That means we can substitute one for another in every expression under consideration without actually changing anything. In this case $\text{map}\ f = \text{map}\ g$.

On the contrary, if we reject the aforementioned axiom, then we can only prove a statement like this:
$$(\forall x:A,\ f\ x = g\ x) \implies \forall xs:\text{list}\ A,\ \text{map}\ f\ xs = \text{map}\ g\ xs.$$
Notice that the conclusion is not the same as $\text{map}\ f = \text{map}\ g$.


Switching Lemma and AC0 reductions between SAT problems Have there been efforts to show (using the Switching Lemma), for example, that SAT or 3SAT cannot have an AC$^0$ reduction to 2SAT?  What are the issues or difficulties involved?

SAT and 3SAT are complete for NP, and 2SAT is complete for NL under AC$^0$ reductions.  Hence such a proof would separate NP from NL.

In the case of a 3SAT to 2SAT reduction in AC$^0$, the bottom fan-in is bounded by 3 (at least prior to the first switching).

It is hard to see how you would use the fact that the target of the reduction is 2SAT rather than, for example, 3SAT.

The common way one applies the switching lemma is roughly this. Apply a random restriction that fixes all but a $\lambda$ fraction of the inputs, for some small parameter $\lambda$ which depends on the parameters (size and depth) of the AC0 circuits in question. Then with constant probability, the function computed by the AC0 circuit becomes constant.

Applying this in our case, we have fixed all but $\lambda n$ of the inputs, and in return, some $\mu$ fraction of the outputs is fixed. And now what? We don't know anything about the reduction, so it's not clear how to obtain a contradiction. What's more, I don't see how you would use the fact that the target problem is 2SAT rather than, say, 3SAT, in which case there can be no contradiction.

The switching lemma is at its best when you have a concrete function in mind and you want to prove AC0 lower bounds for this specific function. Another, less typical, use of the switching lemma is to prove some general properties of any function computed by an AC0 circuit. The most famous example is Linial–Mansour–Nisan, which gives bounds on the rate of decay of the Fourier spectrum. It's not clear how you'd use information like this in your case.


Removing max number of edges while keeping minimum distances Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there are two types of edges - black and red. The black edges are in the form (1,x) where x is a vertex and red edges can be any pair (x,y) .My question is how can I find the maximum number of black edges I can remove so that the minimal distance from 1 to any other vertex is preserved?

Your graph has no negative edges, then you can do a full exploration using Dijkstra algorithm starting from node 1. You stop when you have explored all nodes. Just record every black edges you cross.

An important point is, when you have several equal distances on a step, always give priority to red edges.


Find shortest paths in a weighed unipathic graph A directed graph is said to be unipathic if for any two vertices $u$ and $v$ in
the graph $G=(V,E)$, there is at most one simple path from $u$ to $v$.

Suppose I am given a unipathic graph $G$ such that each edge has a positive or negative weight, but contains no negative weight cycles.

From this I want to find a $O(|V|)$ algorithm that finds all the the shortest paths to all nodes from a source node $s$.

I am not sure how I would go about approaching this problem. I am trying to see how I could use the fact that it contains no negative weight cycles and of course at most one simple path between any node $u$ to $v$.

Choose a data representation

First, look at the size of the result. You want the collection of shortest paths from $s$ to every other node. Unless the average length of a path is bounded by a constant (which it isn't: any list is unipath, and if you take the root for $s$ the total length of the paths is $n(n-1)/2$ where $n$ is the length of the list), you'll need to be careful in your data representation: the structure containing the paths will need to use sharing between paths.

   Excluding cycles, there is a single path from $s$ to any other node $u$. If that path goes through an intermediate node $t$, then the first segment of the path is the desired path from $s$ to $t$.

I propose to store the result in an array, indexed by nodes numbered from $0$ to $|E|-1$, with $s=0$. Each element in the array stores the index of the previous node on the path to that node (use e.g. $-1$ as a special marker for nodes that are unreachable from $s$). The path from $s$ to $t$ will be $(s=R[\ldots R[t]\ldots],\ldots,R[R[t]],R[t],t)$.

Traverse the graph

Initialize $R$ to all $-1$.

Perform a depth-first or breadth-first traversal of the graph starting from $s$. Each time a node $u$ is reached, set $R[u]$ to its predecessor.

Since there are cycles, a node might be reached more than once. Having $R[u] \ne -1$ indicates that $u$ has already been visited.

Prove the correctness

   Because of the unipathic property, it doesn't matter how we reach each node, as long as we haven't completed a cycle. There is only one simple path.

Prove the complexity

The algorithm may reach each node more than once, so it's not clear that its complexity is $O(|V|)$. The work done is in fact $\Theta(|E_0|)$ where $V_0$ are the edges that are reachable from the source. More precisely, we reach a node more than once only in one circumstance: if the node is the first that we reach on a particular cycle, and in this case we reach it twice (once from a simple path, and once after completing the cycle).

Well then. Let's prove that in a unipathic graph, the number of elementary cycles grows at most linearly with the number of nodes. (An elementary cycle is one that does not contain a shorter cycle.) In the following discussion, I'll assume that the graph has no self-edge (no edge from a node to itself; such edges are irrelevant for the path construction anyway).

Unipathic graphs can have cycles, but in a very constrained way. It would be nice if we could somehow associate each cycle to a distinct node (or at least, at most a bounded number of cycles per node). Can cycles share a node? Unfortunately, yes.

   You can have $m$ cycles all sharing one node $a$ and no other nodes. The resulting graph is unipathic. With cycles of length 2, this is a star pattern with a central node $a$ and any number of nodes $b_i$ such that $\forall i, a \leftrightarrows b_i$.

So we'll need to work harder. Well, let's try to prove it inductively. Let $\#V(G)$ be the number of nodes in a graph $G$, $\#E(G)$ the number of edges and $\#C(G)$ the number of elementary cycles that aren't self edges. I assert that if $G$ is unipathic and not empty then $\#C(G) \le \#V(G)-1$.

For a graph with one or two nodes, this is obvious. Suppose the assertion holds for all graphs such that $\#V(G) < n$ and let $G$ be a unipathic graph with $n$ nodes. If $G$ has no cycle, $0 = \#C(G) < \#V(G)$, case closed. Otherwise, let $(a_1,\ldots,a_m)$ be an elementary cycle.

   Collapse the cycle: let $G'$ be the graph whose nodes are those of $G$ minus $\{a_1,\ldots,a_m\}$ plus a node $a$ and whose edges are all the edges of $G$ not involving the $a_i$'s, plus $a \rightarrow_{G'} b$ whenever $\exists i, a_i \rightarrow_G b$ and $b \rightarrow_{G'} a$ whenever $\exists i, b \rightarrow_G a_i$. Every path in $G'$ induces a path in $G$ (if the path involves $b \rightarrow a \rightarrow c$, then replace this by $b \rightarrow a_i \rightarrow a_{i+1} \rightarrow \ldots \rightarrow a_j \rightarrow c$ in $G$). Therefore $G'$ is unipathic. Furthermore, since cycles in $G$ do not share edges, $G'$ has all the cycles in $G$ except for the one we eliminated: $\#C(G') = \#C(G)-1$. By induction, $\#C(G') \le \#V(G')-1$. Since $\#V(G') = \#V(G) - m + 1$, we have $\#C(G) = \#C(G')+1 \le \#V(G) - m = n-m \le n-1$.

This concludes the proof. The traversal follows at most $2|V|-2$ edges.


Return copy of array, each element product of all others, constant additional space, no division Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows:

Given an array $<a_1, \ldots, a_n>$ of fixed-length ints, devise an algorithm which returns a new array $<b_1, \ldots, b_n>$ where each $b_i$ is the product of all $a_j$ with $j \neq i$. That is, each element of the result is the product of all other elements in the original array. Division is not allowed, and the algorithm  must run in $O(n)$ time and $O(1)$ additional space.

Example: $<1, 2, 3>$ should be updated to $<2*3, 1*3, 1*2>$.

A variation of a solution left by a commenter called Vince
Given input $a = <a_1, ..., a_n>$.

Allocate result array $b = <b_1, \ldots, b_n>$. Set $product = 1$.
For $i \in [1, n]$, set $b_i = product$ and set $product = product * a_i$.
Set $product = a_n$. For $i \in [n - 1, 1]$, set $b_i = b_i * product$, and set $product = product * a_i$.
Return the array $<b_1, \ldots, b_n>$.

This solution runs in $O(n)$ time and $O(1)$ space additional to that allocated for the result.


Show that the Halting problem is reducible to its complement HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$
  halts on input $w$

  The complement of HALT$_{TM}$ is the set of all machine-input pairs
  $<M,w> $ where $M$ doesn't halt on input $w$

  Show that HALT$_{TM}$ is turing reducible to its complement, and
  explain why it's impossible for it to me many-one reducible.

Regarding the Turing reduction, I've made reduction proofs using using A$_{TM}$ and HALT$_{TM}$ but this doesn't make sense to me intuitively.

I understand the concept of many-one reduction using the Oracle, but have difficulty applying it, not being given any examples to work with.

I'd hugely appreciate it if someone could help me approach the above question, I'm more concerned with the approach rather than the answer, as I've an exam tomorrow!

Thanks a lot.

Suppose $HALT$ was many one reducible to $\overline{HALT}$. Let the mapping function be $f$. We construct a machine $D$. It takes input $\langle M,w \rangle$ obtains the string $f(\langle M,w \rangle)=\langle M^{'},w^{'} \rangle$. $D$ simulates $ M$ on $w$ and  $M^{'}$ on $w^{'}$. If the first simulation ends  $D$ accepts if second simulation ends/halts it rejects. $D$ is a decider for $HALT$ which is not possible.


A more rigorous proof on a Bellman-Ford's corollary The following corollary can be found at page 653 of "Introduction to algorithms (3rd edition)"

Corollary 24.3
Let $G = (V, E)$ be a weighted, directed graph with source vertex $s$
and a weight function $w: E \to \mathbb{R}$. Then, for each vertex $v
> \in V$, there is a path from $s$ to $v$ if and only if BELLMAN-FORD
terminates with $v.d < \infty$ when it is run on $G$.

I have an intuition for the corollary and would formulate its proof as following:
$\rightarrow$: Suppose there are paths from $s$ to $v$, we call the shortest path $p$. The path $p$ is shortest and therefore simple and hence has at most $|V| - 1$ edges. Each edge of the path $p$ will be relaxed by Bellman-Ford, an operation which will only decrease $v.d$. Therefore we can concluse, that $v.d < \infty$ after the algorithm terminates.
Another argument may also include the "Path-relaxation property", which states $v.d = \delta(s, v) < \infty$ after relaxations of all edges of $p$.
$\leftarrow$: Suppose there is no path from $s$ to $v$ but Bellman-Ford terminates with $v.d < \infty$. This would be a contradiction with "No-path property", which states $v.d = \delta(s, v) = \infty$.
I am self-studying the book and there is a lack of feedbacks from tutor, so my question is: would my proof be sufficient in this case?

I think your proof is correct, but there are 2 things that I would like to comment:

I think that when you are proving the $\rightarrow$ direction and you say:

"Each edge of the path $p$ will be relaxed by Bellman-Ford, an operation which will only decrease $v.d$. Therefore we can conclude, that $v.d < \infty$
after the algorithm terminates."

there is an assumption that a call to RELAX will necessarily decrease $v.d$. But this is not necessarily true, as a call to RELAX can leave $v.d$ untouched. So, you would need to prove that in BELLMAN-FORD there would be a call to RELAX that necessarily decreases $v.d$.
The alternative argument you are proposing (use the "Path-relaxation property") would work fine here, though.

Since this is a corollary, I think the authors expected you to use the previous Lemma to solve it (of course, solving it via a different reasoning is ok too).
In this case, we have Lemma 24.2:

Lemma 24.2
Let $G = (V, E)$ be a weighted, directed graph with source $s$ and weight function $w: E \rightarrow \mathbb{R}$, and assume that $G$ contains no negative-weight cycles that are reachable from $s$. Then, after the $|V| - 1$ iterations of the for loop of lines 2-4 of BELLMAN-FORD, we have $v.d = \delta(s, v)$ for all vertices that are reachable from $s$.

We can use it to prove the corollary:
$\rightarrow$: If there is a path from $s$ to $v$, by Lemma 24.2, we have $v.d = \delta(s, v)$, where $\delta(s, v)$ (the shortest path weight from $s$ to $v$) is less than $\infty$ since there is a path.
$\leftarrow$: If BELLMAN-FORD terminates with $v.d < \infty$ when it is run on $G$, by Lemma 24.2 we have that $\delta(s, v) = v.d < \infty$, which by definition of $\delta$ means that there is a path from $s$ to $v$.


Quick Sort with first element as pivot I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point.

I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot S[1] (17) into its appropriate position.

Example: [17, -10, 7, 19, 21, 23, -13, 31, 59].

^# = pivot
^ pointer

My understanding:

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                               ^

Comparison 1. No swap.

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                           ^

Comparison 2. No swap.

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                      ^

Comparison 3. Swap.

-13, -10, 7, 19, 21, 23, 17, 31, 59
                     ^   ^#

Comparison 4. Swap.

-13, -10, 7, 19, 21, 17, 23, 31, 59
                 ^   ^#

Comparison 5. Swap.

-13, -10, 7, 19, 17, 21, 23, 31, 59
             ^   ^#

Comparison 6. Swap.

-13, -10, 7, 17, 19, 21, 23, 31, 59
          ^  ^#

Comparison 7. No swap.

 -13, -10, 7, 17, 19, 21, 23, 31, 59
       ^      ^#

Comparison 9. No swap.

-13, -10, 7, 17, 19, 21, 23, 31, 59
  ^          ^#

Comparison 10. No swap.

Is this how it works? Would it take 10 comparisons and 4 swaps to move pivot S[1] (17) into the correct position?

Quicksort doesn't swap the pivot into its correct position in that way, but it lies on the hypothesis that each recursive call sorts the sub-array and then merging sorted sub-arrays would provide a completely sorted array:

let $V$ be the array to sort
$pivot \leftarrow pick()$ picks a pivot, in your case it's always the first element in $V$
let $V_{\lt}$ be a list $s.t. \forall a \in V_{\lt} \  a \in V \ \wedge \ a \lt pivot$
let $V_{=}$ be a list $s.t. \forall a \in V_{=} \  a \in V \ \wedge \ a = pivot$
let $V_{\gt}$ be a list $s.t. \forall a \in V_{\gt} \  a \in V \ \wedge \ a \gt pivot$

Quicksort then proceeds recursively calling itself on $V_{\lt}$ and $V_{\gt}$, thus assuming to get those two back with their values sorted.

The final step is then to return the concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$, in this order.

Providing a numerical example:

$V = [17, -10, 7, 19, 21, 23, -13, 31, 59]$

Steps:

Initial run

$pivot = 17$

$V_{\lt} = [-10, 7, -13] $

$V_{=} = [17] $

$V_{\gt} = [19, 21, 23, 31, 59] $
Recursion on $V_{\lt} = [-10, 7, -13] $

$pivot = -10$

$V_{\lt} = [-13] $

$V_{=} = [-10] $

$V_{\gt} = [7] $

skips recursion on $V_{\lt}$ and $V_{\gt}$ since they're of size 1, thus already sorted

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[-13, -10, 7]$
Recursion on $V_{\gt} = [19, 21, 23, 31, 59] $

$pivot = 19$

$V_{\lt} = [] $

$V_{=} = [19] $

$V_{\gt} = [21, 23, 31, 59] $
Recursion on $V_{\gt} = [21, 23, 31, 59] $

$pivot = 21$

$V_{\lt} = [] $

$V_{=} = [21] $

$V_{\gt} = [23, 31, 59] $
Recursion on $V_{\gt} = [23, 31, 59] $

$pivot = 23$

$V_{\lt} = [] $

$V_{=} = [23] $

$V_{\gt} = [31, 59] $
Recursion on $V_{\gt} = [31, 59] $

$pivot = 31$

$V_{\lt} = [] $

$V_{=} = [31] $

$V_{\gt} = [59] $

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[31, 59]$
Back from recursion in 5.

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[23, 31, 59]$
Back from recursion in 4.

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[21, 23, 31, 59]$
Back from recursion in 3.

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[19, 21, 23, 31, 59]$
Back from recursion in 2.

returns $V_{sort}$ = concatenation of $V_{\lt}$, $V_{=}$ and $V_{\gt}$ = $[-13, -10, 7, 21, 23, 31, 59]$

As you can see, from the step 3 and onwards, the chosen pivot isn't an optimal one, since there only are elements at its right, preventing the algorithm to run in optimal time of $\mathcal{O}(n log_2 n)$

EDIT: following Kai's comment, I fixed the definitions of $V_{\lt}$, $V_{=}$ and $V_{\gt}$. I also acknowledge this is the simpler and less efficient Lomuto's partition.


How to present ping data from ICMP timestamp The ICMP timestamp protocol is useful for determining which path — forward or reverse — is contributing to the jitter on the line.

In an ideal world, all computers would have an excellent ntpd, and time accuracy of about 1ms (the granularity of ICMP timestamp) should not be a problem:

0       145.5   146 = 75 + 71
1       142.7   142 = 72 + 70
2       140.7   140 = 70 + 70
3       146.7   146 = 76 + 70
4       148.3   148 = 77 + 71
5       157.5   157 = 87 + 70
6       167.1   167 = 96 + 71
7       166.3   166 = 95 + 71
8       167.7   167 = 97 + 70
9       159.0   159 = 88 + 71

However, in reality, as per https://stackoverflow.com/questions/20172028/awk-hping-print-difference-between-icmp-originate-receive/20186781#20186781, the data could be like this:

0       165.9   166 = -142113 + 142279
1       160.2   160 = -142118 + 142278
2       155.2   155 = -142122 + 142277
3       156.5   156 = -142121 + 142277
4       164.7   165 = -142112 + 142277
5       164.4   164 = -142111 + 142275
6       160.9   161 = -142114 + 142275
7       158.1   158 = -142117 + 142275
8       155.6   156 = -142119 + 142275
9       143.0   143 = -142131 + 142274
10      153.2   153 = -142120 + 142273
11      157.1   157 = -142115 + 142272
12      158.3   158 = -142114 + 142272
13      148.6   149 = -142123 + 142272
14      144.3   144 = -142127 + 142271
15      145.3   145 = -142125 + 142270

Which still shows that only one path is responsible for the jitter, since only one value jumps up and down randomly, whereas the other one is decreasing monotonically (probably due to an actively-running ntpd, which is correcting the time as we ping).

Another example could be less wrong-looking of the time not being synchronised, say:

0       165.9   166 = -113 + 279

Or, better yet:

0       165.9   166 = 7 + 159

Or, say, still wrong by some 10ms to 40ms, on a landline link from Alberta to Vogtland, but much less obvious:

0       165.9   166 = 59 + 107

How to make scientific sense of this data, for it to be easily presentable, and not blatantly wrong?

Feel free to assume to have between 10 to 1000 measurement points, measured over a couple of seconds or minutes.

You ask:

  How to make scientific sense of this data, for it to be easily presentable, and not blatantly wrong?

Well, the bottom line is: this data is blatantly wrong.  If your measurement method says that the latency on some link is negative 113 ms, there is something wrong with your measurement method.

Right now, you've got a "garbage in, garbage out" situation.  The data you've got does not survive simple cross-checks, which tells you that your measurement methods has problems.  What you need to do at this point is go back to the drawing board and devise a better measurement method.  For instance, maybe you can find some way to measure the offset between your clock and the remote machine's clock more precisely, and then adjust for that offset.

But in any case, it's pretty clear that the current measurement method isn't adequate on its own.


How to prove/disprove distribution of division over union How can I prove distribution of division over union in relational algebra, i.e. the following:

$$(R \cup S) / X \overset{?}{=} (R / X) \cup (S / X)$$

Ok so i figured it out. Let $L_1$, $L_2$ be relation sets where $L_2$ is a subset of $L_1$. We know $R$ and $S$ are subsets of $L_1$ and $X$ is a subset of $L_2$. Since we do not know whether $X$ is a subset of $R$ and $S$, we can give the following counter example:

Suppose
$$\begin{align*}
  L_1 &=(1,2,3,4,5,6,7,8), \\
  R &= (1,2,3,4), \\
  S &= (5,6,7)\; \text{and}\\ X &= (1,3).
\end{align*}$$
Then, $(R \cup S) / X = (2,4,5,6,7)$ whereas $R / X$ and $S / X$ are illegal.


Why is the running cost of SQUARE-MATRIX-MULTIPLY-RECURSIVE in CLRS $\Theta(n^3)$ instead of $\Theta(n^2)$? I am reading Introduction to Algorithm CLRS (3rd ed.), Chapter 4 (Divide and Conquer), page 78, and am not sure why the explanation of why SQUARE-MATRIX-RECURSIVE algorithm takes $Θ(n^3)$.

  Combining equations (4.15) and (4.16) gives us the recurrence for the running time of SQUARE-MATRIX-MULTIPLY-RECURSIVE:
  $$
T(n) = \begin{cases}
   Θ(1) &\text{if } n=1 \\
   8T(n/2) + Θ(n^2) &\text{if } n>1
\end{cases}
$$
  As we shall see from the master method in Section 4.5, recurrence (4.17) has the solution $T(n) = Θ(n^3)$.

The part that I don't understand is that why $8T(n/2) + Θ(n^2)$ becomes $Θ(n^3)$. I only see $n^2$ in the term but why would it become $n^3$?

What you are asking is indeed answered in section 4.5 of CLRS using a methodology described later in the book. I will post here an alternative answer you should be able to understand with your current knowledge.

Think of the recursive relationship
 $$T(n) = 8T(\dfrac{n}{2}) + cn^2.$$

Let us first see what happens if we substitute $T(\dfrac{n}{2})$

$$T(n) = 8 (8T(\dfrac{n}{4}) + c (\dfrac{n}{2})^2) + cn^2 = 8^2 T(\dfrac{n}{4}) + 8c(\dfrac{n}{2})^2 + cn^2.$$

By substituting $T(\dfrac{n}{4})$ we get:

$$T(n) = 8^2 (8T(\dfrac{n}{8}) + c (\dfrac{n}{4})^2) + 8c(\dfrac{n}{2})^2 + cn^2 = 8^3 T(\dfrac{n}{8}) + 4cn^2 + 2cn^2 + cn^2.$$

It becomes obvious that in the general case after $k$ iterations we have:

$$T(n) = 8^k T(\dfrac{n}{2^k}) + cn^2(2^{k-1} + 2^{k-2} + \dots + 2 + 1).$$

Let $n = 2^k$.

Notice that $k = \log_2n \Rightarrow8^k = 8^{\log_2n} = 2^{3\log_2n} = 2^{\log_2n^3} = n^3$. By substituting $k = \log_2n$ in the previous relationship we get:

$$T(n) = n^3T(1) + cn^2 (\dfrac{1}{2} + \dfrac{1}{4} + \dots + \dfrac{1}{n})n.$$

$T(n) = n^3 T(1) + cn^3$, therefore you have $\Theta (n^3)$.


In an M/M/1 Queue, what does exponential distribution of service time mean? I was reading about the M/M/1 Queue and that we assume new customers arrive according to a Poisson distribution, and each customer takes an amount of time to service that is drawn from an exponential distribution?

I understand what it means to have an arrival rate based on Poisson distribution - if an average of 10 come per hour, you'll have 9 a few times, 6 very infrequently, 11 pretty often etc - but what does it mean that service is exponential?

Does this mean that as you serve more customers, the average time it takes to service them rises exponentially? Wouldn't the system crash soon after a few customers?

In an exponential distribution, the probability is DECREASING exponentially -- hence little risk that service time will grow. On the contrary, the mean service time is fixed, at the inverse of the rate.
This distribution is actually very rare in practice, but is chosen because it is Markovian:
the probability to terminate servicing a client does not depend on the past, and in particular on how much time you already spent servicing that client. That yields very nice mathematical properties.


Clique vs Complete Graph Is there a difference between a complete graph and a clique topology? As far as I understand, both refer to graphs in which every possible edge between any two vertices is present. Is there a subtle difference between these two concepts?

A complete graph is a graph with every possible edge; a clique is a graph or subgraph with every possible edge. That is, one might say that a graph "contains a clique" but it's much less common to say that it "contains a complete graph".


How does Rabin fingerprint finds breakpoints (chunk boundary)? I was reading up on chunking and found Rabin fingerprinting is also used to break files into chunks. After reading about this algorithm, I understood how rolling hash is computed using Rabin fingerprint. This is explained almost everywhere. What I don't get is how in Rabin fingerprinting, we know to end one chunk here and start another? And how does insertion doesn't affect original chunks? Some sources mention the following, which I didn't get. (Although it's given with reference to LBFS, I think for de-duplication also chunking will be done in similar way.)

When the low 13 bits of the fingerprint are zero LBFS calls those 48 bytes a breakpoint and ends the current block and begins a new one. Since the output of Rabin fingerprints are pseudo-random the probability of any given 48 bytes being a breakpoint is 2^{-13}. This has the effect of shift-resistant variable size blocks.

We are checking if low 13 bits are 0 or not, because fingerprint is basically a remainder, after dividing by an irreducible polynomial? But even then, how does inserting something in chunk-1, still makes sure chunking will be shift-resistant?

Thanks in advance for the help!

Edit : I am talking about application of Rabin fingerprinting in breaking files into chunks for de-duplication. (Not for string search, I understood that one)

I know I'm very late to this question, but I want to try and provide an answer for anyone who stumbles across this as I have. I went and deciphered the original paper by Michael Rabin, and found that the Rabin-fingerprint was designed to NOT be shift-resistant. In his paper (http://www.xmailserver.org/rabin.pdf) he used the fingerprint to detect any data-modification in files as the fingerprint would be different if any bit was changed. So, I have no idea why the LBFS paper is claiming to use fingerprinting for dynamic chunk borders because that's exactly what it is not meant for. Look for a different rolling hash if you want shift-resistant chunk borders. That being said fingerprinting would be a great way to check whether two chunks are the same or not.


Why is LTL Model Checking in PSPACE Given a LTL formula $\phi$ and a transition system $T$ we have to do following steps:

Build a (non deterministic) Büchi automaton for $T$
Build a (non deterministic) Büchi automaton for $\phi$
Compute the intersection of these automatons and check for emptyness

Step 1 can be done in $\mathcal{O}(|T|)$ time and space. I also know and understand that step 3 requires $\mathcal{O}(log^2n)$ space. But what about step 2? The size of the resulting Büchi Automaton from a LTL formula can be exponential in $|\phi|$. Writing that down requires more then polynomial space. So what am I missing here?

Do you may have any papers or books I could read on this topic?

It is correct that writing the Buchi automaton to memory takes exponential space.....which is why you don't do that.

The construction for the Buchi automaton is however very regular and can be done in a forward manner. This allows you to construct it on-the-fly while you search for an accepting lasso in the product between the Buchi automaton and $T$.

In this way, you can find an accepting lasso in NPSPACE (it is exists): you build a Turing machine that builds the product on-the-fly, searches for a lasso by non-deterministically guessing which transition in the product to take, and non-determinstically guesses the lasso knot to store (which, w.l.o.g., could also be the required accepting state). If it finds a path to such a knot and then a path from the knot back to the knot, you know that there is a word in the product.

To make this algorithm always terminate, you also have a counter to keep track of the number of transitions observed so far. If it exceeds two times the size of the product, then the algorithm aborts with a "no" answer. Such a counter also only needs space polynomial in the size of the LTL formula.

Since PSPACE=NPSPACE, it follows that you only need polynomial space for such a Turing machine.


Substitution for Landau's O notation formula I found the following description when I was reading a paper on computational complexity theory.

  This can be done ... in time 2n･poly(logs,n)+2O(logs)c. For s≤2no(1), the runtime is 2n･poly(n).

I know this means substituting s≤2no(1) for 2n･poly(logs,n)+2O(logs)c results in 2n･poly(n), but I don't know how this is done. So please tell me the calculation process.

First let us notice that $\log s = n^{o(1)} = o(n)$, and so $\mathit{poly}(\log s, n) = \mathit{poly}(n)$. This shows that the first summand is $2^n \mathit{poly}(n)$.

Next, since $\log s = n^{o(1)}$, also $O(\log s) = n^{o(1)}$ (since constants are $n^{o(1)}$) and $O(\log s)^c = n^{o(1)}$ (since a constant multiple of $o(1)$ is also $o(1)$), hence the second summand is $2^{n^{o(1)}} = o(2^n)$. So the first summand is more significant.


Is an $\mathcal{O}(n\times \text{Number of clusters})$ clustering algorithm useful? I am a physicist, with little formal training in computer science - please don't assume I know even obvious things about computer science!

Within the context of data analysis, I was interested in identifying clusters within a $d$-dimensional list of $n$ data-points, for which the dimensionality $d$ could be $\sim100$, whilst the number of data-points could be $\sim 1,000,000$, or perhaps more.

I wanted the points with a cluster to be close together, with distance measured in the Euclidean manner,
$$
d(\vec x,\vec y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2}
$$
As long as the clustering was reasonably accurate, I wasn't bothered if the exactly correct result was obtained. i.e. if of my $\sim1,000,000$, $\sim1,000$ points were wrongly categorized, it wouldn't matter much.

I have written a short algorithm that can perform typically at $\mathcal{O}(n)$ (from trials of up to $n\sim5,000,000$ and some theoretical analysis) and worst-case $\mathcal{O}(n^2)$ (from my theoretical evaluation of the algorithm). The nature of the algorithm sometimes (but not always) avoids the so-called chaining problem in clustering, where dissimilar clusters are chained together because they have a few data-points that are close.

The complexity is, however, sensitive to the a priori unknown number of clusters in the data-set. The typical complexity is, in fact, $\mathcal{O}(n\times c)$, with $c$ the number of clusters.

Is that better than currently published algorithms? I know naively it is a  $\mathcal{O}(n^3)$ problem. I have read of SLINK, that optimizes the complexitiy to $\mathcal{O}(n^2)$. If so, is my algorithm useful? Or do the major uses of clustering algorithms require exact solutions?

In real applications is $c\propto n$?, such that my algorithm has no advantage. My naive feeling is that for real problems, the number of "interesting" clusters (i.e. not including noise) is a property of the physical system/situation being investigated, and is in fact a constant, with no significant dependence on $n$, in which case my algorithm looks useful.

To answer your last question: In real problems, the number of clusters $c$ is usually much less than $n$.

To compare to other algorithms, the running time of a naive implementation of the standard $k$-means algorithm is $O(ncdt)$ (here your $c$ is often called $k$, so $c=k$, and $t$ is the number of iterations needed for $k$-means to converge; $t$ is often much smaller than $n$ and roughly a small constant, but certainly not always).  There are ways to speed it up further.  It tends to be very fast in practice.

For high-dimension spaces, such as you are working in, one can also apply various dimension-reduction techniques on all the values, and then do cluster the reduced-dimension values.  This sometimes gives additional performance improvements.

To answer your first question: We can't tell you whether your algorithm is useful if you don't show us the algorithm.  Sorry, but that question just isn't well-suited for this site.  Some questions aren't, no matter how much you'd love to know the answer.

Perhaps you'd like to ask a new question about what is the state of the art in clustering for Euclidean metrics, for some class of parameters and some distribution on the inputs.  Except... make sure you go do your research first.  There's a lot that has been written on the subject of clustering, so go read about standard clustering algorithms first, and then make sure to tell us what research you've done when you ask the new question.  (In fact, you probably should have done that for this question, too...)


Kosaraju's Algorithm-Strongly connected components In Kosaraju's Algorithm, using first dfs (traversing on reverse graph) we calculate finishing time of nodes, and then traverse (actual graph) in reverse order of finishing times.
why not without reversing graph, using first dfs (traversing on actual graph) we calculate finishing time of nodes, and then traverse (actual graph) in actual order of finishing times.
In case my proposed method is wrong please provide me with a counter example.

What separates theoretical computer science from more applied areas within computer science is the notion of proof. If an algorithm claims to do something, we want proof that it does so, preferably a mathematical proof. (In rare occasions, experiments are also accepted.) We work under the maxim an algorithm doesn't work unless it is proved to work, whereas you seem to be working under the maxim an algorithm works unless we can find a counterexample.

For these reasons, I don't find it a good use of my time to find a counterexample. If you did want to find a counterexample yourself, there are several things to try. First, you can try a few random graphs; often this works. Second, you can try to concoct a parametric situation and determine parameters that defat your algorithm; this seems harder to apply in your case since your edges are not weighted, and so the parameters are too discrete. Third, you can try to prove that your algorithm works, fail at some step, and produce a counterexample as part of the process. Fourth, you can play with your algorithm on several graphs until you get an intuitive understanding of what it does, and given this understanding try to construct a counterexample. Fifth, if you really believe that the algorithm doesn't work but can't use any of the preceding method, treat it as a research project and use your research skills to construct a counterexample.

Kosaraju's algorithm is that way that it is for a reason. If a simpler or more intuitive algorithm worked, probably by now people would have discovered it, and it would be known. The fact that we still teach Kosaraju's algorithm suggests that similar but simpler algorithms don't work. That's why I'm pretty sure that your algorithm doesn't work, even without reading it. Of course, I can be wrong. To prove me wrong, all you have to do is to prove that your algorithm works.


Range update + range query with binary indexed trees I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates.

I found the following sources:

http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree
http://apps.topcoder.com/forums/?module=Thread&threadID=756271&start=0&mc=4#1579597

But even after reading through all of them I could not understand what the purpose of the second binary indexed tree is or what it does.

Could someone please explain to me how the binary indexed tree is modified to handle these?

Suppose you had an empty array:

0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

And you wanted to make a range update of +5 to [3..7]:

0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)

How could you store the desired cumulative sums using 2 binary indexed trees?

The trick is to use two binary indexed trees, BIT1 and BIT2, where the cumulative sum is calculated from their contents.  In this example, here's what we'd store in the the two trees:

0   0   0   5   5   5   5   5   0   0  (BIT1)
0   0   0  10  10  10  10  10 -25 -25  (BIT2)

To find sum[i], you compute this:

sum[i] = BIT1[i] * i - BIT2[i]

For example:

sum[2] = 0*2 - 0 = 0
sum[3] = 5*3 - 10 = 5
sum[4] = 5*4 - 10 = 10
...
sum[7] = 5*7 - 10 = 25
sum[8] = 0*8 - (-25) = 25
sum[9] = 0*9 - (-25) = 25

To achieve the desired BIT1 and BIT2 values for the previous range update, we do 3 range updates:

We need to do a range update of +5 to indices 3..7 for BIT1.
We need to do a range update of +10 to indices 3..7 for BIT2.
We need to do a range update of -25 to indices 8..9 for BIT2.

Now let's do one more transformation.  Instead of storing the values shown above for BIT1 and BIT2, we actually store their cumulative sums.  This lets us do the 3 range updates above by making 4 updates to the cumulative sums:

BIT1sum[3] += 5
BIT1sum[8] -= 5
BIT2sum[3] += 10
BIT2sum[8] -= 35

In general, the algorithm to add a value v to a range[i..j] would be:

BIT1sum[i]   += v
BIT1sum[j+1] -= v
BIT2sum[i]   += v * (i-1)
BIT2sum[j+1] -= v * j

where the += and -= syntax simply means to update the BIT cumulative sum data structure with a positive or negative value at that index.  Note that when you update the BIT cumulative sum at an index, it implicitly affects all indices to the right of that index.  For example:

0 0 0 0 0 0 0 0 0 0 (original)

BITsum[3] += 5

0 0 0 5 5 5 5 5 5 5 (after updating [3])

BITsum[8] -= 5

0 0 0 5 5 5 5 5 0 0 (after updating [8])

Fenwick trees store sums in a binary tree.  It is easy to do the updates shown above to a Fenwick tree, in $O(\log n)$ time.