title: Vertex Cover, Hardness of Approximation

text:
# Question
Title: Vertex Cover, Hardness of Approximation
In chapter of Hardness of Approximation in *V. Vazirani's* book it says:

> For establishing a hardness of approximation result for, say, the vertex cover problem, PCP theorem is used to show the following polynomial time reduction. It maps an instance φ of SAT to a graph G = (V,E) such that
>
> • if φ is satisfiable, G has a vertex cover of size ≤ 2/3\*|V |, and
>
> • if φ is not satisfiable, the smallest vertex cover in G is of size \> α· 2/3\*|V |,

Next line it claims:

> **Claim 29.1** As a consequence of the reduction stated above, there is no polynomial time algorithm for vertex cover that achieves an approximation guarantee of α, assuming P ≠ NP. (α\>1)

I couldn't understand that claim, while in previous chapters it says **Vertex Cover** have 2-approximation algorithm (with Maximal matching).

Could anyone explain what does it means? How it obtained 2/3\*|V|? and Why it said there is no α approximation while in previous chapters it proposed ones?

# Answer
We can proof this claim by contradiction. If there exists an α-approximation algorithm for Vertex Cover, we will be able to use it for solving SAT problem in polynomial time and it's a contradiction by giving P≠NP.

We assume that there exists a gap introducing reduction that converts an instance of SAT to an instance of Vertex Cover giving:

• if φ is satisfiable, OPT(VC) ≤ 2/3 * |V|, and

• if φ is not satisfiable, OPT(VC) \> α * 2/3 * |V|.

We can use this reduction and convert φ to I(VC) in polynomial time, then use the α-approximation algorithm for Vertex Cover in polynomial time and calculate objective function value (we call it *f*) for it.

As we know value of *f* stands between two bounds:

OPT(VC) ≤ *f* ≤ α\*OPT(VC)

After that, we can use *f* to make a decision about φ satisfaction state:

If *f* ≤ α * 2/3 * |V|, then yes, else no.

We claim that if *f* is less than α * 2/3 * |V|, φ should be satisfiable because if φ isn't satisfiable, *f* can't be less than α * 2/3 * |V| which is lower bound to OPT(VC) (according to reduction assumptions) and objective function value can't be less than optimum.

Also we claim that if *f* is greater than α * 2/3 * |V|, φ shouldn't be satisfiable because if φ is satisfiable, it violates the approximation inequality. (*f* ≤ α\*OPT(VC))
> 3 votes

# Answer
Yeah, that is a bit confusing. The bottom line is that you've misunderstood the surrounding context, and consequently, you've misunderstood what the claim is saying.

The previous sentence before Claim 29.1 is basically saying: "Suppose there exists a reduction from SAT to vertex cover with a particular property based on $\alpha$." Then, Claim 29.1 is saying "If such a reduction exists, then you can't approximate vertex cover to approximation ratio $\alpha$." Whether such a reduction exists will depend on the particular value of $\alpha$. Claim 29.1 is not saying that there is no approximation for vertex cover for any $\alpha \> 1$; it's just saying there's no approximation for $\alpha$, if there's a gap-preserving reduction with parameter $\alpha$. Thus, the claim will apply to some values of $\alpha$, but not necessarily all values of $\alpha$.

This becomes particularly clear once you read the proof of Claim 29.1 (which immediately follow the statement of the claim). I agree that the wording in the book is a bit confusing and could be clearer. Fortunately, in this case you can figure out what was meant from context by reading the proof of the claim.

Here's what is true:

* Vertex Cover has a 2-approximation.
* There is no $\alpha$-approximation for $\alpha \le 1.3606$ (unless P=NP).
* No one knows of an $\alpha$-approximation with $\alpha\<2$ (though we don't have a proof that it doesn't exist; this could always represent a lack of imagination on our part).

The claim "Vertex Cover has no $\alpha$-approximation for any $\alpha\>1$" is false; for instance, it does have a $\alpha$-approximation for $\alpha=2$, using maximal matching (as you said).

Ultimately there is no contradiction among all of this, and it doesn't contradict Claim 29.1, once you understand what Claim 29.1 is trying to say.
> 2 votes

---
Tags: np-complete, np-hard, approximation
---


# Question
Title: Create a schedule from overlapping events
Let me first sketch my situation. I have a list of events with time slots, and I need to generate a schedule from these. We can assume that I have already validated and ordered the events from lowest to highest priority, so I will have a list like:

```
Starts  Ends   Event
---------------------------------
   0     12    Background
   2     3     Event A
   4     7     Event B
   6     9     Event C
   6     10    Event D

```

and I want to generate from this the following schedule

```
Starts  Ends   Event
---------------------------------
   0     3     Background
   2     3     Event A
   3     4     Background
   4     6     Event B
   6     10    Event D
   10    12    Background

```

Of course there is the naive O(*n*²) algorithm

```
schedule: []

for each currentEvent in events:

   piecesToAdd = [currentEvent]
   for each eventSoFar in schedule:
     determine the overlap
     modify eventSoFar and piecesToAdd to remove overlap

   append piecesToAdd to schedule

```

but I was wondering if there is a more efficient way.

If all the time slots are integers, I thought I could just fill a big array at the start with

```
Starts  Ends   Event
---------------------------------
   0     1     Background *
   1     2     Background *
   2     3     Background *
   3     4     Background
   ...

```

but in general I do not want to (and probably cannot) assume that this will be the case. Still, if non-integer time slots are the exception rather than the rule, it may be better to start out like this and split the predefined slots only when needed. But then I need a postprocessing step to consolidate all consecutive slots with the same event, *i.e.* collapse the lines marked * in the example above into a single "Background: starts 0, ends 3" entry.

It looks like this will be scripted in PHP so any language-specific tricks are welcome, but I am mainly curious about the most efficient way to program this in general.

# Answer
> 1 votes
One idea would be to construct an additional list of so-called 'changes'. So for your data it would look like this:

```
Time   Change
0      Background Start
12     Background End
2      Event A Start
3      Event A End
4      Event B Start
...

```

Then sort by 'Time' O(n log n)

```
Time   Change
0      Background Start
2      Event A Start
3      Event A End
4      Event B Start
6      Event C Start
...

```

Construct an empty balanced binary search tree T. Loop over the changes in order, when a change is an 'event start' add that event to T, when the change is an 'event end' remove it from T. At each change determine the highest priority event and do that until the next change (If it is not different than your last event, in which case just keep doing it).

Each of the tree operations is log n, and are done n times so this is all O(n log n). Most languages have some sort of balanced tree that could be used. You could encode the event changes as integers which represent the priority, positive meaning add this event, negative meaning remove this event. This works with non-integer times.

---
Tags: algorithms, runtime-analysis
---


# Question
Title: Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets
I am trying to generate a list of digit triplets to specify stimuli in an auditory (speech-in-noise) perception experiment. Each triplet has to have three different digits (i.e., no repetition within triplets). I have recordings of digits 0-9, recorded in each triplet position (i.e., I have 30 digits, 0 in 1st position, 0 in 2nd position, 0 in 3rd position, 1 in 1st position, 1 in 2nd position, etc...). This is for a homogenization task, i.e., a task for figuring out the signal to noise ratio (SNR) for each digit in each position so that the level of individual digits can be adjusted upward or downward to make them equally intelligible at a fixed noise level.

In the homogenization task, stimuli will be presented at 10 SNRs, and I want each digit in each position to be presented four times at each SNR, but in different triplets. Hence, I want 4 x 10 x 10 triplets total. (The four repetitions is somewhat arbitrary, but it's based on previous work, and 400 trials works out nicely with respect to the amount of time listeners will spend doing the task.)

There are 720 total triplets. I use Python, so it's easy to get the full list with:

```
all_triplets = list(itertools.permutations(np.arange(10),3))

```

I'm finding it very difficult to get a subset of 400 of the 720 possible triplets such that each digit occurs in each position exactly 40 times. That is, I want 400 triplets such that

```
np.sum(triplets[:,c]==d) == 40

```

is `True` for all `c` in `[0,1,2]` and all `d` in `[0,1,2,3,4,5,6,7,8,9]`, and with triplets a 400 x 3 numpy array containing the subset.

I think that such subsets exist, but I am not sure, since I haven't buckled down to try to work out the math (I may not have the ability to do so even if I do buckle down, and I *definitely* don't have the time to do so, regardless). I can't figure out how to construct any such subsets from scratch (I wrote some aggressively mediocre code to do this that kind of works sometimes) or to select the right elements from the full set (assuming there are some).

I wrote some less mediocre code to sample randomly from the full subset and score each subset based on how much it deviates from the 40-of-each-digit criterion, and I found a subset with these tallies (rows are triplet position, columns are digits):

```
[[43, 41, 39, 40, 37, 40, 42, 42, 37, 39],
 [43, 41, 39, 38, 41, 39, 44, 38, 40, 37],
 [43, 38, 40, 38, 38, 41, 42, 44, 39, 37]]

```

Of course, randomly sampling from approximately `1.92e+213` total subsets of size 400 from the 720 total set of triplets isn't terribly efficient.

So, is there a solution to this problem? A commenter on reddit's intuition is that this problem is NP-complete, but I don't know enough about the relevant math or computer science to have particularly strong intuitions about this possibility. Should I just be happy with the best solution I stumbled on?

# Answer
> 0 votes
You could try using integer linear programming (ILP). Use the following variables:

* We have a variable $x\_{ijk}$ for each triplet $ijk$, which is 1 if triplet $ijk$ is selected to be included in your set of 400, or 0 otherwise.
* We have a variable $y\_{ip}$ to count the number of times that digit $i$ appears in position $p$ among the selected triplets.

Now add constraints to capture all of your requirements:

* We want to select 400 triplets: $\sum\_{i,j,k} x\_{ijk} = 400$.
* We want each digit in each position to appear 40 times: $\sum\_{i,p} y\_{ip} = 40$.
* We want the $x$'s and $y$'s to be consistent:

$$\begin{align} y\_{i1} &= \sum\_{j,k} x\_{ijk}\\ y\_{j2} &= \sum\_{i,k} x\_{ijk}\\ y\_{k3} &= \sum\_{i,j} x\_{ijk} \end{align}$$

Finally, we require $0 \le x\_{ijk} \le 1$ and $0 \le y\_{ip} \le 1$ for all variables.

Now give the resulting system to an integer linear programming solver, and see if it can find a solution.

If it can't find a solution after a reasonable amount of time, your next step could be to find as small a subset as possible (not necessarily size 400, but hopefully not too much larger than 400). Thus, replace $\sum\_{i,p} y\_{ip} = 40$ with $\sum\_{i,p} y\_{ip} \ge 40$, and instead of the constraint $\sum\_{i,j,k} x\_{ijk} = 400$, ask the ILP solver to minimize the objective function $\sum\_{i,j,k} x\_{ijk}$. That will find a way to ensure each digit is presented at least as many times as desired, using as few trials as possible.

---
Tags: combinatorics, permutations, set-cover
---


# Question
Title: Strongly NP-hard problems and Dynamic Programming
Dynamic Programming seems to result in good performance algorithms for Weakly NP-hard Problems. Two examples are Subset Sum Problem and 0-1 Knapsack Problem, both problems are solvable in **pseudo-polynomial** time using Dynamic Programming. It turns out this is a pretty good result in most cases.

On the other hand, Strongly NP-hard Problems seem to be essentially exponential even by using Dynamic Programming. For example, the Multiple 0-1 Knapsack Problem (page 11).

Is this a true claim if I generalize my observations and state *Dynamic Programming is good for Weakly NP-hard Problems but it is not suitable for Strongly NP-hard Problems*?

# Answer
> 4 votes
You're generalizing too much from a small sample size. There is no guarantee that all weakly NP-complete problems can be solved using dynamic programming; I'd expect probably there are some that dynamic programming isn't much good for.

And, there is no guarantee that a strongly NP-hard problem will take exponential time to solve. There are NP-complete problems that can be solved faster than exponential time. (See also the exponential time hypothesis.)

Dynamic programming is just one algorithmic technique among many. There's nothing magical about it, and it's not a be-all and end-all. There are other algorithmic methods other than dynamic programming.

---
Tags: np-complete, dynamic-programming, np-hard
---


# Question
Title: Best combination of values pulled from a matrix
What is the fastest way to select $n$ values from an $n$ by $n$ matrix such that each value comes from a different row and column and the sum of those n values is minimized?

For example, given the matrix:

$$A=\begin{bmatrix}0 & 1 &5 \\1 & 4 & 3\\2 & 7 & 0\end{bmatrix}$$

The solution is $\\{A\_{1,2}, A\_{2,1}, A\_{3,3}\\}$, taking 1 from the first row, 1 from the second row, and 0 from the third row.

In the brute-force case, there are $n!$ possible solutions that have to be analyzed, so the ovreall running time is $O(n!)$, although are there any faster algorithms to solve this?

# Answer
> 2 votes
It looks like the assignment problem, and it could be solved in $\mathcal O(n^3)$ using the Hungarian algorithm. In your case the $A$ is the *cost matrix* and the sum you are looking for is *cost* in the terms of algorithm.

---
Tags: optimization, time-complexity, combinatorics, efficiency
---


# Question
Title: Deciding whether there exists a permutation of the entries of an $n \times n$ matrix that is magic
Given an array of $n^2$ integers, what is the most efficient way to determine whether any permutation of those integers can form a magic square? "Magic square" being an arrangement of those integers on a square grid such that all rows, columns and diagonals sum to the same value.

Note that this isn't asking how to test if a given arrangement is a magic square, which would be $O(n^2)$, but whether any possible square formed from the array is magic.

# Answer
> 1 votes
One approach is to use integer linear programming, and hope that an ILP solver will be able to find a solution. This will probably still be exponential in $n$ in the worst case, but it might be faster than enumerating all $n!$ solutions.

Here's more detail. Suppose we are given the integers $a\_1,a\_2,\dots,a\_{n^2}$. Let $M=(a\_1+\dots+a\_{n^2})/n$ be the magic constant of the magic square, so that every row, every column, and every diagonal needs to sum to $M$. Define zero-or-one integer variables $x\_{i,j,k}$, with the intended meaning that $x\_{i,j,k}=1$ means that the number $a\_k$ is placed in row $i$, column $j$. Then we have the inequalities

$$\begin{align\*} &\sum\_i a\_k x\_{i,j,k} = M\\ &\sum\_j a\_k x\_{i,j,k} = M\\ &\sum\_i a\_k x\_{i,i,k} = M\\ &\sum\_i a\_k x\_{i,n+1-i,k} = M\\ &\sum\_k x\_{i,j,k} = 1\\ &\sum\_{i,j} x\_{i,j,k} = 1. \end{align\*}$$

Then any feasible solution to these linear equalities will represent a valid magic square, so you can feed this to an off-the-shelf ILP solver and hope that it finds a solution for you. Probably it will fail (take forever) once $n$ gets large, but it might be effective if $n$ is small enough.

---
Tags: algorithms, algorithm-analysis, matrices
---


title: Unique SAT complexity clarification

text:
# Question
Title: Unique SAT complexity clarification
Unique SAT is defined as:

Given any SAT problem, does the SAT problem have exactly 1 solution?

As I understand it is co-NPHard. I am unclear how it is in co-NP

1. Assuming the problem has more than 1 solution, any 2 solutions can be a certificate of it being nonUnique. That part is coNP. Now, given a problem can be unsatisfiable, how do we get a certificate of no solution?
2. Its also said that an NP Oracle can solve this problem in polynomial time, but an NP Oracle just tells if the problem is satisfiable. So how is that possible?

Apologies but I have no clue regarding this version of SAT.

# Answer
1. To prove coNP-*hardness*, you don't need a certificate (that would be needed only if you wanted to show coNP-*completeness*). We just need some coNP-hard problem that reduces to UniqueSAT. UniqueSAT is indeed likely *not* in coNP.
2. You can ask an oracle *multiple* queries. You could begin by asking if the formula has a satisfying assignment (and, using self-reduction, find a solution if one exists). Perhaps you can then use further queries to determine if another solution exists?
> 5 votes

# Answer
1. You say it is coNP-hard. However, it tells nothing about whether it is contained in $\mathsf{coNP}$. It only says that it is **at least as hard** as any problem in $\mathsf{coNP}$.

This problem is known to be US-hard. $\mathsf{US}$ is not known to equal $\mathsf{coNP}$. It is only known to be a subset of $\mathsf{P^{NP}}$.

2. You can find a solution $p$, add a clause that excludes that solution and see if it's satisfiable.

Let's say the formula $\Phi(x,~y,~z,~w)$ has a positive assignment $x,~\overline y,~\overline z,~w$. Now you just solve $\Phi \land (\overline x\lor y\lor z\lor\overline w)$. If it's satisfiable, your formula is not unique-SAT.
> 5 votes

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Is every CPU instruction ultimately read and write?
Is every instruction ultimately all read or write instructions? So, how I imagine this is that every place where something can be stored can be either in a read or write state, including the CPU registers.

How this is controlled is by the control unit. Every instruction goes through the control unit which is connected to the control bus and flips memory locations (computer memory addresses) to either read or write state.

I understand that there is much more too this depending on what information the control bus can carry, but is this general overview correct in how data is moved about?

# Answer
> 6 votes
Ultimately, the state of the machine must change after executing every single instruction: if it did not, then the machine would be stuck in an infinite loop of executing the same instruction again and again. So, in that sense, *some* value in memory or in a register to be changed after each instruction is executed. At a minimum, this would be advancing the program counter.

If you want to count that as a "write" instruction then, yes, every instruction is a write instruction. However, then we would be in the situation that the phrase "write instruction" would mean exactly the same thing as "instruction", so it wouldn't be a useful piece of terminology. OK, so perhaps we want to define a write instruction to be one that directly alters a register or the main memory, where, by "directly alters", I'm excluding the automatic increment of the program counter. Well, OK, but that's not very useful, either, since every instruction I can think of does that, apart from a no-op. That wouldn't be a useful definition, either.

So, typically, "write instruction" is understood to mean an instruction that writes a value to some location in the main memory. Clearly not all instructions do that: for example, typical arithmetic instructions operate only on the registers. Similar arguments can be made for reading.

---
Tags: computer-architecture
---


# Question
Title: Neural Networks: Simulate the working of Dynamic Fixed Point representation of the weights on hardware
I am looking to implement a neural network on hardware using Verilog. I have completed and tested with floating point representation and a 20 bit fixed point representation. I want to further reduce the memory utilisation by using dynamic fixed point. I want to identify the less important weights, and assign them a smaller bit-width, while keeping the more important weights with a higher bit-length. How can I identify the more/less important weights? What I can think of is, reducing bit-width for all the small weights \[-0.001, 0.001\]. But isn't that like pruning? Thanks!

# Answer
> 1 votes
Start by reading the research literature on this topic. There's a large number of published papers that discuss how to quantize the weights or intermediate values used in deep learning. For instance, here are a few papers:

Start by reading them, and do a literature search to identify other relevant papers (e.g., read their related work section and find other earlier papers that are relevant; find papers that cite them using Google Scholar and read them; repeat).

You might also look at the Ristretto tool and this project.

---
Tags: neural-networks, floating-point, fixed-point
---


# Question
Title: Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn
I want to know if the recurrence equation $T(n) = 9T(\frac{n}{3}) + nlogn$, can or cannot be solved using master theorem.

At first, I naively went for $O(n^2)$ applying case 1 of master theorem. But then someone pointed out that $f(n)=nlogn$ and $n^{\log\_3 9}$ do not have polynomial difference and therefore master theorem cannot be used.

Then I found this proof for master theorem. Proof of case 1 is on page 2 of the document right on top of the page. The proof is based on the inequality:

$f(\frac{n}{b^i}) \leq(\frac{n}{b^i})^{\log\_a b -\epsilon}$

which allows the right side of the above inequality to replace f(n) and the proof goes on from there.

As I see it, the above inequality holds for $f(n)=nlogn$ so I think master theorem can be applicable here. I want to know if I am right and if not, why?

# Answer
Citing CLRS 3ed pp. 94-95:

> In the first case, not only must $f(n)$ be smaller than $n^{\log\_b a}$, it must be *polynomially* smaller. That is, $f(n)$ must be asymptotically smaller than $n^{\log\_b a}$ by a factor of $n^\epsilon$ for some constant $\epsilon \> 0$.
>
> Note that the three cases do not cover all the possibilities for $f(n)$. There is a gap between cases 1 and 2 when $f(n)$ is smaller than $n^{\log\_b a}$ but not polynomially smaller.

For your case we have: $$\begin{align} f(n) & = n \log n\\ n^{\log\_b a} & = n^2\\ \end{align}$$

We can then show: $$\begin{align} f(n) & = n \log n\\ & \< n^{2-\epsilon} & ^{\*}\text{for } \epsilon \< 1\\ & \< n^2 & \text{for } \epsilon \> 0\\ \end{align}$$

Then you see we can pick a $\epsilon$ value in the range $(0, 1)$ to get a polynomial difference of at least $n^\epsilon$ because: $$ f(n) \< n^{2-\epsilon} \< n^2$$

So yes, it is admissible, but your caution is noteworthy, because there are cases where the Master Theorem can **not** be applied in scenarios similar to this. One example would be the following:

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

You see $\frac{n}{\log n}$, while smaller than $n$, is not *polynomially* smaller, thus we cannot use the Master Theorem.

$^\*$: *A polylogarithmic function grows more slowly than any positive exponent*
> 1 votes

# Answer
You can apply the case one of master theorem

Case 1 : If $f(n) = \theta(n^c)$ where $c \< log\_ba$ then $T(n) = \theta(nlog\_ba)$. According to the recurrence equation $\theta(n^{1+x})=nlogn$ where $1+x=c$ and $c\<2$ because of the obvious reason $logn\<n$ hence $c\<log\_ba$. And the result of the equation will be $\theta(n^2)$.
> 0 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Algorithm to find k elements following the median in sorted order
I have the following problem:

Given an unsorted array A of size n, print the first k elements in A larger than its median.

Here's my approach to the problem:

```
     1. Create a minHeap and a maxHeap
     2. Iterate over elements in A // O(n)
        - if maxHeap.count < minHeap.count
             insert current element to maxHeap // O(log(n))
          else:
             insert current element to minHeap // O(log(n))
     3. if maxHeap.count < minHeap.count:
              median = minHeap.extractMin()
     4.  output k elements from minHeap  // O(klog(n))

```

This maintains a maxHeap of elements less than the median and a minHeap of elements greater than or equal to the median. But from my analysis, this seems to take `O(nlogn + k(log(n))` which is no better than sorting A first and grabbing A\[n/2:n/2+k\] in just `O(nlog(n) + k)`.

Now I have 2 questions:

1. Is my analysis tight? I am doubtful since the heaps have at most i elements in the ith iteration, not n.
2. Is there a better algorithm? Maybe something like O(n+klog(k))?

# Answer
> 3 votes
Answering your second question:

1. Find the median $m$, and partition the set into $L\_1 = \\{x | x \in S \wedge x \< m\\}$ and $L\_2 = \\{x | x \in S \wedge x \> m\\}$.
2. Find the $k$th largest element $x\_k$ in $L\_2$, and partition the set into $L\_2' = \\{x | x \in L\_2 \wedge x \leq x\_k\\}$ and $L\_3 = \\{x | x \in L\_2 \wedge x \> x\_k\\}$.
3. Sort $L\_2'$ and return.

Steps 1 and 2 take $O(n)$. Step 3 takes $O(k \log k)$. Total time $O(n + k \log k)$.

Note this assumes distinct values. Repeated values involves some edge case handling.

# Answer
> 3 votes
The k elements following the median can be retrieved in O(n). To get them in sorted order, an additional O(k log k) sorting step is required.

### Quickselect

From a high-level perspective, the Quickselect algorithm takes an array and an integer k. It then places the k-th largest number in the correct place, smaller numbers at smaller indices and larger numbers at larger indices. The lists of smaller and larger values are unordered. This is done in O(n) on average, or even O(n) in the worst case (median of medians pivot selection).

In pseudocode a Quickselect invocation could look like this:

```
> arr = [Array of 101 elements in random order]
> QuickSelect(arr, 50)
> arr
[lower 50 elem's][median][upper 50 elem's]
>

```

### k elements following the median

Just apply Quickselect twice. On the first pass, split the input sequence into median, upper and lower half. Then apply Quickselect on the upper half to split it into a list of k-1 lower values, the k-th-order statistic and some upper values.

Here's another pseudocode implemntation:

```
> arr = [Array of 101 elements in random order]
> QuickSelect(arr, 50)
> arr
[lower 50 elem's][median][upper 50 elem's]
> QuickSelect(upper, k)
> arr
[lower 50 elem's][median][elem's you're looking for][median+k][upper elem's]

```

# Answer
> 0 votes
You can find the median of an array using QuickSelect in O(n) in the average case.

Then you only need to grab the k smallest elements out of the second half of the array in sorted order.

---
Tags: algorithms, sorting, arrays, heaps
---


# Question
Title: What is the most efficient algorithm to get percentile distribution from histogram distribution?
So let's say you have a histogram distribution represented as an array where each element is equal to the number of numbers from the underlying data set that are equal to that element's index.

For example, if your underlying data had 5 0's, 18 1's, 11 2's, 0 3's, etc., then the array representing this distribution would look like... `histogramBinSizes = [5, 18, 11, 0, ...]`

Now, let's say you want to get the percentile distribution, which would be represented as an array where each element is equal to the number of numbers from the underlying data that fall in that percentile. What's the most efficient algorithm to get the percentile distribution array? (Maybe call this array `percentileBinSizes`)

To make the question easier, assume the numbers in the underlying data range from 0 to 100. That would make it so that `histogramBinSizes` and `percentileBinSizes` both have lengths of 101. Is there an even more efficient algorithm when this constraint is added?

I tagged this question with data structures as well as algorithms because I'm open to solutions that use a different data structure besides arrays. However, the input and output should still be arrays.

# Answer
First, compute the cumulative distribution. Suppose the input array is $A\[0..n-1\]$. You can compute the cumulative distribution as follows:

* Set $C\[-1\] := 0$.
* For $i:=0,1,2,\dots,n-1$, do: set $C\[i\] := C\[i-1\] + A\[i\]$.

After this, $C\[i\]$ contains a count of the number of values in the underlying data set that are $\le i$.

Now you can compute percentiles directly from the cumulative distribution. In particular, item $i$ is in the $\lfloor 100 C\[i\] / C\[n-1\] \rfloor$ percentile. So, the output array can be computed as

* Set $P\[j\] := 0$ for $j=:0,1,2,\dots,100$.
* For $i:=0,1,\dots,n-1$, do:
    + Set $j := \lfloor 100 C\[i\] / C\[n-1\] \rfloor$, and set $P\[j\] := P\[j\] + A\[i\]$.

Now $P\[j\]$ contains the number of values from the underlying data set that fall into the $j$th percentile. That was what you wanted to compute.

The running time is $O(n)$, where $n$ is the length of the input array. It seems unlikely you can build anything that's any faster than that, as the problem seems to require reading the entire input.
> 5 votes

---
Tags: algorithms, data-structures
---


# Question
Title: Algorithm for finding a matrix which satisfies certain constraints
Given a list of entries `entryList`, determine a 4x4 matrix of which you sum up the entries specified in `entryList` such that there is no other matrix for which the sum of entries specified in `entryList` is greater.

In other words: `entryList` specifies some entries, now imagine an arbitrary 4x4 matrix `m`, `entryList` tells us which entries of `m` should be summed up. Summing up a matrix with a given `entryList` means summing up all entries of the matrix which are specified in `entryList`. (the examples will make this clearer).

The 4x4 matrix must satisfy the following constraints:

1. All entries are integers between -10 and 10 (inclusively).
2. It must be symmetric, entry(x,y) = entry(y,x).
3. Diagonal entries must be positive, entry(x,x) \> 0.
4. The sum of all 16 entries must be 0.

**My question:**

Given such an `entryList` how do I compute the **maximal possible sum** (the actual matrix is not necessary) of any 4x4 matrix which satisfies the constraints above?

In other words: determine for which matrix the sum of entries specified in `entryList` is maximal, output that sum.

For example (Javaish code):

```
List<MatrixEntry> entryList = new ArrayList<>();

// for this example I arbitrarily chose entries (0,0), (1,2), (0,3), (1,1).
entryList.add(new Entry(0,0));
entryList.add(new Entry(1,2));
entryList.add(new Entry(0,3));
entryList.add(new Entry(1,1));

int result = computeMaxSum(entryList);

/* The result (maximal possible sum for any valid 4x4 matrix) is 40,
   it can be achieved by the following matrix:
    0.   1.   2.   3.
0.  10  -10  -10   10
1. -10   10   10  -10
2. -10   10    1   -1
3.  10  -10   -1    1       */

// Another example:

entryList = new ArrayList<>();

// for this example I arbitrarily chose entries (0,3), (0,1), (0,1), (0,4), ...
entryList.add(new Entry(0,3));
entryList.add(new Entry(0,1));
entryList.add(new Entry(0,1));
entryList.add(new Entry(0,3));
entryList.add(new Entry(0,3));
entryList.add(new Entry(0,2));
entryList.add(new Entry(1,2));
entryList.add(new Entry(2,1));
entryList.add(new Entry(3,1));
entryList.add(new Entry(1,3));
entryList.add(new Entry(2,3));
entryList.add(new Entry(3,2));

int result = computeMaxSum(entryList);

/* The result (maximal possible sum for any valid 4x4 matrix) is -4,
   it can be achieved by
   the following matrix:
    0.   1.   2.   3.
0.   1   10   10  -10
1.  10    1   -1  -10
2.  10   -1    1   -1
3. -10  -10   -1    1      */

```

**My current unfinished approach:**

The only thing that comes to my mind is solving it by brute force.

Some observations:

The equality `sumOfTheLowerLeftPart + sumOfTheUpperRightPart + diagonal = 0` holds since the sum of all entries must be 0.

It's also true that `sumOfTheLowerLeftPart = -1 * sumOfDiagonal/2` and `sumOfTheUpperRightPart = -1 * sumOfDiagonal/2`, since the matrix is symmetric and the diagonal entries must be positive.

So I want to maximize the value of entries in the matrix which are specified in `entryList`, the rest of the entries are irrelevant for the resulting sum and should be set such that the constraints on the matrix are satisfied. I start with the maximum possible assignment of values to entries specified by `entryList` (set all the entries to 10), then I check if I can fill out the rest of the entries such that my matrix satisfies all of the constraints. If it is possible to do so, we are done, output the sum of the entries, if it is not possible to fill out the rest such that the matrix satisfies the constraints then move onto the next best assignment of values to entries (decrement the value of the entry which appears the least amount of times in `entryList`). Repeat till a valid assignment is found or all options are exhausted.

The steps are:

1. Iterate through all possible assignments of values to entries which matter for the sum (are specified by `entryList`).
2. Check for the current assignment if the rest of the matrix can be filled out such that all constraints on the matrix are satisfied.
3. If step 2 is possible (all entries are filled out and satisfy all of the constraints) then output the sum of entries specified by `entryList`.
4. Otherwise, if step 2 is not possible, continue with the iteration of step 1.

What do you think of my approach?

Ideally there would be some well studied problem to which my problem can be reduced to, unfortunately none come to my mind.

I want to conceptually solve this problem so that I can implement a solution later (I'm using Java if that's of any relevance).

# Answer
> 1 votes
You have 10 variables $x\_1,\dots,x\_{10}$ (representing the entries on and above the diagonal, in the matrix), with constraints that:

* Each $x\_i$ is an integer in the range $-10 \le x\_i \le 10$.
* The first four are non-negative, i.e., $x\_1\>0$, $x\_2\>0$, $x\_3\>0$, $x\_4\>0$.
* A certain sum must be equal to zero, namely,

$$x\_1 + x\_2 + x\_3 + x\_4 + 2 x\_5 + 2 x\_6 + 2 x\_7 + 2 x\_8 + 2 x\_9 + 2 x\_{10} = 0.$$

You are given a subset $S$ of the variables, and you want to find an assignment to the variables that maximizes the sum of the variables in that subset, i.e., you want to maximize $\sum\_{i \in S} x\_i$.

On approach is to formulate this as an integer linear programming problem. The problem is small enough that any off-the-shelf ILP solver should be able to solve it without difficulty. Indeed, even ordinary linear programming might suffice.

A possible greedy algorithm is: pick elements from $S$ one at a time (preferring elements on the diagonal over non-diagonal elements, but otherwise in any arbitrary order), and assign them the value 10. At each step, look for any assignment to the yet-to-be-assigned variables that satisfies the constraints (e.g., make all unselected diagonal elements be 1, except that if there is an odd number of unselected diagonal elements, make one of them be 2; then assign values to the other unselected non-diagonal elements so that things sum to zero). In each step, we set one more element from $S$ to 10, then look for a reasonable way to fill in values for the unassigned variables. This gives you a sequence of candidate matrices, one per step. Choose the best one, i.e., the one where the sum of desired elements is the largest. I'll leave it to you to verify whether or not this is correct.

---
Tags: algorithms, greedy-algorithms, matrices
---


# Question
Title: CFG problem solved with PDA - looking for alternative solution
I'm trying to find CFG for the language $$L = \\{ a^nb^mc^kd^l | n + k = m + l, (n,m,k,l) \in \mathbb{N} \\}$$ and what I have done so far is to make PDA which simply does the following:

* If on the stream there is "a" -\> push $\xi$ in the stack
* If on the stream there is "b" and the stack is empty -\> push $\zeta$ in the stack
* If on the stream there is "b" and there is $\xi$ in the stack then while there are $\xi$ in the stack read b from the stream and pop $\xi$.
* If there is "b" on the stream and no $\xi$ left in the stack continue reading "b" and push $\zeta$.

And so on counting the a,b,c and d's which I get, but the problem is that my transition function is getting really big and I'm gonna have some troubles to convert it into CFG, so there must be straightforward way to do it and seems I can't find it.

Can somebody help me, please?

# Answer
First assume $n\ge m$. Then we can take $i=n-m$ and we have $i+k =l$, so strings are of the form

$ a^i a^m b^m c^k d^k d^i$.

You can do a CFG for that.

Then consider $n\le m$.
> 2 votes

---
Tags: formal-languages, context-free, pushdown-automata
---


title: Greatest matching values in matrix

text:
# Question
Title: Greatest matching values in matrix
**Problem:**

Looking for an efficient algorithm to find the largest value that exists in all columns.

---

**Constraints:**

* The values in each column are always decreasing

---

My algorithm:

1. Check the first row for match
2. Use the lowest value from first row to search for match
3. Use the value from row x, column y to search for match
4. Increase row index until n
5. Increase column index until n

---

**Examples:**

*Best case* $$A=\begin{bmatrix}17 & 17 & 17\\ 14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\end{bmatrix}$$

```
Select Row1,Col1 to match
17, 17, 17

Result is 17

```

*Average case* $$B=\begin{bmatrix}13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\\ 9 & 5 & 10\end{bmatrix}$$

```
Select Row1,Col1 to match
13, 10, 15

Select lowest value in Row1 (10)
10, 10, 10

Result is 10

```

*Worst case* $$C=\begin{bmatrix}14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\end{bmatrix}$$

```
Select Row1,Col1 to match
14, 14, 16

Select lowest value in Row1 (14)
14, 14, x

Select Row2,Col1 to match
13, x, 13

Select Row2,Col2 to match
10, 10, x

Select Row2,Col3 to match
x, x, 15

Select Row3,Col1 to match
11, x, x

Select Row3,Col2 to match
x, 8, x

Select Row3,Col3 to match
13, x, 13

Select Row4,Col1 to match
10, 10, x
(repeated!)

Select Row4,Col2 to match
x, 7, x

Select Row4,Col3 to match
x, x, 12

Result is no matches

```

# Answer
Build single hash table from any column and augment it with counter, set it to 1.
Add second column to the hash table discarding not existing values from the second column. Optionally you can remove values that are still singular.
Add third column element by element, store the maximal encountered triplet.

This will run in expected $\mathcal O(n)$ time, where $n$ is column length.

What you have proposed looks a bit like selection sort. Making it explicit, sort columns in descending order and start checking for triplet. It would give $\mathcal O(n\log(n))$ runtime.
> 1 votes

---
Tags: algorithms
---


title: Complete Graph & Connected Component

text:
# Question
Title: Complete Graph & Connected Component
There seems to be various implementations of algorithms that find the connected components of a graph.

I have not found, however, an algorithm or implementation for finding which of the connected components are also complete. Does anybody know of one?

Thank you!

# Answer
Most graph libraries will find the connected components of a graph G as a list of connected subgraphs \[H1, H2, H3, ...\] and most of these libraries will have the functionality to obtain the number of nodes and number of edges in a graph. Assuming H is a simple graph (no loops, no multiple edges) with m edges and n vertices, one can say it is complete if

```
m == n*(n-1)/2

```

So, given the output of connected components, you should do:

```
for each graph H in [H1, H2, ...]
  int n = H.getNumVertices()
  int m = H.getNumEdges()
  if (n*(n-1) == 2*m)
    state that H is complete
  else
    state that H is not complete

```
> 1 votes

# Answer
Though the answer is already posted, here I propose a beatiful approach. One can notice that a graph is union of cliques if and only if it doesn't contain a path on 3 vertices, $P\_3$, as induced subgraph. It looks like a triangle without one side. Just checking the adjacency matrix for $a\_{ij}+a\_{ik}+a\_{jk}=2$ will be sufficient. It's $O(n^3)$.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Can all programs with mutable state be refactored in programs without?
Given the space A of all programs that could be possibly written in a given language and given the space B of all programs that could be possibly written in the same language but without any mutable state: can we be sure that with just B we can solve all the same problems we could solve with A ?

# Answer
There is no general notion of "mutable state" for a generic language. I believe we need to restrict this question to some specific language.

For instance, consider a basic imperative language with arithmetic expressions ($\*,+,-$), read input, write output, assignment, composition, conditional ($e=0$ guards), and while loop. No user-defined functions, hence no recursion. Unbounded-precision integer variables. Forbidding mutability would greatly affect the computational power. Unrestricted, it is Turing powerful, but after restriction becomes a very weak language which is able (I believe) to compute only piecewise polynomials / divergence.

If the language is instead a higher order functional language with recursion and assignment (e.g. Scheme), forbidding mutability will not affect its computational power: it was and remains Turing powerful. Mutable state can still be simulated without mutability. A way to do it is to encode state-mutating functions $f$ as pure functions $f({\sf input},{\sf old\\\_ state})=({\sf output},{\sf new\\\_state})$ (see the so-called "state monad" in functional programming).

Further, Turing & Church proved that the (pure) $\lambda$-calculus has the same power of the Turing machine. So this is a pretty established result! It is one of the very first discoveries that started computer science in the 30s.
> 5 votes

# Answer
You need to define what "mutable state" means. In one interpretation space A is all Turing machines and space B is all the read-only Turing machines. Read-only Turing machines are only as powerful as DFAs.

If you allow one-time writing to new tape in space B then by copying the string over to new tape and making certain substitutions to the string, you can create a String Rewriting System which is Turing complete.
> 3 votes

# Answer
Yes, there is such a transformation.

Consider a programming language which has a number of commands $c\_1, \ldots, c\_n$ that manipulate state. When we run a program, it starts in some initial state $s\_0$. As commands are executed, they change the state so that it goes through a series of configurations $s\_0, \ldots, s\_k$ (the series may be infinite if the program runs forever).

Instead of there being one global state $s$ which changes with time, we will instead make sure that every command and every function takes in the current state and outputs the new state. We will then "pass along" the "current state" throughout the program in a systematic way. For instance, if there is a command $\mathtt{INCR}(\ell)$ which increases the counter at memory position $\ell$, we will change it to a stateless function $\mathtt{INCR}' : \mathtt{State} \times \mathtt{Location} \to \mathtt{State}$ which takes the "current state" and a location, and returns the new state. In general, any construct $c$ which takes as input $A$ and outputs $B$ will be transformed to a construct $c'$ which takes as input $\mathtt{State} \times A$ and outputs $\mathtt{State} \times B$.

This sort of transformation can be performed systmatically so that in the end we obtain a stateless program which takes as input the initial state and outputs the final state (as well as whatever output it was going to give). I did not explain all the details, but they are there and are well known. Various complications, such as local state, can be dealt with. A good exercise is this: take a language with a fixed number of stateful variables, say `a`, `b`, `c`, and think about transformations that replace the variables with state, say a triple `(a,b,c)`, which is passed along (if there are any `while` loops they will have to be replaced with recursive functions).

In fact, this is how state is implemented in purely functional languages. Haskell has the state monad, for instance, which does precisely what I described above.
> 3 votes

---
Tags: computability
---


# Question
Title: Searching a sorted array to find the $k$ closest values to a target value $T$
Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A\_j, A\_{j + 1}, ..., A\_{j + k - 1}$ have the $k$ closest values to the given target value $T$. Assume that $k$ is comparable, in magnitude, to $N$; i.e. we *don't* have $k \ll N$.

One can naively do this by first (binary) searching for the closest element, and then successively probing the left/right neighbors of that element to arrive at the result. This method has a time complexity of $O(\log N + k)$.

I suspect one can modify the original binary search algorithm to arrive at the result in $O(\log N + \log k)$ time. I tried searching online for such a variant of the binary search algorithm, without success. I'd appreciate any/all pointers to sources I might have missed, and also original attempts at formulating such a variant.

*Note*: It turns out there is an elegant binary search cousin that computes the result in $O(\log(N - k))$ time. See Ivan Smirnov's answer for a discussion.

# Answer
You can do it in two binary searches. For simplicity I assume that all numbers are distinct and, even more, absolute differences between $T$ and all other elements are distinct too. The solution is easily adapted if it is not the case.

What means that a selected subrange is optimal? That means that we can't move it neither right ($|A\_{j+k} - T| \> |A\_{j} - T|$) nor left ($|A\_{j+k-1} - T| \< |A\_{j-1}|$). That looks like a binary search as well!

Look at the function $h(j) = \mathbb{1}\\{|A\_{j+k} - T| \> |A\_{j} - T|\\}$ (that is, $h(j)$ is 1 iff the answer does not become better if we move the subrange to the right). Now you have to find minimum $j$ s.t. $h(j) = 1$. As the function is monotonous, it can be done by a binary search by $j$ in $O(\log n)$ time. (Actually, it is $O(\log (n-k))$ because $j \< n - k$).

If there are identical values in the array, we need some case handling. Whenever $|A\_{j+k}-T| = |A\_j-T|$, there are three cases possible: Either $A\_{j} = A\_{j+k}$ and the segment is to the left of $T$; in this case we should move right. Or, $A\_{j} = A\_{j+k}$ and the segment is to the right of $T$, and we should move left. Or the segment contains $T$, in this case we've found the optimal answer.
> 3 votes

---
Tags: algorithms, search-algorithms, binary-search, nearest-neighbour
---


# Question
Title: How can I understand if reduction is Karp reduction?
I have a reduction and can't understand if it is Karp reduction. I want understand if my reduction is Karp reduction as well as understand how to determine which one is so.

Let I have formula $\Phi = (l\_{1,1}\lor l\_{1,2}\lor...\lor l\_{1,k\_1})\land(l\_{2,1}\lor...\lor l\_{2,k\_2})\land...\land(l\_{n,1}\lor...\lor l\_{n,k\_n})$

And I want to check if it is minimal CNF (decision variant of CNF minimization, one that requires to minimize amount of literal occurences). Determine if formula has an equivalent with $m$ or lower amount of literal occurences. This problem is $\Sigma^P\_2$-complete. However, I have reduction:

$$Min(\Phi)=m\ge(length(\Phi)-(\overline{S(\Phi\land\overline {l\_{1,1}}\land l\_{1,2}\land...\land l\_{1,k\_1})}+\overline{S(\Phi\land l\_{1,1}\land \overline{l\_{1,2}}\land...\land l\_{1,k\_1})}+...+\overline{S(\Phi\land l\_{1,1}\land l\_{1,2}\land...\land\overline{l\_{1,k\_1}})}+\overline{S(\Phi\land\overline {l\_{2,1}}\land...\land l\_{2,k\_2})}+...+\overline{S(\Phi\land l\_{2,1}\land...\land\overline{l\_{2,k\_2}})}+...+\overline{S(\Phi\land\overline {l\_{n,1}}\land...\land l\_{n,k\_n})}+...+\overline{S(\Phi\land l\_{n,1}\land...\land\overline{l\_{n,k\_n}})}))$$

Here I use $S$ to denote $SAT$-problem.

$length(\Phi)$ counts amount of literal occurences in formula $\Phi$.

If this reduction is Karp reduction, then $\Delta^P\_2 = \Sigma^P\_2$ and $PH$ collapses.

But is this reduction Karp reduction, how can I determine it (general method is preferred)?

Okay, it seems, using $P^{NP}$ machine I can use $+,-,\<,\>,=$ operations (do not know about $\cdot,/$) for any data machine has at some step (after getting answer from oracle). If so, then I'm surprised that no one found such simple algorithm for CNF minimization.

# Answer
Your reduction repeatedly calls a SAT oracle. Karp reductions only make one oracle call, and furthermore they must immediately return whatever the oracle returns (so it's like a "tail call"). So your reduction isn't a Karp reduction.

How to know if a reduction is a Karp reduction? Use the definition. A Karp reduction from a language $A$ to a language $B$ is a polytime function $f$ such that for all $x$ we have $x \in A$ iff $f(x) \in B$. If your reduction cannot be put in this form, it is not a Karp reduction.
> 2 votes

---
Tags: reductions
---


title: Space complexity of Chomsky Normal Form

text:
# Question
Title: Space complexity of Chomsky Normal Form
I'm trying to find sup of $\\|\mathbb{G}\\|$ where $\mathbb{G}$ is CFG in Chomsky Normal Form. So far i have done some work, but I'm really not sure in my proof. Let $G = \langle Q, N, S, R\rangle$ and $$\alpha \rightarrow \beta \in R,\ |\beta| = n$$ $$\\|\alpha\\| \le \sum\_{i=0}^{\log\_{2}n}2^{n}\\,.$$ I made this conclusion by observing the binary tree I get when I try substituting the right side of the rule with $$\beta =b\_{1}b\_{2}...b\_{n}$$ $$\beta \rightarrow A\_{1}A\_{2},A\_{1}\rightarrow B\_{1}B\_{2}, A\_{2}\rightarrow B\_{3}B\_{4}$$ and so on until $$Q\_{1} \rightarrow b\_{1}b\_{2}, ...,Q\_{\[\frac{n}{2}\]}\rightarrow b\_{n-1}b\_{n}$$

The result is binary tree with height $\log\_{2}n$ which on each level has $2^{i}, i = {0,1,...,\log\_{2}n}$ nodes. Finally I claim that $$\\|\mathbb{G}\\| \le |N| + |N|\sum\_{i=0}^{|N|-1}(\\|\alpha\\|),\ \exists (A \rightarrow \alpha) \in R\\,.$$

# Answer
It is well-known, and stated in Wikipedia (which gives a reference: Lange and Leiß), that there is an algorithm transforming an arbitrary context-free grammar $G$ into a grammar in Chomsky normal form of size $O(|G|^2)$.

The following grammar might be an example showing that the quadratic blow-up is necessary: $$ \begin{align\*} &S \to A\_1 \ldots A\_m \\ &A\_1 \to A\_2 \mid \sigma\_1 \\ &A\_2 \to A\_3 \mid \sigma\_2 \\ &\cdots \\ &A\_{m-1} \to A\_m \mid \sigma\_{m-1} \\ &A\_m \to \sigma\_m \end{align\*} $$ This grammar has size $\Theta(m)$, and it seems that every grammar in Chomsky normal form for this language must have size $\Omega(m^2)$.
> 2 votes

---
Tags: formal-languages, context-free
---


# Question
Title: How to prove that a system is real-time?
I'm writing a paper on the system I designed which upon receiving an event, performs a number of calculations and publishes the result to several subscribers. I can calculate the amount of time it takes from the moment the system is informed about the event, to the moment when all subscribers successfully received the calculation results. I perform multiple experiments to measure the amount of time for a various number of subscribers.

In my paper, I'm claiming that my system is capable of real-time responses to the first event. Could you please give me some hints that how I can prove that based on the data I collected? Thanks

# Answer
> 3 votes
You need to provide a more precise description of your system and real-time requirements.

If you are interested in only the timeliness and timeliness predictability of the response to the first event, your question is about that one event response and not about the subsequent events responses and thus the system.

You didn't specify your required timeliness and timeliness predictability for responding to that event. It sounds like you are satisfied with your empirical measurements for subsequent responses to varied numbers of recipients. So for the first event response, you need to specify your desired response time constraint, such as a deadline. Then you need to specify the desired predictability of that response's timeliness.

Perhaps you want to a' priori know that the deadline will always be met--i.e., that the response is deterministic (deterministic is one end-point on the scale of predictability). If so, you need to identify what presumptions about your system and its execution environment you make for that prediction; that is called a system model.

Your question indicates that your measurements do not cause you to expect that subsequent responses be deterministic--instead you expect that if the first response is deterministic, your subsequent response measurements have been empirically predicted accurately.

There is a large body of literature about determining worst case execution times (the first response latency in your case), and the presumptions that are necessary for those times to be accurate. Formal proof that your first response time is deterministic may or may not be feasible, depending on the unstated presumptions you are making. (In general, such proofs get rapidly more difficult as more things are presumed to be more dynamic instead of all being static.)

But if instead of requiring that the first response time be deterministic, you are either satisfied with or forced to concede that your system model provides a non-deterministic first response time, you have to explicitly deal with the response time predictability.

There is a vast body of theory and practice on that topic in general (although not in the conventional real-time computing field).

In your case, you could simply do sensitivity experiments to measure and establish bounds on the variability of the first response timeliness, by varying parameters of your system model.

To convert that into analytical predictability, you can do probability distribution function fitting. For example, perhaps your measured first response times are normally distributed with means and variances based on your measurements. While not a proof, that gives you an analytical way to reason about that response time.

# Answer
> 5 votes
It depends on your definition of "real-time system". A standard definition is: a system is real-time if it will respond within $T$ seconds, with probability at least $P$. Here you need to fill in the parameters $T,P$; e.g., it might be $T = 1$ millisecond and $P = 0.999$.

How do you prove that this condition is met? One way is to find a way to generate random workloads, from the same distribution as the system will be exposed to in practice, and count how often the system meets the deadline and how often it doesn't. Another way is to prove a theorem (e.g., with formal methods) about the maximum time it might take to respond; see the literature on worst-case execution time analysis. The latter might be particularly challenging in many cases.

There's an entire literature on this topic, that you can read more about.

---
Tags: real-time
---


title: Generating words in given format

text:
# Question
Title: Generating words in given format
i am looking for an algorithm that will generate all possible combinations of words from given dictionary that satisfy given format.

Let me explain what i mean with format:

For example, if the format is "abcd" means that we are looking for one word, length of the word must be 4 and because all the letters in format are different, all the letters in the word must be different.

The format "computer science" means:

1) We are looking for 2 words (one of length len("computer") = 8 and one of lenght len("science") = 7)

2) The first char of the first word must be the same as the second char and the sixth char in the second word (letter "c" in format)

3) The seventh char of the first word must be the same as the the forth and the last char in the second word (letter "e" in format)

Is it better to generate all the possible strings in given format and the look them up in the dictionary or somehow build strings using dictionary ?

edit:

My idea:

1) split big dictionary (100 millions of words) into smaller ones based on word length.

2) for first word get trough all the entries in particular dictionary and try to match first word, then continue with the next one, but with more restrictions.

Thank you for your help!

# Answer
This can be solved with a join operation.

Let's take your example with format "computer science":

* Build one list L1 of dictionary words where each word is mapped to a two-letter key, by extracting the first and seventh letter of the word.
* Build a second list L2 of dictionary words where each word is mapped to a two-letter key, by extracting the second and fourth letter of the word; with the additional restriction that you only include words where the 2nd and 6th letter are the same, and where the 4th and 7th letter are the same.
* Now compute the "join" of L1 and L2, i.e., where you look for all pairs of a word from L1 and a word from L2 that have the same key. This can be done by any of the standard join algorithm, e.g., a hash join or a sort-merge join.

You should be able to see how to generalize this to arbitrary formats, possibly by performing multiple join operations (if the format has three or more words). If you need to perform multiple join operations, there are multiple different orders in which you can perform the join operations; the topic of query optimization deals with how to choose the best order.
> 0 votes

# Answer
Alright, I managed to solve this problem using Prolog.

First of all, I've converted wordlist.txt from:

* word1
* word2
* ...

Into wordlist.pl:

* w(w,o,r,d,1).
* w(w,o,r,d,2).

Then I've found Prolog function, that tells me if all the elements in the list are different:

```
alldif([]).
alldif([E|Es]) :-
   maplist(dif(E), Es),
   alldif(Es).

```

After that I have written Prolog function, that takes predefined format and finds all the possible words from dictionary, that meet given format:

```
g(Format, String):-
    list_to_set(Format, Uniques),
    alldif(Uniques),
    w(Format),
    atomic_list_concat(Format, '', Atom), atom_string(Atom, String).

```

Now I'm able to call:

```
g([A,B,C], String1), g([A,D,A], String2).

```

That generates me all possible combinations of String1 and string2 with following format:

"ABC ADA"
> 0 votes

---
Tags: algorithms, strings, enumeration
---


# Question
Title: Is there a faster algorithm for constructing the adjacency list of this graph?
My problem is to find a better algorithm to fill the adjacency list.

specs:

```
G = (V , E ) //the graph
V ={w} //vertex in this case each vertex is an array
E={⟨u,v⟩| u,v ∈V ∧ u>v} // edge only if u > v
u > v only if  foreach i u̸=v ∧ u[i]≥v[i]. // (u>v and v>w => u>w)

```

my naive code whit complexity **O((v+1)\*v/2) ≈ O(n^2)** is

```
private void riempiAdj() {
    for(int i=0;i<nodi.length;i++)
        for(int j=i+1;j<nodi.length;j++)
            if(nodi[i].eMaggiore(nodi[j]))
                nodi[i].adj.inserisci(nodi[j]);
}

```

`nodi` is the array of vertex

`adj` is the adjacency list

`AdjList.inserisci(Vertex t)` add a vertex t into adjacency list **O(1)**

`Vertex.eMaggiore(Vertex t)` returns true in this \> t **O(1)**

exist an algorithm whit complexity of **O(v)** or **O(v\*log()v)**?

# Answer
> 1 votes
Since the relation is transitive, in the worst case you have $\frac{|V|(|V|-1)}{2}$ edges and so, if you want to add all edges of the graph in the list, you cannot achieve better than $O(|V|^2)$

PS: This problem is similar to an Algorithm project in my University, what a coincidence! ( ͡° ͜ʖ ͡°)

---
Tags: algorithms, complexity-theory, graphs
---


# Question
Title: Calculating the information density of an encoding system
How do I calculate the information density of an encoding system?

This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major paper on encoding data in DNA after Church's). All of them mention the information density of their encoding system, which I understand to be given in units along the lines of bits or bytes per nucleotide.

From looking around on the internet and asking around in the hbar (the Physics chat) I understand the absolute basics: that one creates a model that gives the probability distribution over the possible messages in your system (say, English, or ASCII) and then from there calculate the average information density of a message using that distribution.

Unfortunately, as a complete beginner, I don't know how to do any of those things. I'd like to understand that process and in the end be able to do my own calculations. Any resources would be helpful, of course, but I was advised to ask this question here.

**Tl;dr: how do you calculate the information density of a system?**

# Answer
> 1 votes
When people talk about information density in this context, they probably mean that the information density is

$$\text{density} = {n \over m}$$

where $m$ is the number of nucleotides needed to encode $n$ bits. Here the assumption is that the $n$ bits come from the uniform random distribution (i.e., all $2^n$ possibilities are equally likely). Implicitly, we are taking $n$ to be very large, or taking the limiting value of the density as $n \to \infty$.

So, think of it this way. Imagine we had $n = $ 1 million bits. How many nucleotides would the encoding scheme need, to encode those 1 million bits, on average? Call that $m$. Now divide $n$ by $m$; that's your information density.

The way to figure out the average number of nucleotides needed to encode a one-million-bit input will depend on the particular encoding scheme.

---
Tags: reference-request, efficiency, information-theory, encoding-scheme
---


# Question
Title: Data Analysis: Have 70 data parameters, how many different classes of 3 are possible?
The order of the classes of three does not matter. Example: 1,2,3 and 3,2,1 would be considered one class. I am trying to do fisher discriminant analysis on a set of data and want to begin reducing the parameters to better help with classification. As of now I cannot tell which parameters are the most pertinent, so looping every combination through and then having MATLAB take out the LDA analysis with the MisIDs on the lower end in my algorithm will help to isolate the parameters. Can someone refresh me on the math behind this/suggest a way to code this in MATLAB?

# Answer
> 2 votes
That probably isn't the most effective way to figure out which parameters (features) are most informative. Instead, I suggest looking at methods for feature selection or feature ranking. There are many methods out there; it's a well-studied topic.

---
Tags: combinatorics
---


title: Time complexity of recursive power code

text:
# Question
Title: Time complexity of recursive power code
While I was learning about time complexity of recursive functions, I came across this code to calculate $x^n$:

```
power (x, n) {
    if n == 0
        return 1
    if n is even
        return power(x, n/2) * power(x, n/2)
    if n is odd
        return power(x, n/2) * power(x, n/2) * x

```

According to the book, its complexity is $\Theta(n)$ which seems rather strange to me. In my eyes, this code should have complexity $\Theta( n^2)$.

What am I seeing wrong?

# Answer
> 2 votes
## An Answer

I will take your code at face value under the Uniform Cost Model.

Let's now assume $n$ is of the form $n = 2^k$ where $k \in \mathbb{N} \wedge k \geq 0$ (e.g. $n$ is a power of $2$).

We then get a recurrence relation like so:

$$\begin{align} T(x, n) & = 2 \cdot T\left(x, \frac{n}{2} \right) + c \\\\[0.5em\] & = 4 \cdot T\left(x, \frac{n}{4} \right) + 2c + c \\ & = \vdots \\\\[0.5em\] & = \sum\_{i = 1}^{\log\_2 n} 2^{i - 1} \cdot c\\\\[0.5em\] & = c(n - 1)\\ & = \Theta(n) \end{align}$$

---

## Some Fun

Now let's take a step back and check out the Logarithmic Cost Model. Let's define the cost of multiplication as $g(n)$ where $n = \log\_2 x$ (the size of $x$ in binary) and $x$ maximum of the two arguments.

Along with our prior assumption about $n$, let's also assume $x$ is of the form $x = 2^k$ where $k \in \mathbb{N} \wedge k \geq 0$ (e.g. $x$ is a power of $2$).

We get a recurrence of the form:

$$\begin{align} T(n) & = 2 \cdot T\left(\frac{n}{2} \right) + g\left(\frac{n}{2}\right) \\\\[0.5em\] & = 4 \cdot T\left(\frac{n}{4} \right) + 2 \cdot g\left(\frac{n}{4}\right) + g\left(\frac{n}{2}\right) \\ & = \vdots \\\\[0.5em\] & = \sum\_{i = 1}^{\log\_2 n} 2^{i - 1} \cdot g\left(\frac{n}{2^i}\right)\\\\[0.5em\] \end{align}$$

Now we can analyze some interesting multiplication methods:

1. Multiplication is linear in size, e.g. $g(n) = n$.

$$ \begin{align} T(n) & = \Theta(n \log n) \end{align}$$

2. Multiplication is quadratic in size, e.g. $g(n) = n^2$.

$$\begin{align} T(n) & = \Theta(n^2) \end{align}$$

3. Karatsuba Multiplication, the divide and conquer method, e.g. $g(n) = \Theta(n^{\log\_2 3})$

$$\begin{align} T(n) & = \Theta(n^{\log\_2 3}) \end{align}$$

4. Just for fun, and to plug Yuval's answer to my own question, multiplication is super-linear-polylogarithmic and sub-polynomial-polylogarithmic, e.g. $g(n) = \Theta(n\log n \cdot 2^{\sqrt{2\log n}})$. We also assume size $n$ for $g$ instead of $\frac{n}{2}$.

$$\begin{align} T(n) & = 2 \cdot T\left(\frac{n}{2} \right) + \Theta\left(n\log n \cdot 2^{\sqrt{2\log n}}\right) \\\\[0.5em\] \end{align}$$

We use case 3 of the Master Theorem to get:

$$\begin{align} T(n) & = \Theta\left(n\log n \cdot 2^{\sqrt{2\log n}}\right) \\\\[0.5em\] \end{align}$$

Essentially, but not exactly, as the time complexity becomes superlinear, the time it takes to multiply overtakes the recursive time. This can be seen as case 3 of the Master Theorem.

---

## Even More Fun!

Now let's say this was implemented in a smart manner, not repeating the recursive calls or using DP.

We get a recurrence of the form:

$$\begin{align} T(n) & = T\left(\frac{n}{2} \right) + g\left(\frac{n}{2}\right) \\\\[0.5em\] & = T\left(\frac{n}{4} \right) + g\left(\frac{n}{4}\right) + g\left(\frac{n}{2}\right) \\ & = \vdots \\\\[0.5em\] & = \sum\_{i = 1}^{\log\_2 n} g\left(\frac{n}{2^i}\right)\\\\[0.5em\] \end{align}$$

The major improvement now is when multiplication is linear in size, we now get linear exponentiation!

$$ \begin{align} T(n) & = \Theta(n) \end{align}$$

# Answer
> 0 votes
The code as written is awfully bad: If n \> 0 then it makes two recursive calls calculating the exact same result, which would make it θ(n). That's awfully bad because it can easily be done in θ(log n) by making *one* call and multiplying the result by itself.

There is no reason to think this would be $θ(n^2)$. If it was $θ(n^2)$, that would be quite bad because even a simple dumb multiplication loop would run in θ(n).

---
Tags: algorithm-analysis, runtime-analysis, recursion
---


# Question
Title: How to express modalities in lambda calculus - are some extensions required?
Lambda calculus can be used for encoding semantics of natural language, e.g. http://yoavartzi.com/tutorial/ contains full details about semantic parsing of natural language: converting natural language texts into lambda expressions - Cornell Semantic Parsing Framework is used https://github.com/cornell-lic/spf.

My question is - **how to express modalities in lambda calculus - are some extensions required?** E.g. usual classical modal logics can express beliefs/duties-permissions/knowledge and other kind of modalities. Relational (Kripke) semantics is used for modal logics. So - how can we extend of combine lambda calculus to express modalities?

There is idea to express modalities as just another kind of predicates https://www.amazon.co.uk/Toward-Predicate-Approaches-Modality-Trends-ebook/dp/B016XM48V0 but are there some alternatives, more "natrual" ways to introduce modalities in lambda calculus? Full handling of natural language certainly requires this.

# Answer
> 6 votes
Are extensions required? Not really. You can take an axiomatic description of a modal logic and simply provide a "primitive" lambda term for each. The modal operators would become type constructors. Haskell's `IO` monad can be viewed this way. Coherence conditions like the monad laws would provide some conversions between terms.

A different approach, which does involve extending the lambda calculus, is described in Frank Pfenning's and Rowan Davies' A Judgmental Reconstruction of Modal Logic. Note, this is for an *intuitionistic* modal logic. This involves changing the context, or specifically, having multiple contexts to include hypothetically valid propositions. You get rules like:$$ \frac{\Delta;\cdot\vdash M : A}{\Delta;\Gamma\vdash\mathsf{box}\ M:\square A}\qquad\frac{\Delta;\Gamma\vdash M:\square A\quad\Delta,u::A;\Gamma\vdash N:B}{\Delta;\Gamma\vdash\mathsf{let\ box}\ u=M\ \mathsf{in}\ N : B}$$ You should read the $\mathsf{let\ box}\ u = M\ \mathsf{in}\dots$ as pattern matching/a destructuring bind against $M$.

We have:$$ (\lambda m.\mathsf{let\ box}\ u= m\ \mathsf{in}\ u) : \square A \to A \\ (\lambda f.\lambda x.\mathsf{let\ box}\ f'=f\ \mathsf{in\ let\ box}\ x'=x\ \mathsf{in\ box}\ (f'x')) : \square(A\to B)\to\square A\to\square B \\ (\lambda m.\mathsf{let\ box}\ u=m\ \mathsf{in\ box}\ (\mathsf{box}\ u)) : \square A \to \square \square A$$ Handling possibility as opposed to or in addition to necessity requires a bit more cleverness.

---
Tags: formal-grammars, lambda-calculus, semantics, natural-language-processing, modal-logic
---


# Question
Title: How is average precision related to the precision-recall curve?
As background, in Information Retrieval, there are many metrics to assess how well search results are retrieving information.

A simple one is precision, where we calculate the fraction of documents returned that are relevant to our query. There is a second (or more general?) metric, precision@K: For a ranked result set, we calculate the fraction of documents at rank $k$ or higher which are relevant. So if the first document is relevant, the second is not, and the third is, then precision@3 is 1/3.

On to average precision. As I understand it (thanks in part to this), for this we get the rank of every relevant document in the result set, and then average the precision@k values at each of those ranks. It's even clearer if you look at my link.

Ok, **my question**: Both Wikipedia (here) and my IR book give the same explanation I gave, but then they start talking about precision-recall curves. My understanding of precision-recall curves is from machine learning, but I assume the concept is similar: You plot precision and recall against each other (on the x and y axis), showing how a decrease in one leads to an increase in the other.

I don't see how that relates to average precision, which is only a metric of precision and not of recall.

Wikipedia says: *Precision and recall are single-value metrics based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. By computing a precision and recall at every position in the ranked sequence of documents, one can plot a precision-recall curve, plotting precision p(r) as a function of recall r. Average precision computes the average value of p(r) over the interval from r=0 to r=1.*

If I had to guess, it seems like they're describing calculating *both* average precision *and* average recall for every rank, or something. But if so it's confusing that they'd put it under Average Precision, and I'm very unsure of my interpretation.

So, how is average precision related to precision-recall graphs? It probably goes without saying that any other tips on understanding that Wikipedia section are also humbly appreciated.

# Answer
> 1 votes
Let $p(r)$ be the best precision which can be achieved at recall $r$. The average precision is $$ p\_{avg} = \int\_0^1 p(r) \\, dr. $$ Let $r(p)$ be the best recall which can be achieved at precision $p$. The average recall is $$ r\_{avg} = \int\_0^1 r(p) \\, dp. $$ Notice that the functions $p(r)$ and $r(p)$ are inverses of one another.

We can express these quantities using the function $\chi(p,r)$, which is 1 if precision $p$ and recall $r$ are achievable at the same time, and 0 otherwise. We have $p(r) = \int\_0^1 \chi(p,r) \\, dp$, and so $$ p\_{avg} = \int\_0^1 \int\_0^1 \chi(p,r) \\, dp dr. $$ Similarly, $r(p) = \int\_0^1 \chi(p,r) \\, dr$, and so $$ r\_{avg} = \int\_0^1 \int\_0^1 \chi(p,r) \\, dr dp. $$ As a consequence, $p\_{avg} = r\_{avg}$.

Yet another interpretation of this common quantity is the area below the precision–recall curve. It is also the area below the ROC curve.

---
Tags: information-retrieval
---


# Question
Title: Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time
**Question**

Is it possible to find an existing point's nearest neighbour within a logarithmic upper bound?

**What I've tried**

I have:

* the set of points $P$,
* a point $p$, where $p\in P$,
* a point $q$, where $q\notin P$,
* a Voronoi diagram, $V(P)$, of the points in $P$.

I know it's possible to query for a new point $q$'s nearest neighbour in $\mathcal{O}(\log{}n)$ time using $V(P)$ but is it possible to find the nearest neighbour of an existing point, such as $p$?

I've thought that if it wasn't possible, then I could delete the point $p$ in $V(P)$, assuming I could somehow create a dynamized Voronoi structure that allows for timely deletions (this paper notes that there is a way to insert points in constant time, so hopefully there's a Voronoi structure that allows deletions in logarithmic or less time), then search for the now non-existing point in logarithmic time. This would also solve my problem. Is there a dynamized Voronoi structure that allows deletions in $\mathcal{O}(\log n)$ time?

# Answer
> 1 votes
If you have a voronoi diagram you have neighbour information of each $p$. You can use that to path search (using A\* or even greedy depth first) to the 3 points that surround $q$. Then you can extract the closest from that.

If the voronoi is stored as a binary tree where each line divides the space into half-planes then it's just a dive into the search tree.

---
Tags: nearest-neighbour, voronoi-diagrams
---


title: CCS synchronization

text:
# Question
Title: CCS synchronization
Within CSS we talk about binary interactions. Does this prevent synchronizing multiple processes in one step? Example:

$P\_1 ::= a.D$

$P\_2 ::= \overline{a}.D$

$P\_3 ::= a.D$

Let's consider the following LTS: $(P\_1 | P\_2 | P\_3)\restriction\_a$

Do I get $P\_1, P\_2, P\_3$ $\tau$-synchronized simultaneously if an action $\tau$ happens or only two of them get synchronyzed and so I get $D|D|P\_3$?

# Answer
From $P \stackrel{def}{=} (P\_1 | P\_2 | P\_3)\restriction\_a$ you have exactly two outgoing transitions:

$$ P \stackrel{\tau}{\rightarrow} (D | D | P\_3)\restriction\_a $$

and

$$ P \stackrel{\tau}{\rightarrow} (P\_1 | D | D)\restriction\_a $$

CCS does *not* have ternary synchronisation, only binary. Indeed it can be shown that ternary synchronisation is strictly more expressive than binary synchronisation, in the sense that there cannot be a "nice" encoding of ternary synchronisation into calculi with only binary synchronisation.
> 4 votes

---
Tags: transition-systems, ccs
---


# Question
Title: Which are the cases where the "pumping lemma" doesn't work?
Are there some languages not regular and/or not context-free in which the proof by contradiction fails? Why we need a "more specific" version of pumping lemma?

# Answer
> 4 votes
The standard formulations of the regular pumping lemma all force the pumped part to be at a specific place -usually the beginning of the word- and of a very restricted length. Thus you can trick the lemma by contructing a language that allows just about anything in the first part of the string and gets complicated in the second part. Take for example:

$$\\{wba^nb^n\mid w\in\\{a,b\\}^+,\ n\>0\\}\\,.$$ Since the pumping lemma just states the existence of its constants, you can pump anything in the first part of the language without leaving it. However, due to the last component the language is not regular.

---
Tags: formal-languages, pumping-lemma
---


# Question
Title: Query regarding PP complexity class vs NP?
Considering the complexity classes $NP$, $co-NP$ and $PP$:

1. $NP$ and $co-NP$ are both contained in $PP$.
2. For any Language *$L$* suppose we have the mechanism that: If the oracle of $co-NP$ implies $No$ on a modified version of $L$ (lets call it $L'$), then that we can be certain that for every run of $PP$ on $L$ would return $No$.

Does that imply something about the complexity of $PP$/$coPP$ (as $PP$ and $coPP$ are same) vs. $coNP$?

Wouldn't that mean $PP \subseteq coNP$ ?

# Answer
> 0 votes
No, this implies nothing. Suppose the coNP problem is TAUTOLOGY. Here's a mechanism: given any formula $\varphi$, return a new formula $\varphi'$, where $\varphi' = \text{True}$. Then the oracle will always return Yes, so the statement "If the oracle returns No then ..." will be vacuously true. Yet the existence of my mechanism clearly proves nothing interesting (anything we could have proven by considering the consequences of my mechanism, we could have just as easily proven without it).

---
Tags: complexity-theory, complexity-classes
---


title: SSD vs HDD Retrieval Time

text:
# Question
Title: SSD vs HDD Retrieval Time
On an HDD if data is fragmented the discs need to be spun to where the next block in the file is, so how and where data is stored can make a big difference in how long it takes to retrieve the data. With an SSD is the retrieval time for fragmented data constant (due to no moving parts and it being entirely electronic)? Does this mean it doesn't matter how the data is stored on the drive?

# Answer
TL;DR: You don't have to worry about seek times with SSDs like you do with hard disks. As a first-order approximation, you can think of them as random-access devices.

---

SSDs let you read and write entire blocks. There is some cost to read/write a particular block (usually under 0.1ms). Once you're reading or writing a block, it's a lot faster to read/write the rest of the block.

As a consequence, SSDs are almost like random-access devices -- but there is some advantage to having data that will be accessed simultaneously be in the same block, so it does matter to some extent how the data is stored on the SSD.

---

To dive into some more specifics: A SSD is composed of a bunch of erase blocks (think 512KB or so). Each erase block consists of multiple write pages (think 4KB or so). A SSD supports three operations: read at some location; erase an entire erase-block (making all of those write-pages "blank"); and write to an write-page that is currently "blank".

There's no way to to modify just part of a page. Instead, this is implemented by reading the entire page into RAM, modifying it, writing the entire thing to a blank page, and updating some filesystem data structure to point to the new page instead of the old page.

As a consequence, it's best if writes are clustered at the granularity of the underlying pages. Small, random-access writes are slower; long, sequential writes are faster. Many SSDs contain some kind of cache or "write combining" to try to reduce the impact of this.

To give some example performance numbers: it might take 0.05-0.1 ms to read an entire page, 0.3-1 ms to write a page; and 1-3 ms to erase an erase-block. These are just examples -- don't take them too seriously. Actual performance will vary from device to device.

More reading:

https://en.wikipedia.org/wiki/Flash\_file\_system

Design Tradeoffs for SSD Performance. Nitin Agrawal ∗ , Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, Rina Panigrahy. Usenix ATC 2008.

Understanding Intrinsic Characteristics and System Implications of Flash Memory based Solid State Drives. Feng Chen, David A. Koufaty, Xiaodong Zhang. SIGMETRICS/Performance 2009.

https://en.wikipedia.org/wiki/Write\_amplification
> 3 votes

---
Tags: filesystems
---


title: What exactly is bigO notation?

text:
# Question
Title: What exactly is bigO notation?
I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent? I heard that there are two:

1. RunTime
2. Memory Complexity

How can I learn to use it?

# Answer
Big O notation is nothing other than dividing functions into classes based on their asymptomatic growth behavior. What those functions are a measure of is entirely independent of Big O.

Big O is most commonly used to classify the function that maps an input size to the longest time an algorithm runs on any input of that size. But it could be used instead for average running time or shortest running time, or to measure space usage, cache misses, messages sent over the network, etc.

We use big O because we don't generally care about the exact value of these functions, just about how fast they grow. It's an abstraction that lets us see the general pattern but omits constant and lower order factors.
> 0 votes

---
Tags: complexity-theory, asymptotics
---


# Question
Title: How exactly Hashing performs better than a Binary Search?
The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see that log n, when n is around 30 million, is roughly equal to 25.

If for such a large value of n, log n is just 25, then isn't O(log n) roughly the same as O(1)? Because O(1), basically means that the time complexity is constant. So, it could be bigger than or same as 25!?!(here I am assuming that the coefficient of log n, in the actual time usage/consumption function for Binary Search, is less than or equal to 1)

A related question I have, is regarding the calculation of time complexity of a hash algorithm. In all the literature, I barely find any mention of the time complexity of the hash function used and the division required thereafter(to calculate the index of the bucket).

So, exactly how do memory reads/access and computing a fairly complex mathematical operation(as in hash function), compete against each other, w.r.t. time consumption? One memory read/access roughly equates to what kind of basic mathematical operation, in terms of performance?

# Answer
> 3 votes
You are asking excellent questions!

The answer to your first question, regarding the difference between $O(\log n)$ and $O(1)$, is that whereas binary search scales with the size of the array, searching for an item in a hash table scales with the size of the data item, which we often think of as constant. In practice, calculating the hash also takes time (as you also mention), and so to know which data structure has better performance, we need to empirically compare implementations of both data structures.

The answer to your second question, about the time complexity of computing the hash function, is that it takes time linear in the size of the data item. Most hash functions used in this context are "rolling hash", in which a small has value is being updated as the data item is read. This ensures that the time complexity is indeed linear. Hash functions for such uses are designed with speed in mind, and so usually memory access is not an issue. The division operation at the end – if at all – is not too costly for modern CPUs, and can be avoided entirely if the size of the hash table is a power of 2.

# Answer
> 1 votes
Speed of calculating the hash function of large keys: You don't actually have to process the whole key. For example if the key is a string, you might process only the first and last 40 characters to calculate the hash function.

The biggest advantage of hashing vs. binary search is that it is much cheaper to add or remove an item from a hash table, compared to adding or removing an item to a sorted array while keeping it sorted. (Binary search trees work a bit better in that respect).

---
Tags: data-structures, asymptotics, binary-trees, hash-tables, binary-search
---


# Question
Title: Trouble understanding the master theorem, from Jeffrey Erickson's Notes
I'm looking at Jeffrey Erickson's Notes on the master theorem (page 10).

Part (b) of the theorem states that if $T(n) = aT(\frac{n}{b})+f(n)$, $af(\frac{n}{b}) = kf(n)$ and $k\>1$ then T(n) is $\Theta(n^{\log\_b(a)})$. But I get a different result.

Using recursion trees we have $$T(n) = \sum\_{i=0}^{\log\_b(n)} a^i f\left(\frac{n}{b^i}\right) = \sum\_{k=0}^{\log\_b(n)} k^i f(n)\\,.$$

If $k\<1$ then this is $\sim f(n)$ as desired. If $k=1$ then this is $\sim \log\_b(n)f(n)$ as desired. But if $k\>1$ then this is an ascending geometric series, so the last term dominates. Then we have $$\sim k^{\log\_b(n)}f(n) = n^{\log\_b(k)}f(n)\\,,$$ which is wrong; the right answer is $\Theta(n^{\log\_b(a)})$. Where does my reasoning go off the rails, and what is the correct solution?

Any help is appreciated.

EDIT: I think my answer is actually right, and is equivalent to Erickson's simpler answer. Note that $k^nf(n) = k^{n-1}af(\frac{n}{b}) ... = ka^{n-1}f(\frac{n}{b^k-1}) = a^nf(\frac{n}{b^k}).$ Hence $k^{\log\_b(n)}f(n) = a^{\log\_b(n)}f(1) \sim n^{\log\_b(a)}$.

# Answer
You can further simplify $n^{\log\_b(k)}f(n)$.

We have $\frac{a}{k}f(\frac{n}{b}) = f(n)$. If $c = \log\_b(n)$, we can apply this identity $c$ times to get $\left(\frac{a}{k}\right)^c f(1)$.

So $n^{\log\_b(k)}f(n) = n^{\log\_b(k)}\left(\frac{a}{k}\right)^c f(1) = k^{\log\_b(n)}\left(\frac{a}{k}\right)^{\log\_b(n)} f(1) = a^{\log\_b(n)}f(1) = \Theta(n^{\log\_b(a)})$
> 3 votes

---
Tags: recurrence-relation
---


# Question
Title: Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time
> Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time and **constant** space.

The original problem appears here, however the solution uses $\lg n$ space. A problem in my course required adjusting the algorithm such that we use constant space.

I thought of the following algorithm:

```
MyAlgorithm(root, num)
    min<-findMin(root)
    max<-findMax(root)
    while(min.key <= max.key && min != max)
        if((min.key + max.key)=num) return true
        if((min.key + max.key) < num)
            min<-successor(min)
        else
            max<-predeccessor(max)
    return false

```

According the CLRS book both `predeccessor()` and `successor()` functions time complexity depends on tree height which is $O(\lg n)$ in our case since red-black tree is balanced.

However, we have the `while` loop which theoretically can run almost `n` times.

For example, because the algorithm above is equivalent to searching for the number `num` in a sorted array, say we have this array and `num<-3`: $$ 1,2,3,4,5,6,7,8,9,10 $$ In this case we'll call `predecessor(max)` $8$ times which is almost $\Theta(n)$ or $\Theta((n-2)\lg n)=\Theta(n\lg n)$ asymptotically.

Am I wrong in my conclusions? How can I prove that the time complexity is indeed $\Theta(n)$?

# Answer
So we are given a binary search tree $T$ (we, however, do not require it to be balanced). Also we are given an integer; let's call it `target_number`. We wish to query whether there are two distinct nodes in $T$ such that the sum of their values equals `target_number`. In order to do that, we need two functions: `get_successor(x)` and `get_predecessor(x)`. Given a node `x` `get_successor(x)` returns the tree node whose value is larger than that of `x` and is the smallest such value. The definition of `get_predecessor(x)` is symmetric.

The algorithm is now (as in your question): point to the minimum node, and point to the maximum node. Compute the sum $S$ of the nodes pointed by the two pointers. If $S$ is less than the target number, move left pointer to its successor node. If $S$ is greater than the target number, move right pointer to its predecessor node. Otherwise, we have a match and return `true`.

```
query(root, target_number)
    left_finger  = the minimum node of the entire tree rooted at root
    right_finger = the maximum node of the entire tree rooted at root

    while left_finger != nil and right_finger != nil and left_finger != right_finger
        tentative_sum = left_finger.value + right_finger.value
        if tentative_sum < target_number
            left_finger = get_successor(left_finger)
        else if tentative_sum > target_number
            right_finger = get_predecessor(right_finger)
        else
            return true
    return false

```

Next, we need to give a strong argument that it runs, in fact, in $\Theta(n)$. Take a look at operation `get_successor`: If you start from the minimum node and visit the entire tree in successor order, you do $\Theta(n)$ work regardless the fact that `get_successor` runs in worst case $\mathcal{O}(\log n)$, and that is why: you visit each node at most three times: from the parent, returning from the left child and returning from the right child; we spend constant time at each node.

As you can see from the below diagram, each node `x` has at most 3 incoming arcs and has at most 3 outgoing arcs. Traversing each arc is $\Theta(1)$. So basically, if we start from a minimum node, and keep advancing to the successor nodes, we do essentially in-order traversal that is, however, iterative instead of recursive. Same argument for starting from the maximum node via `get_predecessor`.

Now, we do the same traversal but in "both directions" (the `left_finger` proceeds towards successor nodes and `right_finger` proceeds towards predecessor nodes, and we terminate (at latest) when the two fingers meet. Thus, running time is linear in tree size and space complexity constant since no recursion is involved.
> 2 votes

# Answer
First thing that popped into my mind, was using a hashmap (or just a key - storage) while iterating.

In the HashTable, I would store an addend for the sum, and while iterating I would look up if the value is in the list.

```
Addends[] //KeySet
for value in Values {
   if(Addends.contains(value) // Pair found
     return true
   Addends.add(Sum - value)
}

```
> -1 votes

---
Tags: algorithms, trees, balanced-search-trees
---


# Question
Title: Problems understanding the Union functionality of the Union-Find Algorithm
I am currently doing a course based on algorithms (Coursera). I've come across an algorithm called quick find. The course does have reference to Big O Notation. Despite the fact that I do not have much knowledge of Big O, I have been doing some basic reading.

---

***Implementation (Java):***

Initializes the array:

```
public QuickFindUF(int N)
{
    id = new int[N];
    for (int i = 0; i < N; i++)
    id[i] = i;
}

```

Checks if two input values are connected:

```
public boolean connected(int p, int q)
{
    return id[p] == id[q];
}

```

Union Implementation:

```
public void union(int p, int q)
{
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i < id.length; i++)
    {
        if (id[i] == pid)
        {
            id[i] = qid;
        }
    }
}

```

The `id` variable is a private instance variable.

---

***My Problem:***

**1)** In the study material it says:

> It takes N2 array accesses to process a sequence of N union commands on N objects

How can it take N2 if the `union` method only has a single for loop?

**2)** It also says that the **union** method takes

> at most 2N + 2 array accesses

What does this mean? My speculation is that 2N could mean that the array is accessed twice (line 7 and line 9 of the `union` method). I have no idea what + 2 refers to though.

---

I apologize if I have incorrectly stated something.

Any help would be highly appreciated. Thank You.

# Answer
> 1 votes
The answer to your first question is that while it takes (roughly) $N$ array accesses to perform one union operation, it takes (roughly) $N^2$ to perform $N$ of them. This is what is meant by the phrase "a sequence of $N$ union commands".

Regarding your second question, the first two operations are those that initialize pid and qid, and the body of the loop (which runs up to $N$ times) contains two more, one which compares an entry to pid, and another which assigns qid to the same entry.

---
Tags: algorithms, asymptotics, union-find
---


# Question
Title: Relevance of memory reads while calculating the time complexity of an algorithm
Can there be a genuine algorithm in which number of memory reads far outnumber the no. of operations performed? For example, number of memory reads scale with n^2, while no. of operations scale with only n, where n is the input size.

If yes, then how will one decide the time complexity in such a case? Will it be n^2 or only n?

# Answer
> 6 votes
For a memory read to be relevant to the algorithm, the information read in must be processed in some way.

If the information is never compared or used as input to any operator, it will not affect the algorithm and thus was unnecessary to read in the first place.

If there were an operator that could accept a variable number of inputs, a number that could grow without bounds, then and only then could you have the number of memory reads far outnumber the number of operations in the way you describe. For instance, if "sum" were a single atomic operation accepting any number of inputs, then you could have such an algorithm.

However, a model of computation where a single operation could utilize an unlimited number of inputs is not very interesting nor very useful for algorithmic analysis. It would essentially just push all the hard work to a lower level of abstraction. So you won't find such a model in any CS literature.

---

A paragraph from an MIT Open CourseWare PDF about communication networks as in Graph Theory makes a related point (related to what I said about just pushing the hard/interesting work to a different level of abstraction) in discussion of switch sizes:

> One way to reduce the diameter of a network (and hence the latency needed to route packets) is to use larger switches. For example, in the complete binary tree, most of the switches have three incoming edges and three outgoing edges, which makes them $3 \times 3$ switches. If we had $4 \times 4$ switches, then we could construct a complete ternary tree with an even smaller diameter. In principle, we could even connect up all the inputs and outputs via a single monster $N \times N$ switch, as shown in Figure 6.9. In this case, the “network” would consist of a single switch and the latency would be $2$.
>
> This isn’t very productive, however, since we’ve just concealed the original network design problem inside this abstract monster switch. Eventually, we’ll have to design the internals of the monster switch using simpler components, and then we’re right back where we started. So the challenge in designing a communication network is figuring out how to get the functionality of an $N \times N$ switch using fixed size, elementary devices, like $3 \times 3$ switches.

# Answer
> 3 votes
If you follow D.W.'s definition, a "memory read operation" is an operation and can read only one item from memory, so from that definition alone the number of operations *must* be the same or larger than the number of items read from memory. Let's assume that "reading memory" doesn't count as an operation.

If you read a memory location, and you do *anything* with it, including deciding whether to use it or not, that will be at least one other operation. So even if we don't count the memory read itself as an operation, you can only have more reads than other operations if you read memory "just for fun", that is the algorithm would have worked exactly the same if you hadn't read the memory.

Even if we accept that you might be reading memory "just for fun", this cannot change the big-O behaviour of the algorithm. That's because your algorithm can only have a finite number of read operations, so the number of reads could only be larger than the number of other operations by a constant factor. As soon as you have a loop, you have other operations controlling the loop. As an example, in the C language you could have a loop like

```
for (i = 0; i < n; ++i) { x; x; x; x; x; x; x; x; x; x; x; x; x; }

```

Assuming that the expression x; reads memory without any other operations, you still have only a dozen read operations per loop, so you still have O (n) operations to perform the loop, and O (n) read operations. The constant factor could be arbitrarily large, I could add a billion read operations in the loop, but that doesn't change the big-O behaviour.

# Answer
> 2 votes
No. In standard models of computation, each operation can read at most a constant number of memory locations. Therefore, the number of memory reads is at most $O(n)$, where $n$ is the number of operations.

# Answer
> 1 votes
If you assume that one memory-read corresponds to a single operation performed, then the number of memory reads may not outnumber the number of operations performed. This assumption is usually made in theory of computability and complexity theory.

As for complexities, there are two main computational complexities: SPACE complexity and TIME complexity which are actively studied in Computer Science.

# Answer
> 1 votes
An algorithm's time complexity is defined by the maximum rate at which any operation grows with respect to the problem size `n`. Thus, memory accesses will define the complexity of an algorithm if they increase at the fastest rate with respect to `n`. Thus the time complexity is $O(n^2)$ in your case.

As a note, memory accesses are quite expensive in practice, and in sparse linear algebra and graph processing codes often represent the bulk of the run time.

---
Tags: algorithms, algorithm-analysis, data-structures, asymptotics, memory-access
---