# Question
Title: Is there a discipline studying the prioritizing of repeated tasks?
Sorting algorithms have a huge literature behind them, and the algorithm I'm planning has some similarities to the topic, but I couldn't even find the correct search terms to know whether a field exists which studies such algorithms.

Imagine the following problem: there is a serial communication channel of a very low throughput, and you have to communicate with a number of devices through it. If all devices had the same priority, the solution would be obvious:

```
A B C D A B C D A B C D A ...

```

(In case of 4 devices, where "A" means "communicate with device A")

However, it can happen that some devices have a lower priority, and our goal is to improve the latency of high-priority devices, that is, the time between two consecutive communications with the same device should be small.

For example, we have devices A, B, C, and D with a high priority, and devices e, f, g and h, with a lower priority.

The naive solution would be to process the lower priority devices only every second turn, or every third turn, etc. Let's call this the "skipping factor".

*Example: higher-case letters are twice as important:*

```
A B e C D f A B g C D h A B e C D f A B g C D h ...

```

*Example: higher-case letters are three times as important:*

```
A B C e D A B f C D A g B C D h A B C D e ...

```

However, this solution quickly breaks down if the number of elements in the different priority categories differ greatly.

Take the example of "capital letters are twice as important", but with 8 capital letters and 2 lower case letters:

```
A B i C D j E F i G H j A B i ...

```

Here, the lower-case letters occur more often, even though that's opposite to our goal.

A solution would be to multiply the skipping factor by the ratio of the cardinalities of the priority groups. In the above example, the ratio is 8/2 = 4, we multiply it with the skipping factor of two, and we get 8, so after every 8 capital letter there can come a lower case one.

# The problem

The above examples were by far not exhaustive. Even the latest solution in the above example breaks down easily if there are more than two priority groups, and especially if the priority of the elements can change over time. This last constraint can be a very difficult one, as even "smarter" algorithms where every element has its own "timeout" counter ticking down can be fooled by cases where an element changes priority back and forth so that it never gets executed. The complexity also grows because we have to crawl through the lists of elements of every priority level on each occasion we select a new element to be sent.

# The question

I have many different ways in my mind to solve this problem, but I'm afraid of trying to re-invent the wheel, and arriving to a suboptimal solution. I'm therefore looking for a field of study which works with problems such as the one listed above. Does it have a name? Does it have a literature? I tried searching some terminology I guessed relevant for the topic, but I couldn't find anything.

# Answer
> 3 votes
By far the simplest solution is probabilistic. Let's suppose you have $k$ classes, and their relative importance is $c\_1,\ldots,c\_k$. Let's also suppose that there are $N\_i$ objects in class $i$. You want the frequency of appearances of each symbol in class $i$ to be proportional to $c\_i$.

Let $P = \sum\_i c\_i N\_i$ and $p\_i = c\_i N\_i/P$. At each step, choose class $i$ with probability $p\_i$, and output a random element from the class. The probability that a specific element from class $i$ appears is $p\_i/N\_i = c\_i/P \propto c\_i$.

To increase fairness among class $i$, instead of outputting a random element, you can keep a counter for each class (counting modulo $N\_i$), incremented any time the class is chosen, and output the corresponding element from the class.

A similar approach should work for fairness across classes, but here it's not as straightforward so I'll leave it to you.

---
Tags: algorithms, sorting
---


# Question
Title: Is smn theorem the same concept as currying?
I am studying the s-m-n theorem and the concept reminded me of currying.

From wikipedia article about s-m-n theorem:

> the theorem says that for a given programming language and positive integers m and n, there exists a particular algorithm that accepts as input the source code of a program with m + n free variables, together with m values. This algorithm generates source code that effectively substitutes the values for the first m free variables, leaving the rest of the variables free.

From an article about currying:

> Intuitively, currying says "if you fix some arguments, you get a function of the remaining arguments"

Seems like the same idea to me. The only reason why I am unsure is that the materials I came across on s-m-n don't mention currying (and vice versa), so I wanted to consult it to make sure I actually get it.

# Answer
Yes, it is the same thing.

Currying is a concept from $\lambda$-calculus. It is a transformation between $A \times B \to C$ and $A \to (B \to C)$. Think of this as "if we have a function of two arguments of types $A$ and $B$, then we may fix the first argument (of type $A$), and we will get a function of the remaining argument (of type $B$)". In fact, this transformation is an isomorphism. This is made mathematically precise by mathematical models of (typed) $\lambda$-calculus, which are cartesian closed categories.

There is a category of numbered sets. A numbered set is a pair $(A, \nu\_A)$ where $A$ is a set and $\nu\_A : \mathbb{N} \to A$ is a *partial* surjection, i.e., a map from numbers onto $A$, which may also be undefined. If $\nu\_A(n) = x$ then we say that $n$ is a *code* of $x$. In computability theory there are many examples. Whenever we encode some information with a number we get a numbered set. For instance, there is a standard numbering $\varphi$ of partial computable functions, so that $\varphi\_n(k)$ is the number computed by the partial computable function encoded by $n$ when applied to $k$. (The result may be undefined.)

A morphism of numbered sets is a *realized map* $f : (A, \nu\_A) \to (B, \nu\_B)$, which means that there exists $n \in \mathbb{N}$ such that $f(\nu\_A(k)) = \nu\_B(\varphi\_n(k))$ for all $k$ in the domain of $\nu\_A$. This looks complicated, but all it says is that $\varphi\_n$ does to codes what $f$ does to elements. It is the mathematical way of saying that "program $\phi\_n$ implements function $f$".

Here is the punchline: the category of numbered sets is cartesian closed. We may therefore interpret the typed $\lambda$-calulus in it, and ask what program implements the currying operation. The answer is: the program given by the s-m-n theorem.
> 16 votes

---
Tags: computability
---


# Question
Title: Sliding window protocol, calculation of sequence number bits
I am preparing for my exams and was solving problems regarding `Sliding Window Protocol` and I came across these questions..

> A 1000km long cable operates a 1MBPS. Propagation delay is 10 microsec/km. If frame size is 1kB, then how many bits are required for sequence number?
> A) 3 B) 4 C) 5 D) 6

I got the ans as C option as follows,

```
propagation time is 10 microsec/km
so, for 1000 km it is 10*1000 microsec, ie 10 milisec
then RTT will be 20 milisec

in 10^3 milisec 8*10^6 bits
so, in 20 milisec X bits;

X = 20*(8*10^6)/10^3 = 160*10^3 bits

now, 1 frame is of size 1kB ie 8000 bits
so total number of frames will be 20. this will be a window size.

hence, to represent 20 frames uniquely we need 5 bits.

```

the ans was correct as per the answer key.. and then I came across this one..

> Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).
>
> What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmission of two frames.
>
> (A) l=2 (B) l=3 (C) l=4 (D) l=5

as per the earlier one I solved this one like follows,

```
propagation time is 25 ms
then RTT will be 50 ms

in 10^3 ms 10^6 bits
so, in 50 ms X bits;

X = 50*(10^6)/10^3 = 50*10^3 bits

now, 1 frame is of size 1kb ie 1000 bits
so total number of frames will be 50. this will be a window size.

hence, to represent 50 frames uniquely we need 6 bits.

```

and 6 is not even in the option. Answer key is using same solution but taking propagation time not RTT. and their answer is 5 bits. I am totally confused, which one is correct?

# Answer
> 1 votes
> Frames of 1000 bits are sent over a 10^6 bps **duplex link** between two hosts.

When the data is transmitted using a duplex link, Round Trip Time (RTT) do not include the time taken by ACK frame to reach sender from the receiver. This is because the ACK frames are piggybacked with the data frames that are coming from the receiver for the sender (maybe a bit later).

Aforementioned, we must now calculate the number of frames transmitted during propagation time (rather than round trip time)

> $No.\ of\ frames = \left(25\*10^{-3}\*10^{6}\right)/10^3 = 25$

Thus, we will need minimum of $5\ bits$ to represent sequence number distinctly.

HTH

# Answer
> 0 votes
Thing is, the link is full duplex so only half of the capacity can be used by the sender. Bandwidth in calculation will be (10^6)/2 bps. So answer will be 5 bits.

# Answer
> -2 votes
Ignore the key... **Your answer is absolutely correct.**

However, you have missed a small point in the procedure.

> While calculating the window size, you must also consider the Transmission time.
>
> Trans. time = 1000bits / 10^6 bps = 1ms.
>
> Cycle time = 1ms +RTT = 51ms

01sec -\> 10^6 bits

51msec -\> 51\*10^(-3) \*10^6 bits = 51000bits = (51000/1000) frames = 51 frames

Sender window size is 51 frames. lets assume the receiver window size is 1 frame.

then, minimum number of bits required for sequence number =log(51+1)/(log2) *{base 2}* = 6 bits.

---
Tags: computer-networks
---


# Question
Title: Do most bitstrings expand if they halt when executed by a Universal Turing machine?
According to the counting argument, most bitstrings are incompressible or only slightly compressible. However, the counting argument does not work in the opposite direction, since there are an infinite number of bitstrings that are longer. So, the counting argument does not tell us whether most bitstrings will or will not expand when run on a universal Turing machine and halt.

Is it known whether most halting bitstrings will expand?

By 'expand' I mean that a bitstring $b\_1$ generates a bitstring $b\_2$ when run on a universal Turing machine, \begin{align\*} \mathcal{U}(b\_1)=b\_2, \end{align\*} such that the length of $b\_2$ is greater than $b\_1$ \begin{align\*} \ell(b\_2) \> \ell(b\_1). \end{align\*}

# Answer
Both can happen.

The counting argument applies to all TMs that always halt.

In the partial world, you can construct Turing machines for both extreme cases (and everything in between) like so. Assume $T$ is a Turing machine. Construct

```
T<(x) = if |T(x)| < |x| then return T(x) else loop

```

and

```
T>(x) = if |T(x)| > |x| then return T(x) else loop

```

Note that if `T(x)` loops, both `T<(x)` and `T>(x)` loop; that's not a problem. It's easy so see that for `T<`, all halting inputs contract, and for `T>` all expand.

Rice's theorem immediately shows that these expansion/contraction properties (and related ones) are undecidable, by the way.
> 4 votes

# Answer
Well, ... several (different!) scenarios:

I assume that U is a (fixed) UTM, you give it a string s = (TM,input), U(s) = TM(input) = either a finite output "f" or else DIS, the TM does not halt. Additional difficulty: "DIS" vs. "f requires enormous time" can not be resolved by just looking while waiting (in many cases).

Your question then might be: How often do we have |s| \< |f| (expansion), how often is |s| \>= |f| in the non-DIS cases.

1A. "Often" as a counter is void: Both cases appear (countably) infinitely often,namely:

Large s, short f: just stop the (short) TM, regardless of the (arbitrarily large) input, put f = empty word;

Short s, large f: TM consists of $(i)$ copy input to output to make for infinitely many cases, then $(ii)$ run BusyBeaver(7), producing a lot more output, in general run BB(7+log(log(|s|))).

1B. "Often" as a measure is more useful: Count each case with measure $2^{-|s|}$ ($s$ should be self-delimiting), throw away those DIS cases.

Compare $\mu(\le) = \sum\_{U(s)\ stops, |f| \le|s|} 2^{-s}$ with $\mu(\>) = \sum\_{U(s)\ stops, |f| \> |s|} 2^{-s}$.

My feeling is that a considerable fraction of machines just produces nothing or a short output, for any, even quite large, input, so probably $\mu(\le) \> \mu(\<)$ (no proof yet).

This might actually be decidable in finite time: If the difference between the two measures is larger than the measure of the unchecked cases, we are done.

2A/B. You include DIS in one of the cases (since nothing definite happens, the output is neither larger nor shorter than the input, a very large current tape contents might be blanked out later).

I guess that the side with DIS wins. Again, this might be (even easier) decidable by knowledge of finitely many cases.

3. You separate output and working tape and count DIS cases according to the actual output (which will not be allowed to shrink ... but still might grow). Very unclear situation for the $\mu(\le)$ part, while a DIS with current output longer than $|s|$ certainly goes into $\mu(\>)$.

**Summarizing:**

Interesting question,

*potential of completely answering it with finite effort* (unlike, *e.g.* the halting probability $\Omega$ in all its precision);

I do not know this answer.
> 0 votes

# Answer
There are a finite number of bitstrings with a length less than the output, but an infinite number with greater length. Therefore, it is much more likely a halting bitstring will produce a shorter bitstring than a longer bitstring.
> -2 votes

---
Tags: turing-machines, combinatorics, information-theory
---


# Question
Title: What is your approach to unveil the boundary cases when designing an algorithm?
When designing an algorithm for a given problem, sometimes I find it hard to foresee or clarify to myself what the boundary/edge/corner cases are. Not being able to come up with a decent number of the possible boundary/edge/corner cases causes one to make **implicit assumptions** about the problem at hand, which yields overlooked cases not to be accounted for, which is not good.

When reviewing the classic "Programming Challenges" by Steven S. Skiena and Miguel Revilla, one can read the following:

> This is why it is so essential to review the specifications carefully. Even when you may be sure that your program is correct, the judge may keep saying no. *Perhaps you are overlooking a boundary case or assuming something which just ain’t so*. Resubmitting the program without change does you absolutely no good. Read the problem again to make sure it says what you thought it did.

I think it would be useful to sort come up with a method to, given a problem statement and the problem's input domain, assist the algorithm designer with unveiling boundary cases.

On one hand, **knowing the upper and lower boundaries of your input data, helps you choose data types that can represent said values**.

Another useful technique I do, is to ask myself, **per each explicit assumption I can extract from the problem specification, what must exist for that assumption to be valid?** For example, if I am told that all values will be given as a sorted array, does that mean that the given list will never be empty?

I would like to continue putting together a set of thumb rules to assist ourselves in uncovering boundary cases.

# Answer
A good answer for this is over at Software Engineering https://softwareengineering.stackexchange.com/questions/72761/how-do-you-identify-edge-cases-on-algorithms

In general look at zero, empty string, max values, odd/even, nulls, sorted/random data where applicable including repeated testing with random data.

Also "think of everything that can go wrong" https://www.quora.com/How-do-you-identify-edge-cases-on-algorithms.
> 2 votes

---
Tags: algorithms, algorithm-analysis, case-based-reasoning
---


# Question
Title: Why don't imperative languages like C or Go support Haskell-like parametric polymorphism?
Why don't imperative languages support parametric polymorphism as powerful as whats in Haskell and OCaml?

More specifically if I call a function `foo(x)` that internally calls `bar(x)` which internally calls `baz(x)`, what prevents the type of parameter `x` from being inferred all the way down?

Is it possible to design an imperative language (like C or Go) with this behavior or must the language be functional?

**Question**: Does there exist a type system allowing for parametric polymorphism as powerful as Hindley-Milner, but suited for imperative languages and not functional languages. If such a type system exists what are it's advantages and disadvantages? I'm wondering if it *can* be done rather than *why* it hasn't been done.

# Answer
> 4 votes
The real answer is that the designers of those languages chose not to include it.

It's certainly technically possible. As has been said in the comments, Rust does, Java does, C# does, etc. However, there are some difficulties.

The first is in the choice of impelemtation strategy. Polymorphism is easy if you're working with Lambda Calculi and looking only at what reductions work. But when you want actual code that runs on a machine, there are two main strategies, each with their own tradeoffs:

* **Monomorphization:** For each specialization of your polymorphic function that's used, you make a specialized copy of it in the machine code emitted. This option is great when you're using a language that actually emits machine code, and tends to be fast, since you can optimize the different versions of your code. But, it tends to increase the size of your program.
* **Pointers:** The main reason you can't just use a function polymorphically is that you might give it arguments of different size, so when it's looking things up on the stack, it doesn't know their offsets. But if you always give it pointers to its arguments, then it can lay things out nicely. This way is simpler, but has slowness from an extra layer of indirection.

As for why the particular languages didn't use it, for C it's mostly historical. It wasn't really a mainstream thing when it was made, and it hasn't made its way into the main language. For Go, the decision has been quite controvertial, but again their main goals were simplicity, concurrency and code whose performance was easy to reason about.

Also, polymorphism breaks type soundness in the presence of mutable variables, which is why Rust only allows polymorphic functions, and ML has the value restriction.

# Answer
> 1 votes
As others have pointed out, there is nothing preventing an imperative language from using something similar to the Hindley-Milner type system and providing parametric polymorphism. I should point out that something very similar can actually be done in C, through use of the `_Generic` keyword which provides compile-time polymorphism / type inference. In the following program, the "function" `foo` (actually a macro definition) calls `bar` and then `baz` which infer the types all the way down. At that point there is an implementation for each base type we care about.

```
#include <stdio.h>

#define foo(x) (printf("calling foo\n"), printf("%s\n", bar(x)))
#define bar(x) (printf("calling bar\n"), baz(x))
#define baz(x) _Generic(x, int : "int", char* : "char*", void* : "void*")

int main() {
    foo(42);
    foo("hello");
    foo((void*)0);
    return 0;
}

/* output:
calling foo
calling bar
int
calling foo
calling bar
char*
calling foo
calling bar
void*
*/

```

---
Tags: programming-languages, functional-programming, language-design, imperative-programming
---


title: Maximisation of graphs weight

text:
# Question
Title: Maximisation of graphs weight
I have a graph related problem. Let $G$ be an undirected weighted graph of $N$ nodes. I want to find $p$ independent (they have no edge linking them) sub-graphs of $m$ nodes in a way that the total weight is maximized.

For example, let $G$ be a graph of $16$ nodes, I want to find $4$ sub-graphs of $4$ nodes with $w\_1, w\_2, w\_3, w\_4$ as their weights (sum of the weights on the subgraph's edges) I want to determine the $4$ subgraphs that will maximize $w\_1+w\_2+w\_3+w\_4$.

Is this a classic graph problem? Is there already an algorithm for this? I am not very experienced with graphs and my research on the net was only confusing. Any ideas on how to approach this?

Thank you for your help

# Answer
> 0 votes
It is definitely not a classic graph problem such as the shortest path, maximum-flow, or graph coloring problem. But your problem, in its general form, seems to solve the Independent set problem, which is $NP$-complete.

Assume that you have a polynomial time algorithm $A(G,m,p)$ solving this problem. Then take $m=1$ and call $A(G,1,p)$ for $p=N,N-1,...,2,1$ (at most $N$ times) until you find a solution. When $m=1$, each subgraph has only one node and so its weight is 0, which is maximum for a single node graph. Furthermore, these nodes are not connected by an edge, and so they are not adjacent, i.e. they are independent.

If this procedure finds a solution for the maximum $p$ less than $N$, then this means we have a maximal independent set, since we have exactly $n$ nodes (subgraphs) with no edges between them, i.e. independent.

Once your problem is $NP$-complete, you could try any approximation algorithm including Linear or Integer programming.

---
Tags: algorithms, graphs, optimization
---


# Question
Title: How does continuous computer vision works?
First: I have programmed a few programs dealing with computer vision (not with libraries but from scratch):

* Simple Character and Figure Recognition
* Character and Figure Recognition with Neural networks
* Facial recognition

so I am not asking for details on these.

The characteristic of all my programs is that once you focus your camera on something you want to analyze, you hit a command (it can be through several means- serial, voice orders, etc- it is not relevant how) and the system takes a photo and analyze it, then produce a result in some cases the camera is deactivated since it is resource intensive.

---

Following all that introduction, my question is:

How do the programs that do *continuous* recognition work?

You have seem them, the camera is all the time on and it continually recognize or process things. Does it just do all the processing every frame? Or perhaps do the processing in a multithreaded way (for resource intensive processing)?

My apologies if the question is too beginner-like. I would really like to modify my work and increase my knowledge

# Answer
It depends on what you're recognizing, but I'm familiar with two basic techniques:

1. Apply the recognition algorithm to each frame of the video. Be fast enough that you can run on every frame of video. This is probably the most common approach.
2. Recognize the object once, in one frame. Then use motion tracking to keep track of the location of the object in subsequent frames. In this way, you might be able to run the recognition algorithm (say) once every 10 frames and then use motion tracking to keep track of where it is in the remaining frames. This has some tradeoffs (some latency to detect the object when it first occurs; fast motion or fast panning can cause loss of the object), but is another possible alternative.
> 3 votes

---
Tags: machine-learning, pattern-recognition, facial-recognition
---


# Question
Title: Finding a graph where the edge set satisfies a set of integer equations
There is an easy and hard version of the problem I am asking about, so I will start with the easy to make for clearer reading.

Suppose that we are have a set of vertices $V =\\{v\_1,v\_2,...,v\_n\\}$ and sets $S\_1,S\_2,...,S\_m \subset V \times V$. Let

$s\_{ijk} = 1$ if $\ (v\_j,v\_k) \in S\_i $, 0 otherwise.

Given integers $\ k\_1,...,k\_m$ we want to find whether the set of equations

$$\begin{align\*} k\_1 &= \sum\_{j,k} a\_{jk} s\_{1jk}\\ k\_2 &= \sum\_{j,k} a\_{jk} s\_{2jk}\\ &\vdots\\ k\_m &= \sum\_{j,k} a\_{jk} s\_{mjk} \end{align\*}$$

has a solution with all of the $a\_{11}, a\_{12}, ... , a\_{nn}$ indices in $\\{0,1\\}$.

**Explanation**

This set of 0-1 equations is equivalent to checking whether or not there exists a (simple directed) graph with $\ k\_i$ edges from each of the subsets $\ S\_i$. My immediate instinct is that this problem is solvable in polynomial time, say by a straightforward backtracking algorithm. Another possibility is to solve the system using the appropriate technique (say Hermite Normal Form) and then applying LLL to get a short basis for the solutions. The proof that this is solvable in polynomial time isn't entirely clear to me though.

**Example**

We are given $\ v\_1, v\_2, v\_3.$

$\ S\_1 = (v\_2, v\_3) $

$\ S\_2 = (v\_1, v\_3), (v\_2, v\_3)$

$\ k\_1 = 1, k\_2 = 0$

We return false because we have to pick $\ (v\_2,v\_3)$ but this forces $\ k\_2 \> 0$ since we have to pick it in the second set as well.

**The harder version:**

Does there exist a (directed) graph $G$ with $\ k\_i $ edges from each subset $\ S\_i$ such that

$\ G = cl(G)$,

where $\ cl(G) $ denotes the transitive closure?

We can solve this by testing the feasibility of a set of 0-1 linear equations and inequalities, but as we should know that problem is NP hard in general (unlike solving linear integer equations). However it does not look at all trivial to show that this particular problem is NP hard.

**Questions**

Can the first problem always be solved in polynomial time?

Is the second problem NP hard?

# Answer
You are asking two questions. I will answer the first one. Your first problem is NP-hard, by reduction from exactly 1-in-3 positive 3-SAT.

Let $\varphi$ be a positive 3-CNF formula with $m$ clauses and at most $n^2$ variables $x\_i$. Label each edge $(v\_i,v\_j)$ with a distinct variable $x\_{ij}$. Each set $S\_i$ will correspond to a clause of $\varphi$ as follows: the set $S\_i$ contains one edge $(v\_i,v\_j)$ for each variable $x\_{ij}$ that appears in that clause. Let $k\_1=k\_2=\cdots = k\_m=1$.

Now the resulting system of linear equations has a solution if and only if $\varphi$ has an assignment where every clause has exactly one of its three variables set to true.
> 1 votes

---
Tags: complexity-theory, graphs, np-hard, decision-problem
---


# Question
Title: What is instruction throughput and instruction latency?
I was reading an article on an alternative method of modulo reduction and i couldn't understand the following excerpt (Those in bold) :

"A single 32-bit division on a recent x64 processor has a t**hroughput of one instruction every six cycles** with a **latency of 26 cycles**. In contrast, a multiplication has a throughput of one instruction every cycle and a latency of 3 cycles."

# Answer
Latency = time from the start of the instruction until the result is available. If your division has a latency of 26 cycles, and you calculate (((x / a) / b) / c), then the result of the division by a is available after 26 cycles. That's when the division by b can start, with the result available after 52 cycles, and the result of dividing by c is available after 78 cycles.

The throughput is one division every six cycles, which means you can start another division every six cycles. So if you want to calculate x/a, y/a, z/a, u/a, v/a, the five divisions can start at cycles 0, 6, 12, 18, 24, and the results are available at cycles 26, 32, 38, 44, and 50.

As an exercise, figure out how long it takes to evaluate (((x / a) / b) / c), (((y / a) / b) / c), (((z / a) / b) / c), (((u / a) / b) / c) and (((v / a) / b) / c) .
> 10 votes

# Answer
Latency is the number of processor clocks it takes for an instruction to have its data available for use by another instruction. Therefore, an instruction which has a latency of 6 clocks will have its data available for another instruction that many clocks after it starts its execution.

Throughput is the number of processor clocks it takes for an instruction to execute or perform its calculations. An instruction with a throughput of 2 clocks would tie up its execution unit for that many cycles which prevents an instruction needing that execution unit from being executed. Only after the instruction is done with the execution unit can the next instruction enter.
> 3 votes

---
Tags: terminology, computer-architecture, cpu
---


# Question
Title: Greedy algorithms: Minimum sum number pairing
> Given $n$ real numbers (where $n$ is even) find a pairing which minimizes the maximum sum of a pair.

I think the optimal pairing is obtained by sorting the original set, pairing the first element with the last one, and so on. But I get stuck trying to prove it.

I tried use the "difference reduction method", examining differences between an optimal answer and the "greedy" answer, and trying to get the greedy from the optimal without losing optimality, but I didn't reach anything. Any idea?

# Answer
> 5 votes
Suppose that numbers are $x\_1, \ldots x\_{2n}$, and let us rename them as $a\_1, \ldots a\_n, b\_1, \ldots, b\_n$, where $a\_i \geq b\_j$ for any $i, j$, $a\_1 \geq a\_2 \geq \ldots \geq a\_n$, and $b\_1 \leq b\_2 \leq \ldots \leq b\_n$. In this notation, the suggested optimum solution is $(a\_1, b\_1), \ldots (a\_n, b\_n)$.

Given some arbitrary pairing, let us show we can reduce it to the right pairing without increasing the maximum sum of a pair. This shows that the expected correct solution is at least as good as any other. Equality might hold, eg. if all the values are the same, then any pairing is the joint best.

First suppose that there is some pair $(a\_u, a\_v)$. Then since there are an equal number of $a$'s and $b$'s, there must also be some pair $(b\_s, b\_t)$. Clearly $a\_u + a\_v \geq b\_s + b\_t$, furthermore $a\_u + a\_v \geq a\_u + b\_s$ and similarly $a\_u + a\_v \geq a\_v + b\_t$. So if we replace the pairs $(a\_u, a\_v), (b\_s, b\_t)$ by $(a\_u, b\_s), (a\_v, b\_t)$, we have reduced the maximum sum of a pair, or at worst kept it the same.

So now assume that our pairing is of the form $(a\_{i\_1}, b\_{i\_1}), \ldots (a\_{i\_n}, b\_{i\_n})$, but that it's not $(a\_1, b\_1), \ldots (a\_n, b\_n)$. There must be at least one pair of pairs, $(a\_j, b\_k)$ and $(a\_l, b\_m)$, where $j \< l$ but $k \> m$. (Otherwise, the $b$'s are in the same order as the $a$'s, which means it's the suggested solution.)

This means that $a\_j \leq a\_l$ and $b\_k \leq b\_m$. So $a\_l + b\_m \geq a\_j + b\_k$, also $a\_l + b\_m \geq a\_j + b\_m$, and similarly $a\_l + b\_m \geq a\_l + b\_k$. So $(a\_l, b\_m)$ must be the bigger of $(a\_j, b\_k), (a\_l, b\_m)$, and replacing those two pairs with $(a\_l, b\_k), (a\_j, b\_m)$ can only reduce the maximum (or keep it the same).

This shows that whatever pairing we start out with, we can swap pairs until we reach the suggested solution, without making the maximum sum any bigger. So the suggested solution must be the best.

I believe you could collapse the two steps into a single argument since both are very similar and rely on showing that two pairs can be 'flipped' without making the maximum sum any bigger. However I find it easier to imagine in two stages.

---
Tags: correctness-proof, greedy-algorithms
---


# Question
Title: Find non-smooth function that meets conditions
I learned the following theorem in class: "If $T(n)$ is asymptotically non-decreasing and $f(n)$ is smooth, then $T(n) = O(f(n)|n=b^k, k=integer)$ implies $T(n) = O(f(n))$."

I'm trying to show using a counterexample that this theorem doesn't hold if $f(n)$ is non-decreasing but not smooth. Smoothness means that $f(bn) = O(f(n))$.

From my understanding, the above conditions mean that $f(n)$ must be an exponential. Other than that, how would I go about finding a function that meets the conditions outlined above?

Since this is a homework problem, please don't give an actual function, but instead give a series of steps to take to find the function. Thanks.

# Answer
> 0 votes
As you mention, the function $f(n)$ needs to grow fast, though not necessarily exponentially fast ($n^{\log n}$ also works, for example). Nevertheless, let's take your suggestion $f(n) = 2^n$ for definiteness. Simplifying things a bit, you are looking for a function $T(n)$ such that

1. $T(n)$ is non-decreasing.
2. $T(2^k) = 2^{2^k}$.
3. $T(n)$ is not $O(2^n)$.

To satisfy the third condition, we would like $T(n)$ to be "as large as possible" given the first two conditions.

> (a) Find the function $T(n)$ which is "as large as possible" subject to the first two conditions.
>
> (b) Show that it satisfies the third condition as well.
>
> (c) For which functions $f(n)$ does this construction work?

---
Tags: algorithm-analysis
---


title: CNF and small-depth circuits

text:
# Question
Title: CNF and small-depth circuits
I'm reading on small-depth circuits. Since every formula can be turned into a CNF formula, which has depth at most 3, why should we study deeper circuits? Is it because convertion to CNF may result in an explosive blow-up? If so, can you give an example?

# Answer
Much of the interest in circuits stems from the following implication: $$ \mathsf{NP} \not\subseteq \mathsf{P/poly} \Longrightarrow \mathsf{P} \neq \mathsf{NP}. $$ In words, if we show that some problem in NP doesn't have polynomial size circuits then we have proved that P≠NP.

Unfortunately, we don't really know how to prove lower bounds on general circuits. We do know how to prove lower bounds for constant depth circuits and for monotone circuits, which is the main reason we are interested in these models at all.

We already know of functions in $\mathsf{NP}$ which don't have polynomial size constant depth circuits. Unfortunately, these functions are in $\mathsf{P}$, and so won't help in proving $\mathsf{NP} \not\subseteq \mathsf{P/poly}$. What we want is to improve our techniques so that they apply for circuits with polynomial depth — that would show that $\mathsf{NP} \not\subseteq \mathsf{P/poly}$.

Now, to your question. While it is true that every function can be represented as a CNF and so as a constant depth circuit, sometimes allowing larger depths makes a big difference. For example, Parity has an exponential size CNF (and even exponential size constant depth circuits), but has a polynomial size circuit of logarithmic depth (and even a polynomial size *formula*). In other words, Parity exhibits an exponential blowup when converting from circuit to CNF. This shows that lower bounds on CNFs (probably) won't be able to separate P and NP according to the program laid out above.
> 1 votes

---
Tags: circuits
---


title: Randomized algorithm for 3SAT

text:
# Question
Title: Randomized algorithm for 3SAT
There is a very simple randomized algorithm that, given a 3SAT, produces an assignment satisfying at least 7/8 of the clauses (in expectation): choose a random assignment. A random assignment satisfies each clause with probability 7/8, and so linearity of expectation shows that the expected fraction of clauses satisfied by a random assignment is 7/8.

Can this be done in a deterministic way? If so, why are we interested in the randomized algorithm?

# Answer
The random assignment algorithm can be derandomized (made deterministic) using the method of conditional expectations.

Let the 3SAT instance consist of clauses $C\_1,\ldots,C\_m$. During the algorithm we will assign values to variables. The *score* of a clause $C$ is defined as follows:

* If $C$ is satisfied then its score is 1.
* If $C$ is not satisfied and has $k$ unassigned literals then its score is $1-2^{-k}$.

Initially the score of each clause is $1-2^{-3} = 7/8$, and so the total score is $(7/8) m$. We now assign values to the variables $x\_1,\ldots,x\_n$ in order. Suppose that we have assigned values to variables $x\_1,\ldots,x\_{i-1}$, and the current total score is $S = S(C\_1)+\cdots+S(C\_m)$. Let $S\_0,S\_1$ the total score if we assign the values $0,1$ (respectively) to $x\_i$. I claim that $S\_0(C)+S\_1(C) = 2S(C)$ for any clause $C$, and so $S\_0 + S\_1 = 2S$. Indeed:

* If $C$ is satisfied (only given $x\_1,\ldots,x\_{i-1}$) or doesn't contain $x\_i$ then $S\_0(C) + S\_1(C) = 2S(C)$.
* Suppose that $C$ contains $k$ unassigned literals, including $x\_i$. Then $S(C) = 1-2^{-k}$, $S\_0(C) = 1-2^{-(k-1)}$, and $S\_1(C) = 1$. Therefore $$ S\_0(C) + S\_1(C) = \[1 - 2 \cdot 2^{-k}\] + 1 = 2(1 - 2^{-k}) = 2S(C). $$
* A similar argument works when $C$ contains $\bar{x}\_i$.

Since $S\_0 + S\_1 = 2S$, either $S\_0 \geq S$ or $S\_1 \geq S$ (possibly both). Therefore there is some assignment to $S$ such that after the assignment, the new score is at least $S$.

The initial score is $(7/8)m$ and the algorithm ensures that the score never decreases. At the end, the score of a clause $C$ is 1 if it is satisfied and $1-2^{-0}=0$ otherwise. Thus the final assignment satisfies at least $(7/8)m$ clauses.

Given that there is a deterministic algorithm, why are we interested in the randomized one? There are several reasons:

1. The randomized algorithm is much simpler.
2. The randomized algorithm is potentially faster.
3. The randomized algorithm can be converted to a deterministic one using the method of conditional expectations; we can think of it as a *recipe* for constructing a deterministic algorithm.

More generally, it is conjectured that every randomized polytime algorithm for a decision problem can be derandomized (this is the $\mathsf{P}=\mathsf{BPP}$ conjecture). Randomized algorithms will still be interesting for all the reasons enumerated above.
> 7 votes

---
Tags: randomized-algorithms, 3-sat
---


title: Universal family of hash functions

text:
# Question
Title: Universal family of hash functions
How to prove that a $k$-universal family of hash functions is $(k-1)$-universal family?

I tried to prove it by definition of k-universal family of hash functions but I didn't know how to use the definition.

If I prove it, Is it necessary that a $1$-universal family of hash function is universal family?

**Definitions:**

Let $U$ be a universe of keys, and let $H$ be a finite collection of hash functions mapping $U$ to $\\{0,\dots,m-1\\}$.

$H$ is **universal** if $\forall x,y\in U$ where $x\neq y$: $\Pr\[h(x)=h(y)\] \leq \frac{1}{m}$ where $h$ is chosen randomly from $H$.

$H$ is **k-universal** if $\forall x\_1,x\_2,\dots,x\_k\in U$ distinct elements and $\forall i\_1,i\_2,\dots,i\_k\in \\{0,\dots,m-1\\}$: $\Pr\[h(x\_1)=i\_1 \land h(x\_2)=i\_2 \land \dots \land h(x\_k)=i\_k\] = \frac{1}{m^k}$ where $h$ is chosen randomly from $H$.

# Answer
> 2 votes
For your first question, here is a hint: $$ \Pr\[h(x\_1) = i\_1 \land \cdots \land h(x\_{k-1}) = i\_{k-1}\] = \\ \sum\_{i\_k} \Pr\[h(x\_1) = i\_1 \land \cdots \land h(x\_{k-1}) = i\_{k-1} \land h(x\_k) = i\_k\]. $$

Regarding the connection between *universal* and *$k$-universal*: Consider the family consisting of all constant functions. This family is 1-universal but not universal (for $|U|\>1$).

However, it turns out that every 2-universal family is universal (exercise). The converse isn't true: for example, the family of all functions $h$ such that $h(x\_1) = 0$ is universal but not 2-universal (for $m\>1$).

---
Tags: hash
---


# Question
Title: Is there a name for the "tree" aproach to listing things?
I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question.

Suppose we're trying to list all elements of the set $$C(r) = \\{(x,y,z) \in \mathbb{N}^3 : \sqrt{x^2+y^2+z^2} \leq r\\}.$$

An obvious approach would be this: first, list all integers between $0$ and $r$; these become our $x$-values. Then, for each $x$-value, list all integers between $0$ and $\sqrt{r^2-x^2}.$ These become our $y$ values. Then, for each $(x,y)$ pair, list all integers between $0$ and $\sqrt{r^2-x^2-y^2}$. These become our $z$ values. We can visualize this process as a tree; the branches of the tree are the elements of $C(r)$.

A similar approach can be applied to solve the Knapsack problem a little quicker than brute force. Begin by forgetting the value of each item and just focusing on its weight. Now go through the items from left to right, bifurcating each node into two as you go, so that one edge corresponds to "take the item" and the other corresponds to "don't take the item." If taking the item would send you overweight, you refrain from adjoining the edge that corresponds to taking the item, but you still adjoin the one corresponding to not taking the item. In the end, we get a binary tree whose branches can be viewed as subsets of the set of items, which ultimately means fewer numbers that need comparing.

Well, I can see my computer running out of memory pretty quickly trying to do this - I'm sure there's better approaches out there - but nonetheless, if there's a name for this kind of thing, I'd like to know it.

# Answer
Your technique is known as *exhaustive search* (with some pruning). It consists of trying all possibilities. In many cases, the way to implement exhaustive search is using a search tree. There are several possible optimizations:

* Tree pruning algorithms like A\* avoid going through paths which are known to be suboptimal.
* Greedy algorithms, when they apply, are able to make the correct choice at each step without going over all possibilities.
* Dynamic programming corresponds, morally, to exploring a DAG instead of a tree, thus reducing the number of vertices explored. (The actual details are rather different.)
> 3 votes

---
Tags: algorithms, terminology, trees, lists
---


title: Union of R.E. and Non R.E. language

text:
# Question
Title: Union of R.E. and Non R.E. language
Let \begin{align\*} L\_1 &=\\{\langle M,w\rangle \mid M\text{ halts on }w\\}\\ L\_2 &=\\{\langle M,w\rangle \mid M\text{ does not halt on }w\\}\\,. \end{align\*} Here $M$ represents encoding of a Turing machine (T.M.) and $w$ is the input string. What is the class of $L=L\_1 \cup L\_2$?

---

I read that the union would be a regular language as a string has to belong to either $L\_1$ or $L\_2$ (i.e., halt or not halt) so their union would be a regular language.

I have a doubt. Suppose we assume $L$ as a recursively enumerable (R.E.) language then there exists a T.M. which halts on all "yes" cases. Here yes cases means strings which belong to either $L\_1$ or $L\_2$. So, if a string belongs to $L\_2$, then the T.M. should halt which means that we are able to halt and say "yes" even if machine doesn't halt on this string (according to condition of $L\_2$). This solves halting problem and hence assumption is not correct and so $L$ should be non recursively enumerable.

I know that there is some flaw in the explanation given above but I am not able to find it.

Can someone please help me?

# Answer
The language $L = L\_1 \cup L\_2$ consists of all pairs $\langle M,w \rangle$ where $M$ is a description of a Turing machine and $w$ is a word. This language is not necessarily regular (it depends on the exact encoding), but it is certainly decidable. All you have to do, given an input, is to decide whether it is of the form $\langle M,w \rangle$.

Note that deciding $L$ bears no relation to the halting problem. My description of $L$ doesn't refer to whether $M$ halts on $w$ or not. Here is a similar example. Let $f$ be an uncomputable integer-valued function. The function $g := 1-f$ is uncomputable as well, yet $f + g$ is computable.
> 10 votes

# Answer
> a string has to belong to either L1 or L2 (i.e halt or not halt) so their union would be a regular language.

This is a false statement. There is no chain of reasoning so it's hard to tell where the problem is.

Maybe it's a language issue. Consider this statement:

> *Every* string (over some alphabet $\Sigma$) belongs to either $L\_1$ or $L\_2$. (\*)

If that is true, then $L\_1 \cup L\_2 = \Sigma^\*$ which is indeed regular.

Whether it *is* true depends on the encoding $\langle \\\_,\\\_ \rangle$. If it is surjective¹, then (\*) is true; otherwise it's not.

---

> I have a doubt. Suppose we assume L as recursively enumerable language then there exists a T.M which halts on all "yes" cases. Here yes cases means strings which belong to either L1 or L2. So, if a string belongs to L2, then the T.M should halt which means that we are able to halt and say "yes" even if string doesn't halt (according to condition of L2). This solves halting problem and hence assumption is not correct and so L should be non recursively enumerable.

You make a basic (but understandable and common) mistake: somebody promises you that an algorithm exists, and you go ahead an assume you know how the algorithm must work: clearly, the algorithm must check if either case happens! No, not if membership in the union can be checked in *other*, simpler ways.

This misconception is very widespread among novices. My favorite related example is the computability of whether $\pi$ contains $0^k$. Try to understand why that's the case, then revisit this question.

---

Now, for *arbitrary* $L\_1 \in \mathrm{RE}$ and $L\_2 \not\in \mathrm{RE}$ we don't know anything.

* If $L\_1 = \emptyset \in \mathrm{RE}$ we get $L\_1 \cup L\_2 = L\_2 \not\in \mathrm{RE}$.
* If $L\_1 = \Sigma^\* \in \mathrm{RE}$ we get $L\_1 \cup L\_2 = \Sigma^\* \in \mathrm{RE}$.

---

1. This is certainly possibly: Both the sets of all TMs and the set of all words are countably infinite, so we know there are bijections between either set and $\mathbb{N}$. The bijections can be lifted to pairs, and the result then bijectively maps to any universal language (your choice of alphabet). Of course, nobody outside of recursion theory uses such an encoding; it's unreadable. Then, the hardness of $L\_1 \cup L\_2$ depends on the specific encoding at hand.
> 5 votes

---
Tags: computability, turing-machines
---


# Question
Title: Under which field of computer science does cloud computing fit?
I am trying to categorise subfields of computer science. Wikipedia does a good job of it.

However, it cannot fit cloud computing, virtual machines, containers and related technologies in any of the mentioned fields.

Does it fit under computer architecture or do we need a new sub-field?

I know categorising topics under subfields might not seem that useful but it really helps me put things into perspective.

# Answer
> 3 votes
According to the ACM classification, cloud computing belongs to:

* Distributed architectures, under Architectures, under Computer systems organization.
* Network services, under Networks.
* Distributed systems organizing principles, under Software system structures, under Software organization and properties, under Software and its engineering.
* Storage architectures, under Information storage systems, under information systems (as *Cloud based storage*).

So cloud computing is at the intersection of Computer architecture, Networking, Software engineering, and Information systems.

Cloud computing could also be considered its own area, since it has a dedicated conference, SoCC.

# Answer
> 2 votes
Distributed computing is pretty closely related. It studies sytems comprised of networked computers.

A lot of what you count as cloud computing I wouldn't necessarily put under the label "computer *science*", since it's in large parts engineering. E.g. the different methods of fooling programs running on the same physical machine believe that they're actually on their own machine and talk to the rest of the world via a network. But as usual with there are no hard cutoffs between science and engineering.

---
Tags: computer-architecture
---


# Question
Title: Is the output of a Mealy/Moore automaton a regular language?
1. How can I prove that the output sequence of Mealy Moore Machine is a Regular Language ?
2. And what if transition outputs more than one character ? How can we prove for this case that the language in (1) and (2) are same ?

Can I do something like this -

The right side one is Mealy Machine. So can I prove like making a machine in left with transitions using output sequence of Mealy Machine ?

# Answer
> 2 votes
By discarding the input-letters you only consider the output language of the respective Mealy automaton. Effectively you obtain a finite state automaton that recognizes the output language and because it is a finite state automaton, which may be non-deterministic, the language it accepts is regular.

The length of the output of a Mealy-transition is irrelevant as you may have for example$aa\in\Gamma$, where $\Gamma$ denotes the output alphabet of a Mealy automaton.

---
Tags: regular-languages, automata, finite-automata, transducers
---


# Question
Title: Understanding the geometrical interpretation of word2vec
I'm trying to understand how the $word2vec$ method actually nudges word vectors of similar semantic/syntactic content closer together in the word vector space.

I've read here (Quora answer) that it's because $word2vec$ tries to maximise the probability of target word $w$ given context $c$, and that this probability is roughly inversely proportional to the distance between $w$ and $c$ in the word vector space. I don't really see why the latter is the case though.

# Answer
If two words tend to appear in the same context, then they will tend to receive a similar word vector.

For instance, a large corpus might contain sentences like "I really love Fuji apples" and "I really love Gala apples". From this we can see that "Fuji" and "Gala" have appeared with the same context (in this case the context is "love _ apples", if by context we look one word to the left and one word to the right). This will tend to cause the optimization algorithm to assign Fuji and Gala vectors that are similar.

As you can see, words that tend to be associated with the same surrounding context will often have a similar semantic content. Not always, but it's a good heuristic.
> 2 votes

---
Tags: optimization, machine-learning, natural-language-processing
---


# Question
Title: If we allow a database, what complexity class it is?
Let we have some problem $A$. Input length is $n$. Now we write a database that will store info about some positive instances of problem $A$. For every $n$ size of $n^{th}$ sector of DB is $O(f(n))$. $f(n)$ is some function.

Then we assume that some solver for problem in complexity class $C$ (for example, $GI$) can use this DB to solve the problem $A$. Can we say that $A\in C/f(n)$ ($C$ solver with advice of size $f(n)$)?

# Answer
You can say anything you want, if you define your terms and your notation and make it clear what you are saying.

In this case I would not expect someone to know what you mean by $M/f(n)$ or by $A \in M/f(n)$. Something like $P/\text{poly}$ is well-understood, but $P$ is a complexity class, and $M$ is a specific machine. Rather than risking confusion, just say what you mean -- it only takes a sentence to say that the problem can be decided by $M$ using advice of size $f(n)$.
> 3 votes

---
Tags: complexity-theory, databases, oracle-machines
---


# Question
Title: compute a gradient with "minimal" colorstops from a ordered set of RGB colors
I got a array of colors that are closely related = most of the time there is no sharp transition between color\[n\] and color\[n+1\].

Exemple of such an array of colors \[**0**,.1,.2,.3,.4,.5,.6,.7,.8,.9,**1.0**,.8,.6,.4,0.2,**0**\]

You'll notice that there are 3 "special" values. The colors
slowly increase from value 0 to 1 (in 10 steps) then
decrease more rapidly from 1 to 0 (in 5 steps).

So our array could also be described this way :

an array of 16 colors where
Color\[0\] whose value is 0 evolves linearly until
color\[10\] whose value is 1 evolves linearly to
color\[15\] whose value is 0

I don't really care about the length of my initial array. It will be stretched (interpolated) so instead of using indexes it makes more sense to use percentage values
index 0 /15 = 0%
index 10 /15 = 66%
index 15 /15 = 100%

so the initial array could be rewritten like this \[{0, 0%}, {1, 66%}, {0, 100%} \]

This last notation is close to what is called a gradient in svg or css. The special color are named "colorstops" and gradients are written this way
linear-gradient(black 0%, white 66%, black 100%);

One could notice that some gradients are equivalent

linear-gradient(black 0%, white 100%) =
linear-gradient(black 0%, grey 50%, white 100%) =
linear-gradient(black 0%, lightgrey 25%, grey 50%, darkgrey 75%, white 100%)

like

interpolation\[0, 1\] =
interpolation\[0, .5, 1\] =
interpolation\[0, .25, .5, .75, 1\]

**So my challenge is to go from
\[0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1,.8,.6,.4,.2,0\]
to
linear-gradient(black 0%, white 66%, black 100%)
and not the naive
linear-gradient(
black 0%,
grey++++ 6%,
grey+++ 13%,
grey++ 20%,
grey+ 26%,
grey 33%,
grey- 40%,
grey-- 46%,
grey--- 53%,
grey---- 60%,
white 66%,
grey--- 83%,
grey- 80%,
grey+ 86%,
grey+++ 92%,
black 100%)**

The expected size of color array is no more that 2000 RGB colors and the goal for color-stops is no more that 10 and ideally 2.

**EDIT** in fact what i want to do is compute the blue lines like on the following graph

# Answer
What you want to do is fit a piecewise linear function to your data.

# No noise

If the data is perfect and has no noise, this is easy:

* Form a line from the first points. Remember those two points as the endpoints of the line.
* If the third point lies on this line, discard the right endpoint and replace it with the third point. Otherwise, start a new line from the second point and third point.
* Repeat.

That can be done with a simple linear scan.

# Noisy data

If the data is imperfect and noisy, you want to do a best fit of a piecewise linear function to your data.

There's no universal answer, as there are multiple ways to fit a piecewise linear function. If you have $n$ points, you can always get a perfect fit by drawing $n-1$ lines (one line between each consecutive pair of points), but the resulting function might be very wiggly and not what you are looking for. In practice, we probably have the idea that a solution with few pieces (few lines) is probably more likely than one with more pieces, all being equal. On the other hand, with too few pieces, you might get a very poor fit.

Thus, you need a parameter to balance the number of pieces against the amount of error in your fit, and then you can try to find an optimal solution. So, the first step will be to define a loss function that quantifies how good/bad each candidate solution is. Once you have that, there are various algorithms for finding the best fit. One approach is to use dynamic programming. See https://en.wikipedia.org/wiki/Segmented\_regression, https://dsp.stackexchange.com/q/1227/5874, https://stackoverflow.com/q/22028529/781723, and probably many other sources.

My guess is that if there is any noise/error in your data, it will be very small, so any reasonable procedure will work well.
> 2 votes

---
Tags: algorithms, graphics
---


title: Bucket sort with gaussian distribution

text:
# Question
Title: Bucket sort with gaussian distribution
Bucket sort algorithm lets you sort an array of $n$ elements in expected $O(n)$ time, supposing the elements are equally distributed in the $\lbrack 0,1 )$ interval.

Is there a way to modify the bucket sort in order to sort in expected $O(n)$ time an array of $n$ elements distributed in $\lbrack 0,1)$ according to the Gaussian distribution?

# Answer
> 3 votes
The algorithm works by choosing the number of buckets and the boundaries of the buckets such that in expectation the number of elements that land in a bucket is constant. The analysis is particularly simple for a uniform distribution, because uniformly sized buckets work.

For more complicated distributions you have to choose your bucket size more cleverly, but there is nothing stopping you from looking hard at the probability density function and creating more buckets in regions where you'd expect many elements to occur.

# Answer
> 4 votes
Mathematically this does exactly the same thing as @adrianN's answer, but it might be useful: you can transform random observations from the Gaussian distribution (or any other known distribution) to values uniformly distributed between 0 and 1, with a function which preserves order and which is invertible.

In the case of the Gaussian this is the function known as the error function, Z-score, etc. In general, it's the cumulative distribution function of a distribution.

So you can, for each element $x\_i$, take the number $f(x\_i)$. Sort these values. Then sort the $x\_i$ by putting them in the same order (or apply $f^{-1}$ to get back the sorted original values).

---
Tags: sorting
---


# Question
Title: What's the possibility of random guessing a youtube's video ID
Let's say i make a program that produces an eleven character long ID like youtube does and tries to find a valid video in youtube. What's the actual possibility that it's going to produce a valid ID corresponding to a real video and also an unlisted one??

# Answer
> Each YouTube id consists of 11 characters denoted by $v = \[v\_1, ··· , v\_{11}\]$. The first $10$ characters of a valid id contain any of the characters in $S = \\{0 − 9,\\\_, −, A − Z, a − z\\}$, i.e., $v\_i ∈ S (i = 1, ··· , 10)$. The last (11-th) character $v\_{11}$ only comes from $T = \\{0, 4, 8, A, E, I,M, Q, U, Y, c, g, k, o, s, w\\}$, namely, $v\_{11} \in T 1$. The size of video id space is, therefore, $64^{10}\cdot16$.
>
> We also observe that YouTube video ids are not generated in any sequence. Instead, YouTube picks an unused random id from this pool for each new video that is uploaded.
>
> **Source: http://conferences.sigcomm.org/imc/2011/docs/p371.pdf**

For instance, they show that YouTube video is randomly generated from the id space and that the entire YouTube id space can be represented as $S = S^{10} × T$, where:

* $S = \\{0−9,\\\_, −, A−Z, a−z\\}$
* $T = \\{0, 4, 8, A, E, I,M,Q, U, Y, c, g, k, o, s, w\\}$.

Their estimation of the total number of youtube videos is $502\cdot10^6$.

Given these 2 information (video id space and estimation of the total number of videos) you can deduce the probability that, given an id of $11$ characters in $S^{10} × T$, it corresponds to the id of a valid video.
> 4 votes

---
Tags: random-number-generator
---


# Question
Title: Expressing the language of squares as a concatenation of two languages
Can the language $L = \\{ vv : v \in \Sigma^\* \\}$ be expressed as the concatenation of two nontrivial languages? (A language is nontrivial if it differs from $\\{\epsilon\\}$.)

# Answer
> 2 votes
The answer depends on $|\Sigma|$. If $\Sigma$ contains a single letter then $L = (\Sigma\Sigma)^\*(\Sigma\Sigma)^\*$ can be written as a concatenation of two nontrivial languages.

Conversely, suppose that $|\Sigma| \> 1$, say $a,b \in \Sigma$. Since $\epsilon \in L$, necessarily $\epsilon \in L\_1,L\_2$. This implies that all words in $L\_1,L\_2$ are squares, and in particular $a \notin L\_1,L\_2$. Since $aa \in L$, we must have $aa \in L\_1$ or $aa \in L\_2$. Without loss of generality, assume that $aa \in L\_1$. We similarly get that $bb \in L\_1$ or $bb \in L\_2$. Since $aabb \notin L$, we must have $bb \in L\_1$. Since $L\_2 \neq \\{\epsilon\\}$, it must contain some non-empty word $w$. Hence both $aaw$ and $bbw$ are squares. However, this is impossible (why?), and we reach a contradiction.

---
Tags: formal-languages, word-combinatorics
---


# Question
Title: Definition of Turing Machine as a language acceptor
The following is an excerpt from the book *"An Introduction to Formal Languages and Automata"* by Peter Linz.

My question is, why is $\Sigma^+$ used and not $\Sigma^\ast$?

# Answer
Immediately after the definition, the text (fifth edition) continues

> This definition indicates that the input $w$ is written on the tape with blanks on either side. The reason for excluding blanks from the input now becomes clear: It assures us that all the input is restricted to a well-defined region of the tape, bracketed by blanks on the right and left. Without this convention, the machine could not limit the region in which it must look for the input; no matter how many blanks it saw, it could never be sure that there was not some nonblank input somewhere else on the tape.

This differs from the approach some other authors take, using a tape that's bounded on the left and unbounded in the other direction, and stipulating that the input string begins at the leftmost cell and continues to the first blank. I don't find Linz's definition to be better, if for no other reason than it eliminates any language containing the empty string from being the language of a TM.
> 6 votes

# Answer
I cannot tell you whether this is a mistake, but I can tell you what you should do in such cases.

1. Double check that the author is using the same notation that you are using. In this case, find in the textbook the definition of $\Sigma^{+}$.
2. Assuming there is no confusion about the notation, read surrounding text to see if there is a comment as to why he is excluding the empty word.
3. Assuming there is no confusion about the notation and no comment, look through the text to see if the author is following his own definition, or is violating it. Does he ever consider a language that contains the empty word? When he defined what a language is, is the empty word allowed?
4. Check other sources to see whether other authors allow the empty word to be part of a language. (I can tell you that they mostly do.)
5. Assuming that the author allows the empty word when he defined what a language is, and does indeed consider such languages, then you may safely conclude that you are looking at a typo and it should have been $\Sigma^{\*}$.
6. **Optional:** respectfully write an email to the author and ask him, but only after you have made the effort to resolve the issue yourself.
> 3 votes

# Answer
This is a question for the author, Peter Linz. Some authors include the empty word as a possible member of the language of a Turing machine. It is possible that the machine will always get "stuck" if it starts at the configuration $q\_0$, but it is hard to tell without knowing the exact definitions in the textbook.
> 1 votes

---
Tags: formal-languages, turing-machines
---


title: Possible combinations of soccer results

text:
# Question
Title: Possible combinations of soccer results
I'm trying to calculate the best and worst position for each team in the ranking based on the weekly matches.

Suppose we have 4 teams with these position:

Pos.| Name | Pts.

1 | Team A | 12

2 | Team B | 10

3 | Team C | 8

4 | Team D | 6

And during the week there are 2 matches **A vs C** and **B vs D**

If you don't know, in soccer you can win, lose or draw. A win are 3 points, draw 1 points each, lose 0 points.

In this scenario we have 9 possible combinatiosn \[3^(number of matches)\].

What I want to do is calculate the best and worst position each team can get based on all combination.

Of course is fairly simple to do with 4 teams (2 matches), but in real case scenario we would have about 10 matches (59000 combinations).

I guess the best way to approach the problem is to use recursion but I can't get to a real starting point.

Any help?

# Answer
Here's an alternative to recursion:

You have 3 different outcomes. You can assign each outcome to a digit in $\[0, 1, 2\]$. E.g. 0 means loosing, 1 means draw, 2 means win.

Then you can represent one combination as a series of digits, e.g. $\[1, 1, 2, 0, ...\]$ (first two matches ended in a draw, the third one was won, ...). And you can interprete this series as the digits of a number in base 3.

So obviously all combinations can be described using a number between $0$ and $3^{\\#matches}-1$ and you can very easily iterate over them:

```
for combination in 0 .. 3^(#matches)-1:
    results = combination in base 3 (exactly #matches digits)
    process results

```
> 1 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: cancel out parts of a formula in CNF (conjunctive normal form)
In this image there is a given formula in DNF and CNF. When I check it on Wolfram Alpha I see that it cancel out (E or D) because of (not A or A) which is colored in red. My question is if it is allowed to cancel out (not A or D) because of (not E or E) which is colored in green instead. THX

# Answer
It's probably useful to note that the resolution rule can be used to figure out exactly which literals (things like $\neg A\vee D$) may be deduced from the others.

In this case, the resolution rule applied to the clauses $\neg A\vee \neg E$ and $E\vee D$ results in the clause $\neg A\vee D$, which shows that that clause is redundant.
> 1 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Compute square root using (bit) additions and shifts as primitives
> **Question:** Given an $n$-bit natural number $N$, how to compute $\lceil \sqrt{N} \rceil$ using only $O(n)$ (bit) additions and shifts?

The tip is to use binary search. However, I could not achieve the required complexity (I got $O(n^2)$).

---

**What does it mean by `using only $O(n)$ (bit) additions and shifts`:**

This is an exercise in an algorithm book.
In my opinion, it means that adding two, say $n$-bit, natural numbers costs $O(1)$ and shifting a, say $n$-bit, natural number also costs $O(1)$. Then we are only allowed to use such $O(1)$ operations $O(n)$ times.
It does not mention the cost of comparison. I guess we can ignore it or assume that comparing two, say $n$-bit, natural numbers costs $O(1)$ as well.

---

**My $O(n^2)$ algorithm**:

1. Determine the range of the number of bits $t$ of $\lceil \sqrt{N} \rceil$: $$2^{\frac{n-1}{2}} \le \sqrt{N} \le 2^{\frac{n}{2}} \Rightarrow 2^{\lfloor \frac{n-1}{2} \rfloor} \le \lceil \sqrt{N} \rceil \le 2^{\lceil \frac{n}{2} \rceil}$$ Therefore, $$t\_1 \triangleq \lfloor \frac{n-1}{2} \rfloor + 1 \le t \le \lceil \frac{n}{2} \rceil + 1 \triangleq t\_2.$$
2. Binary search: Find $\lceil \sqrt{N} \rceil$ between $2^{t\_1}$ and $2^{t\_2}$ using binary search. For each number $x$, to compute $x^2$ using additions and shifts as primitives and compare it with $N$.

The complexity is thus $O(n \times n) = O(n^2)$ for $O(n)$ times of binary search and computing $x^2$, each of which in turn takes $O(n)$ additions and shifts.

# Answer
An iterative algorithm seems like it should work.

Let $M=\lfloor N/4 \rfloor$. Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously).

Now we want to find $y=\lceil \sqrt{N} \rceil$. What are the possible values of $y$? I'm pretty sure the only possible values are $y=2x$ or $y=2x+1$. And, it's easy to try both of them and see which is correct. In particular, for $y=2x$, we have $y^2=4x^2$, which can be obtained from $x^2$ by two left-shifts ($O(1)$ time); for $y=2x+1$, we have $y^2=4x^2+4x+1$, which can be obtained from $x^2$ and $x$ with four left-shifts and two additions ($O(1)$ time). Now just compare those two values to $N$ to see which one is correct.

In this way, we get an iterative algorithm where we do $n/2$ iterations, and where each iteration takes $O(1)$ time. The total running time is $O(n)$, as required.

I realize this didn't use binary search. Oh well.
> 7 votes

# Answer
Are we talking integers here? Where N is n bits long?

```
A = 2<sup>(n/2)</sup>, B = A  and C = A<sup>2</sup>
Step: B = B/2
     If C > N,
         C = C - 2AB + B<sup>2</sup>    // too high - make smaller
         A = A - B
     Else
         C = C + 2AB + B<sup>2</sup>   // keep this bit
         A = A + B
Repeat until B = 0                  // =1 on last loop

```

Loop is performed n/2 times, which should give you O(n) performance

**Edit:** How does it work, & why?
This is a version of Successive Approximation, which is also used in CORDIC algorithms.
Starting with the largest possible single bit (with a square less than N) you set one bit at a time, and calculate the new square.
If the new square is still less than N, keep the bit as set.
If the new square is too big, clear the bit, undo the effect of adding it, and move on to the next bit.

**Example:** N = 441 (1 1011 1001 binary), n = 9

```
Start:  A = 2<sup>4</sup> = 16 (1 0000)  B = 16 C = 256 (100 0000)

1   B = 8 (1000) C = 256 + 2(16)(8) + (8)(8) = 576 (10 0100 0000) {high}
    A = 16 + 8 = 24
2   B = 4  (100) C = 576 - 2(16)(4) + (4)(4) = 400 (1 1001 0000) {low}
    A = 24 - 4 = 20
3   B = 2   (10) C = 400 + 2(20)(2) + (2)(2) = 484  (1 1110 0100) {high}
    A = 20 + 2 = 22
4   B = 1    (1) C = 484 - 2(20)(1) + (1)(1) = 441  (1 1011 1001) {keep this}
    A = 22 - 1 = 21
5   B = 1/2 or 0 in integer math; end

```
> 3 votes

# Answer
The main method is to fill in the bits of $\sqrt{N}$ from left to right while keeping our estimate below it, or rather the square of our estimate below $N$. Each bit $b$ is a power of 2, so squaring or multiplying another number by $b$ is always a bit shift.

If the current estimate is $a$, $b=2^i$, and we know $a^2$ already, we get $(a+b)^2 = a^2 + 2ab + b^2$, and we can rewrite the second and third terms as $ a \<\< (i+1)$ and $1 \<\< (i \<\< 1)$. We then add it all up and test (I assume you can do $\<$) and set bit $i$ if the square is still below $N$.

We start the loop at $i = n/2 = n \>\> 1$ and count down to zero, keeping $a$ and $a^2$ as we go. It's a kind of binary search, but one where the bounds map to single-bit differences.
> 0 votes

# Answer
I like Alan Campbell's answer: with careful tracking of previous guesses, the new subtraction is easy each time, and the binary shift-and-add square root is about as fast as a binary shift-and-add divide.

But it may be possible to go faster, by instead of making your next guess a single binary digit, instead using an "A-b" x "A-b" algorithm, and making your next guess the average of your previous guess, and the original number divided by the previous guess. That sounds like it would take longer, not shorter. However, the division doesn't have to be exact. So if the division only runs to the square root of the number of digits remaining to find, then you might actually save time. Moreover, if for your division you use the french method, of shorthand division, then you might actually break some speed in your calculation for really big divides.

Now, if we add in calculations in parallel that yield preliminary correctable results before the answer is found... then we might be onto something.
> -3 votes

---
Tags: algorithms, arithmetic, binary-search
---


# Question
Title: What guarantees do "soft" real-time operating systems actually provide
I think I know what a "hard" real-time operating system is. It is an operating system with a scheduler that provides a contract with the application programmer. An application provides a deadline with each resource allocation request. *If* the deadline requests are *feasible*, the scheduler guarantees that each resource will be allocated to the requesting application before the deadline. The guarantee is sufficient to enable an application programmer to reason about the maximum latencies and minimum throughputs of specific requests.

All the definitions I find of "soft" real-time systems seem vacuous to me. Wikipedia says

> the usefulness of a result degrades after its deadline, thereby degrading the system's quality of service.

Uhhhh. Okay. By that criteria Windows 95 was a soft real time system and so was 3BSD and so is Linux. Wikipedia is not a great source, but the next couple of Google hits aren't much better. For example http://users.ece.cmu.edu/~koopman/des\_s99/real\_time/ says

> In a soft real-time system, a degraded operation in a rarely occurring peak load can be tolerated.

That's not a contract, that's a fancy way of saying nothing.

**What are examples of real soft real-time guarantees/contracts offered by real operating systems?**

I'm looking for answers of the form:

> In (OS-name) if programmer does (what-programmer-needs-to-do) then the operating system guarantees (what-the-system-guarantees).

# Answer
> 23 votes
You've got it right, and Wikipedia is as informative as can be — soft real-time is not a formal characterization, it's a value judgement. Another way to say “soft real-time” is “I wish it was real-time”, or perhaps more accurately “it should be real-time but that's too hard”.

If you really want to word in the form of a guarantee, it's a guarantee of best effort rather than a guarantee of specific performance.

Or, to quote the Erlang FAQ (Erlang is a programming language originally designed for use in telephony):

> What does soft realtime mean?
>
> Cynics will say "basically nothing".
>
> (…) Many telecomms systems have less strict requirements \[than hard realtime\], for instance they might require a statistical guarantee along the lines of "a database lookup takes less than 20ms in 97% of cases". Soft realtime systems, such as Erlang, let you make that sort of guarantee.

And this does provide a useful definition. Soft real-time indicates a design which is optimized towards **each individual task taking no more than a certain amount of time**, rather than towards optimizing the total time spent to perform all tasks. For example, a soft real-time system would aim to complete 99.9% of the requests in 10ms and process 100 requests per second, where a non-real-time might aim to proceed 200 requests per second but allow the occasional request to block for 50ms or more. A hard real-time would guarantee one request every 15ms no matter what.

Soft real-time is used for applications where a missed deadline means a degradation of service, but is not performance-critical. Multimedia and telephony are some typical use cases. Each audio or video frame must be rendered it time, or else it has to be skipped; but skipping a frame is not the end of the world. The designers of Erlang had similar objectives on reliability in other matters: they observed that it was better for a telephone exchange to very occasionally drop a call, but to be absolutely sure that the exchange as a whole would keep working come what may, than to ever risk catastrophic failure in trying to maintain connections at all cost.

In contrast, something like controlling a motor requires that the software never misses a deadline. This has costs: the overall performance is typically slower, and only relatively simple behaviors can be achieved. On the other side of the spectrum, a number crunching application typically cares only about overall performance — what matters is how fast the 1000x1000 matrices are multiplied, not how fast each column is calculated.

# Answer
> 4 votes
Linux with the -rt (real time) patchset provides a scheduler that provides an interesting guarantee that seems non-vacuous. (Although I'm not clear on how the guarantee can be put to real use.)

The Linux-rt `SCHED_FIFO` scheduling policy works as follows: The user assigns a priority to every process. (The priority numbers for "real time" processes are 0-99, and the traditional Unix `nice` values -20 through 19 map to priorities 100 through 139. (So "0" is the "highest" priority and "139" is the "lowest" priority.)

The guarantee is that at any time the scheduler will schedule the `N` highest priority runnable jobs on an `N` processor machine. Great pains have been taken to avoid priority inversion problems inside the kernel. When process `A` becomes runnable and it has a higher priority than some other running process `B`, `A` will immediately preempt `B`.

Note, though, that there are no strict time guarantees given. The time spent actually performing the preemption could theoretically be arbitrarily long. Also, there do seem to be some ways in which a low priority job could initiate a bunch of long latency i/o. When the i/o completes the interrupt handlers for the low priority job could interrupt a higher priority job, which is, arguably, a form of priority inversion.

So the limited guarantee provided is: if there is a single process with the highest priority, whenever it is runnable it will get all the processor resources that the OS can realistically give it. If you have a good upper limit on the amount of processor resources consumed by the highest priority process you can calculate a reasonably accurate estimate of the resources that will be available to the second-highest priority process, and so on.

An in depth article describing the Linux real-time scheduler is http://www.linuxjournal.com/magazine/real-time-linux-kernel-scheduler.

# Answer
> 4 votes
To define "soft real-time," it is easiest to compare it with "hard real-time."

Speaking casually, most people implicitly have an informal mental model that considers information or an event as being "real-time"

• if, or to the extent that, it is manifest to them with a delay (latency) that can be related to its perceived currency

• i.e., in a time frame that the information or event has acceptably satisfactory value to them.

There are numerous different ad hoc definitions of "hard real-time," but in that mental model, hard real-time is represented by the "if" term. Specifically, assuming that real-time actions (such as tasks) have completion deadlines, acceptably satisfactory value of the event that all tasks complete is limited to the special case that all tasks meet their deadlines.

Hard real-time systems make the very strong assumptions that everything about the application and system and environment is static and known a' priori—e.g., which tasks, that they are periodic, their arrival times, their periods, their deadlines, that they won’t have resource conflicts, and overall the time evolution of the system. In an aircraft flight control system or automotive braking system and many other cases those assumptions can usually be satisfied so that all the deadlines will be met.

This mental model is deliberately and very usefully general enough to encompass both hard and soft real-time--soft is accommodated by the "to the extent that" phrase. For example, suppose that the task completions event has suboptimal but acceptable value if

* no more than 10% of the tasks miss their deadlines
* or no task is more than 20% tardy
* or the average tardiness of all tasks is no more than 15%
* or the maximum tardiness among all tasks is less than 10%

These are all common examples of soft real-time cases in a great many applications.

Consider the single-task application of picking your child up after school. That probably does not have an actual deadline, instead there is some value to you and your child based on when that event takes place. Too early wastes resources (such as your time) and too late has some negative value because your child might be left alone and potentially in harm's way (or at least inconvenienced).

Unlike the static hard real-time special case, soft real-time makes only the minimum necessary application-specific assumptions about the tasks and system, and uncertainties are expected. To pick up your child, you have to drive to the school, and the time to do that is dynamic depending on weather, traffic conditions, etc. You might be tempted to over-provision your system (i.e., allow what you hope is the worst case driving time) but again this is wasting resources (your time, and occupying the family vehicle, possibly denying use by other family members).

That example may not seem to be costly in terms of wasted resources, but consider other examples. All military combat systems are soft real-time. For example, consider performing an aircraft attack on a hostile ground vehicle using a missile guided with updates to it as the target maneuvers. The maximum satisfaction for completing the course update tasks is achieved by a direct destructive strike on the target. But an attempt to over-provision resources to make certain of this outcome is usually far too expensive and may even be impossible. In this case, you may be less but sufficiently satisfied if the missile strikes close enough to the target to disable it.

Obviously combat scenarios have a great many possible dynamic uncertainties that must be accommodated by the resource management. Soft real-time systems are also very common in many civilian systems, such as industrial automation, although obviously military ones are the most dangerous and urgent ones to achieve acceptably satisfactory value in.

The keystone of real-time systems is "predictability." The hard real-time case is interested in only one special case of predictability--i.e., that the tasks will all meet their deadlines and the maximum possible value will be achieved by that event. That special case is named "deterministic."

There is a spectrum of predictability; most real-time systems (namely, soft ones) have non-deterministic predictability, for example, of the tasks' completions times and hence the values gained from those events. In general, predictability, and hence value, can be made as close to the deterministic end-point as necessary but at a price which may be physically impossible or excessively expensive (as in combat or perhaps even in picking up your child from school).

Soft real-time requires an application-specific choice of a probability model (not the common frequentist model) and hence predictability model for reasoning about event latencies and resulting values.

Referring back to the above list of events that provide acceptable value, now we can add non-deterministic cases, such as

* the probability that no task will miss its deadline by more than 5% is greater than 0.87.

In a missile defense application, given the fact that in combat the offense always has the advantage over the defense, which of these two real-time computing scenarios would you prefer:

* because the perfect destruction of all the hostile missiles is very unlikely or impossible, assign your defensive resources to maximize the probability that as many of the most threatening (e.g., based on their targets) hostile missiles will be successfully intercepted (close interception counts because it can move the hostile missile off-course);
* complain that this is not a real-time computing problem because it is dynamic instead of static, and traditional real-time concepts and techniques do not apply, so you are not interested in doing R&D for soft real-time.

Despite the various misunderstandings about soft real-time in the real-time computing community (but not in other non-computing fields), soft real-time is very general and powerful, and potentially very complex compared with hard real-time.

To directly answer the OP question:

* a hard real-time system can provide deterministic guarantees—most commonly that all tasks will meet their deadlines, interrupt or system call response time will always be less than x, etc.—IF AND ONLY IF very strong assumptions are made and are correct that everything that matters is static and known a' priori (in general, such guarantees for hard real-time systems are an open research problem except for rather simple cases)
* a soft real-time system does not make deterministic guarantees, it is intended to provide the best possible analytically specified probabilistic timeliness and predictability of timeliness that are feasible under the current dynamic circumstances, according to application-specific criteria. Obviously hard real-time is a simple special case of soft real-time. Obviously soft real-time's analytical non-deterministic assurances can be very complex to provide, but are mandatory in the most common real-time cases (including the most dangerous safety-critical ones such as combat) since most cases are dynamic not static.

I have a detailed much more precise discussion of real-time, hard real-time, soft real-time, predictability, determinism, and related topics on my web site real-time.org.

---
Tags: terminology, operating-systems, process-scheduling, real-time
---


title: Is the below language Non R.E?

text:
# Question
Title: Is the below language Non R.E?
$L\_0=\\{\langle M,w,0\rangle\mid M \text{ halts on } w\\}$

$L\_1=\\{⟨M,w,1⟩\mid M \text{ does not halts on } w\\}$

Here $\langle M,w,i \rangle$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ is a bit.

Let $L=L\_0 \cup L\_1$. Is $L$ non R.E ?

---

After seeing the question I was able to figure out that there are some strings that do not belong to $L\_0$ as well as $L\_1$.

Like, lets take the case for $L\_0$ and a string $001\dots10−01−1$, ("$-$" shown for notation purpose only) where the first component describes a TM $M$ followed by input "$w=01$" and last bit "$1$". Now suppose M halts on "$01$". Still the given input is not in $L\_0$ as the last bit is "$1$" and not "$0$" as required by $L\_0$. So, this input must be in $L\_1$. But since $M$ halts on $w$, this input is not in $L\_1$ either. So there are infinite strings like these. I am not able to prove that these infinite set of strings are not r.e.

Is there any method to solve these kind of problems? I am not able to master these kind of problems.

Please someone help.

# Answer
Assume that $L$ is r.e. and $M\_L$ recognizes $L$. Given $\langle M,w \rangle$, $M$ on $w$ either halts or not. This means that either $\langle M, w, 0 \rangle$ or $\langle M, w, 1 \rangle$ must be in $L$. Then using a universal Turing machine start to run/simulate $M\_L$ on both inputs $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$, simultaneously, say one step at a time for each input. After each step check if $M\_L$ halts on at least one input. Since $L$ is r.e. and exactly one of $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$ belongs to $L$, $M\_L$ must eventually halt on one of them. Depending on which input $M\_L$ halts, you can tell if $M$ halts on $w$. This decides the Halting problem and hence **$L$ is not r.e**.
> 4 votes

# Answer
The Turing machine $M$ doesn't halt on $w$ if and only if $\langle M,w,1 \rangle \in L$. This shows that **$L$ is not r.e.**: if it were, then since the halting problem is r.e., we would get a decision procedure for the halting problem. Similarly, **$L$ is not co-r.e**.
> 2 votes

---
Tags: computability, undecidability, halting-problem
---


title: Min-cut in DAGs with unit edge weights

text:
# Question
Title: Min-cut in DAGs with unit edge weights
I'm trying to better understand the min-cut problem for directed acyclic graphs. I understand that the minimum capacity cut has equal capacity to the max flow of a graph by the max flow-min cut theorem (https://en.wikipedia.org/wiki/Max-flow\_min-cut\_theorem). This makes some sense to me but I'm confused as to what happens in a DAG with unit edge weights. In this case, there's three claims I'm trying to make:

1. The max flow of a DAG with unit edge weights has an upper bound equal to the sum of the number of edges entering all sinks. In other words, max flow is bounded by the sum of the indegree of all sink nodes.
2. Because all edges have the same weight, there are $\binom{n}{\text{max flow}}$ possible min-cuts where $n$ is the number of edges. In essence, if the max flow for a DAG is 3, then choosing any 3 edges would give you a min-cut.
3. If you apply the Ford-Fulkerson to identify a min-cut, it will effectively always include edges connected to the source node because those will immediately have their capacity maxed out and the algorithm returns the cut closest to the source(s).

These feel unintuitive to say the least but seem to hold true for the few small examples I tried to run through. In particular, the second statement seems very wrong to me. It seems to imply that any set of edges with capacity equal to max flow constitute a min-cut. While a min-cut definitely has capacity equal to max flow, I'd guess the reverse statement that any set of cuts with a capacity equal to max flow is a min-cut isn't necessarily true (though I can't quite come up with a counter-example).

My question is, are any of the 3 claims above true?

Edit:

After thinking about it some more, I think I found a counterexample to my 2nd claim. In the DAG below, the max flow is 2 but cutting any two of the dotted edges wouldn't yield a partition.

# Answer
> 2 votes
Your first claim is true.

As for the second consider the following counterexample. Consider the following DAG with edges $(s,v\_1),(v\_1,v\_2), (v\_1,v\_3), (v\_2,t), (v\_3,t)$, where $s$ is the source and $t$ is the sink

```
                 (v2)
                 /  \
                /    \
        (s)-->(v1)   (t)
                \    /
                 \  /
                 (v3)

```

There is only one mincut while according to your claim there are $\binom{5}{1} = 5$. So your second claim is false.

For the third claim consider the following DAG with edges $(s,v\_1),(s,v\_2), (v\_2,v\_3), (v\_1,v\_3), (v\_3,t)$

```
                 (v2)
                 /  \
                /    \
              (s)   (v3)---->(t)
                \    /
                 \  /
                 (v1)

```

The Ford-Fulkerson (or any other) algorithm should find min-cut as the only edge $(v\_3,t)$ which is not connected to the source. The the third claim is false.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Can Pearson Correlation be used between structured data
I'm trying to determine correlation between two structured data sets.

Eg:

```
  D1
name: ABC
age: 3
address: xyz

  D2
name: ABC
dob: x/t/r
occupation: xyz

```

Is there a way to use Pearson correlation on structured data instead of variables?

# Answer
> 1 votes
No. Pearson's correlation is a correlation measure between two variables. You might be looking for `canonical correlation analysis`.

---
Tags: algorithms
---


title: Portfolio rebalancing algorithm

text:
# Question
Title: Portfolio rebalancing algorithm
Quite possibly this problem is already solved and has it's own name, but I was unable to find any directions.

So, I have a portfolio with some items in it:

```
| Name   | Price | Amount | Share |
|--------|-------|--------|-------|
| Item 1 | 200   | 1      | 25%   |
| Item 2 | 100   | 2      | 25%   |
| Item 3 | 50    | 4      | 25%   |
| Item 4 | 25    | 8      | 25%   |

```

After some time, prices changed

```
| Name   | Price | Amount | Share  |
|--------|-------|--------|--------|
| Item 1 | 220   | 1      | 27.36% |
| Item 2 | 130   | 2      | 32.34% |
| Item 3 | 17    | 4      | 8.46%  |
| Item 4 | 32    | 8      | 31.84% |

```

but I still want all items to have 25% share.

Assuming amount can be decimal, how do I find the optimal way of rebalancing this portfolio back to 25% shares? How to determine how many of each item to sell so we won't have to buy it back again (sell everything and spend 25% on each item is not an option)?

What if I have extra $100 to spend while rebalancing?

Upd: what I mean by "optimal" is to keep the amount of transactions as less as possible, assuming each transaction costs something.

# Answer
> 9 votes
Your problem specification is incomplete. What do you mean by *optimal*? Do you want to, say, minimize transactions costs? Do you want to make sure you do not cross the spread?

The original portfolio was worth \\$800. The new portfolio is worth \\$804. Assuming your actions do not change the market price, and assuming no transactions costs, that is a given.

You had \\$200 allocated to each security. Now, you want \\$201 allocated to each security:

```
| Name   | Price | Amount | Notional |
|--------|-------|--------|----------|
| Item 1 | 220   | 1      |  $220    |
| Item 2 | 130   | 2      |  $260    |
| Item 3 | 17    | 4      |   $68    |
| Item 4 | 32    | 8      |  $256    |
```

For every security whose notional is above the desired amount, sell that many units:

* Item 1: Sell 19/220 = 0.0863636363636364 units
* Item 2: Sell 59/130 = 0.453846153846154 units
* Item 4: Sell 55/32 = 1.71875 units

With the money you made from those sales, i.e. \\$19 + \\$59 + \\$55 = \\$133, buy 7.82352941176471 units of Item 3.

Now, you will have \\$201 worth of each security, exactly 25% of the new portfolio size of of \\$804.

The only time the extra \\$100 would come in to play is if you are trying to minimize your transaction costs and/or if you are worried about not being able to trade at the spot etc.

With the extra \\$100, you want to allocate \\$226 to each security. So, buy 6/220 units of Item 1, buy 158/17 units of Item 3, and sell 34/130 units of Item 2 and 30/32 units of Item 4.

However, as far as I can see, you have not specified an optimization problem.

Let $c\_i$ denote current units of security $i$ in your portfolio. Let's say you pay a percentage commission of $k$ per transaction. The amount you buy of security $i$ is denoted $x\_i$ (negative $x\_i$ mean selling). Your objective function is to minimize $\sum\_i k p\_i |x\_i|$.

Since $k$ is a constant, this is equivalent to minimizing $\sum\_i p\_i|x\_i|$ where $|x\_i|$ is the absolute value of $x\_i$.

This objective is subject to the portfolio allocation constraints:

1. $p\_1(c\_1 + x\_1) = p\_2(c\_2 + x\_2)$
2. $p\_2(c\_2 + x\_2) = p\_3(c\_3 + x\_3)$
3. $p\_3(c\_3 + x\_3) = p\_4(c\_4 + x\_4)$.

Further, the new value of your portfolio, $\sum\_ip\_i(c\_i + x\_i)$, plus the amount you spend, $k\sum\_ip\_i|x\_i|$, must be affordable, i.e, must be less than or equal to $B + \sum\_ip\_ic\_i$ which is the current value of your portfolio and the additional balance you have available.

This, of course, ignores borrowing money to finance the rebalancing which *might* be worthwhile depending on borrowing costs.

I am assuming there is going to be no short selling in a portfolio rebalancing, so $x\_i\>-c\_i$ must also hold.

You might be able to simplify the problem, and possibly save some money, by first spending $B$ on underbought items.

You might be able to drop the absolute values by first deciding which stocks are overbought.

I did not prove the last two statements.

When I get a chance, I will post the solution to the applicable linear program.

# Answer
> 2 votes
Assuming you are not allowed to buy anything, after selling each of your items will be worth at most the current value of the worst item (of smallest share). It is thus best to keep the worst item as it is, and sell amounts of each other item so that its total worth is the same as the total worth of the worst item. In your example, you would like to sell an amount of each item so that the total worth is $17 \times 4 = 68$.

Suppose now that you are allowed to use $B$ dollars for extra buys (possibly $B=0$, which is *not* the same as the preceding case). Let's suppose that you sell $x\_i$ units worth of item $i$ (the amount possibly negative, in which case you're buying), of which you currently have $c\_i$ units, and which has price $p\_i$. Then you have the following constraints:

* You cannot have a negative quantity: $x\_i \leq c\_i$.
* The total worth of each item is the same: $(c\_i - x\_i)p\_i = (c\_j - x\_j)p\_j$ for all $i,j$.
* The total expenditure is at most the budget: $-\sum\_i x\_i p\_i \leq B$.
* The goal (my guess, which turned out to be wrong) is to maximize the total worth of the remaining portfolio, which is $\sum\_i (c\_i - x\_i) p\_i$.

(As Sinan Ünür notes in the comments, my objective function is meaningless, since it amounts to the equation $-\sum\_i x\_ip\_i = B$.)

This is a linear program, which you can solve using any of the well-known algorithms. It is also possible that you can find the solution explicitly by going over all basic feasible solutions (the case $B=0$ sounds especially promising), but I'll leave that to you.

# Answer
> 0 votes
I think the optimization problem is to minimize the portfolio variance from the target allocation. I'm going to assume we are trading equities or etfs in which case the trade quantity can only be integers. (Mutual funds can have fractional shares but we can get into that later).

Min Sumofall Ending allocation% - target allocation %

Each security would be traded 0 or 1 time. The extra 100$ should actually be a 5th security called cash with a target allocation of 0%.

From the example, the transaction cost would be the price\*quantity\*1%. Thats not how it works in the real world though so let's throw that out. The transaction cost is going to be a flat amount per trade, lets say 5$ because that is fairly common. That 5\\$ will be the same regardless of the price.

So if you ran all the combinations of trades you can make there is going to come a point where that 5$ per trade is going to reduce the total variance by less than making a trade will. For his example, you probably wouldn't make very many trades. Especially for security 1 or 2, because the prices are really high and a single trade would greatly increase the total portfolio variance.

I'm getting tired so I'll check back in later.. but the answer to the algorithm is to not trade security 1 or 2, sell security 4 and 5(cash), and buy security 3.

Doh... I think I may have it wrong, the optimization problem is really maximize the portfolio value given a limit to the total portfolio variance. Or, some sort of ratio of portfolio value to variance. If you simply minimized variance then it would make trades in the overweight securities just so that you would incur trading costs and reduce your overweight in that security.

Edit: If you want a real brain buster try to figure it out when you add in all the real world considerations and constraints.... some securities have 0 commissions, some 5, some 20$. Some incur 2% fee if sold within 60 days. Some trade in only whole quantities(equities) and some trade in fractional quantities(mutual funds). Most people have more than 1 account so that adds to the complexity. Each security can have vastly different costs based on which account you put it in because of all the tax rules.

---
Tags: algorithms, optimization
---