# Question
Title: Can one count the number of n points in m triangles in less than O(nm)?
We have n points given as $(x,y)$ coordinates and m triangles given as triples of $(x,y)$ coordinates, and want to count the number of times that one of the points is inside one of the triangles. The triangles may overlap so each point may be counted multiple times.

The naive way is to check each pair of a point and a triangle and count +1 if the point is inside the triangle. Is it possible to do it more efficiently than $O(nm)$?

# Answer
> 4 votes
# Pragmatic solution that's easy to implement

If you care more about a pragmatic solution that will likely work well enough in practice in most cases, and is easy to code, I would suggest storing each point in a quadtree. Then, for each triangle $T$, recursively search the quadtree to find all points within the triangle $T$. (This recursive search is pretty easy; at a node that represents a split of the space, check whether the triangle intersects the rectangular regions corresponding to the node's two children, and recurse on whichever node(s) it intersects.)

I don't know of any reason to think that the worst-case asymptotic running time will be better $O(nm)$ (e.g., it might perform poorly if you have many long, skinny, diagonal triangles), but it might work well in practice in many cases.

# Sweepline algorithm

Alternatively, you could use a sweepline algorithm, similar to the Bentley-Ottman algorithm for detecting intersections among line segments. Unfortunately, it seems it might take quadratic time in the worst case.

Each triangle is defined by three line segments, so build the Bentley-Ottman data structures from these line segments. Also, you'll have an interval tree; for each triangle, it stores the interval of $y$-values that are obtained by intersecting that triangle with the current sweepline. Each point and each vertex of any triangle triggers an event when the sweepline hits that point or vertex. When you hit a point $p$, you can quickly count the number of triangles it is contained in: check the interval tree to see how many intervals in the tree contain it.

Each operation can be done in $O(\log(n+m))$ time. Unfortunately, there could be as many as $O(n+m^2)$ events (since there can be $O(m^2)$ intersections among the line segments), so in the worst case the total running time could be as bad as $O((n+m^2)\log(n+m))$. If you care only about typical running time, this might often do a lot better than that, as the number of intersections among the triangles might often be as little as $O(m)$, which would lead to a $O((n+m)\log(n+m))$ running time; but that's not guaranteed, and there exist inputs where it is much slower.

---
Tags: algorithms, computational-geometry
---


title: Good resources for Graph labelling

text:
# Question
Title: Good resources for Graph labelling
I'm searching for good resources on different graph labelling, especially **Graceful**, **Antimagic** and **Antibandwidth Labelling**. Could anyone please help me with that? It will be very much appreciated. Thanks in advance.

# Answer
You will hardly find anything more comprehensive than the 400-page dynamic survey of Gallian \[1\] discussing almost 2300 references.

---

\[1\] Gallian, Joseph A. "A dynamic survey of graph labeling." The Electronic Journal of Combinatorics 16, no. 6 (2016): 1-219.
> 2 votes

---
Tags: graphs
---


# Question
Title: dynamic pseudo-code for simplified coin changing algorithm
As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible combinations. Instead we need only to determine if a certain subset of coins of same or varying denomination, equal exactly to, some amount M.

My recursion equation of the problem is as follows:

```
let k = 0

If ∑ (v1 + v2 + … + vn) = M
    return true

If ∑ (v1 + v2 + … + vn) < M
    return false

Else
    Increment k by 1
    make recursive call on coin subset {v1, v2, … v(n-k)}

```

The next question is to convert this into pseudo-code that represents a dynamic programming solution to this problem.

I'm a bit stuck. If you were to make a table of every possible sum {v1 + v2}, {v1 + v2 + v3}, {v1 + v2 + v3 + v4}, etc. You could eventually find a solution but wouldn't that be a much less efficient brute force approach?

I assume the solution would include some implementation of memoization or some way to store and retrieve sums already encountered, but being that the problem is not an optimization problem, I'm having a hard time envisioning a dynamic solution.

Much of the dynamic programming examples that I see suggest iteratively subtracting elements, one item at a time, which is similar to the composition of my recursion equation but I don't see a modification that would make this pseudo code dynamic in nature.

If anyone could please enlighten me, I'd be very grateful

# Answer
Given an integer $M\>0$ and $n$ coins with integer values $v\_1, v\_2,\cdots, v\_n$, where $M, n, v\_i$ are positive, how can we determine if some of the coins can add up to $M$?

This problem is a common version of subset sum problem. There are many strategies to solve the problem.

---

Here is the pseudocode by dynamic programming that is about as simple as possible.

* Let $s$ be an array of size $M+1$ with default value 0 and starting index 0. Let $s\[0\]=1$.
* For $i$ from 1 to $n$, do:
    + For $j$ from 0 to $M$, do:
        - If $s\[j\]=1$, let $s\[j+v\_i\]= 1$.
* If $s\[M\]=1$, return yes. Otherwise, return no.

Here is an example to illustrate the algorithm. Let $M=7$. Coins are $1,3,3,5$.

* $s=\[1,0,0,0,0,0,0,0\]$.
* Here are $s$ at the end of each iteration.
    + $s=\[1,1,0,0,0,0,0,0\]$
    + $s=\[1,1,0,1,1,0,0,0\]$
    + $s=\[1,1,0,1,1,0,1,1\]$
    + $s=\[1,1,0,1,1,5,1,1\]$
* return yes since $s\[7\]=1$

We can optimize the algorithm above in various ways.

* We can stop the algorithm once we have found $s\[M\]=1$.
* We can change $s$ to a double linked-list, whose elements are the realizable values in increasing order.
* We can split the given array of values to two arrays of equal size or sizes with difference 1. Run the algorithm on each of two arrays. Check if we can select one number from each resulting array $s$ such that their sum is $M$, using two-pointer technique.
* This last item means all other ways, as always.

---

**Exercise.** Adapt the algorithm so that it also tells the least number of coins used if the answer is yes.
> 1 votes

---
Tags: dynamic-programming, coin-change, pseudocode
---


title: Interpolate on a cylic x axes

text:
# Question
Title: Interpolate on a cylic x axes
Let's assume you are in 2D space and you have a set of fix points `FIX_POINTS = [(x1, y1), (x2, y2)]`. I want to interpolate the `y` value for a given `x` value using the provided points as fix points for a piecewise linear interpolation.

Caveat: The x-axis is cyclic, so it wraps around at a certain known value.

I'm searching a neat algorithm (or way to write this down) which can do this interpolation, so take an x value on the cyclic x-axes and compute the y- value using piecewise linear interpolation.

Example: Given `FIX_POINTS = [(10, 50), (90, 100)]`, and a "cyclic interval" (so the value at which the x axes wraps) of `100`, the interpolation would lead to the following results:

```
  interpolation(10) = 50 # No interpolation necessary, directly on fix points
  interpolation(90) = 100 # Same

  interpolation(50) = 75 # Normal Interpolation
  interpolation(0) = 75 # Wrap around interpolation
  interpolation(1) = 72.5 # Same
  interpolation(99) = 77.5 # Same

```

I'm not too curious in the actual programming, I'm searching for a way to write this down nicely. Maybe there is even an existing implementation for this? I'm having troubles asking google for the lack of search terms.

I implemented it myself, but it got a lot of code, so I'm in search of something simpler: https://gist.github.com/theomega/9782be548fd452e1f1469757387b35e4 . This implementation also is far from optimal on the computational side (scanning over the array).

*I'm not sure if this is the stack exchange for this. Feel free to point me in a different direction.*

# Answer
Find the fixed point $(x\_l,y\_l)$ just to the left of your $x$-value, and the fixed point $(x\_r,y\_r)$ just to the right of your $x$-value. Then use the line between those two fixed points to interpolate.

To find the fixed point to the left and the fixed point to the right, store the fixed points in sorted order (sorted by their $x$-coordinate). Then you can use binary search to find the fixed point to the left and to the right.

To deal with wrap-around, take the left-most fixed point and add a wrapped-around copy above the upper limit, and similarly add a copy of the right-most fixed point. For instance, suppose the limit is 0..100, and the left-most fixed point is $(5,20)$ and the right-most fixed point is $(98,3)$. Then you should add the two additional points $(105,20)$ and $(-2,3)$. Now apply the algorithm above.
> 1 votes

---
Tags: algorithms, mathematical-programming
---


# Question
Title: Decide if a string is in a language without simulating the automata accepting the languge
Is it possible for a Turing machine with input of a DFA that accepts a finite language and a string to decide whether the string is in the language without "fully simulating" the DFA on the string?

More formally, Is there a TM $M$ with a constant $C\_M$ that can decide $L$, where for every input it halts at most $C\_M$ steps after reading $w$'s last bit where $L$ is given by:

$L=\\{\langle D,w\rangle \mid D\text{ is a DFA that accepts a finite language and $D$ accepts $w$}\\}$?

I was thinking it is not possible, though I am not sure because maybe one can deduce from the encoding of the DFA without simulating the DFA what is the language.

I can't see how this can be done but not sure how to prove it can't be done.

# Answer
> 2 votes
You ask two questions.

For your first question, about whether a TM can do this without fully simulating the DFA:

The problem statement is not well-defined. Given a TM, you can't tell whether it "fully simulates the DFA on a string" or not. (That's undecidable.) There are all sorts of ways that a TM might effectively "simulate", but in an obfuscated way that makes it hard for you to realize that's what it is effectively doing.

Your language $L$ is certainly decidable. It has the form $L=L\_1 \cap L\_2$ where $L\_1$ and $L\_2$ are both decidable, hence $L$ is decidable too.

For the second question, about whether a TM can do this using at most a constant number of steps after reading the last bit:

Sure. That's always possible, for any decidable language. After reading all but the last bit, the TM can decide what it will do if the last bit is 0 and what it will do if the last bit is 1 (doing as much computation as necessary to handle both cases). Then, when it reads the last bit, it will immediately be able to produce the correct output, using only a constant number of steps. This doesn't really have anything to do with whether the TM is or isn't simulating the DFA, though.

---
Tags: turing-machines, computability, finite-automata
---


# Question
Title: How to statically type polymorphic lambdas using hindley milner style type inference
I am playing with a simple implicitly typed functional language and have implemented type checking using a Hindley Milner style system. In order to guide code generation, I want to tag each term with its type during type inference.

Of course my language uses lambda expressions and the implicit typing should enable nice polymorphic use of those lambdas. Unfortunately, this goal clashes with the static type tagging as each lambda can be tagged only once which specializes it for a particular set of argument and closure types. It is also not possible to statically copy lambdas on each use, as this requires dynamic knowledge.

I thought about dynamically copying and tagging lambdas at runtime but this would involve quite some work and possibly overhead. Is there a standard solution for this kind of problem?

**Update 1** The following example might help to clarify my point.

```
add := func (a, b) begin a + b end
a   := add(2, 3)
b   := add('hello', 'world')

```

The lambda `add` has polymorphic type `(T1, T1) -> T1` and during type checking `add` is first instantiated to `(Int, Int) -> Int` and then to `(Str, Str) -> Str`, everything fine so far. But, during compilation, I want to have the tree representing `add` to be annotated with conrete types. Unfortunately, `add` is a single tree and that tree is either tagged with the first or the second type instantiation.

I could create copies of the `add` tree for each application but it seems to me that this is only possible at runtime, when the actual target of a call is available. On the other hand, maybe I could somehow `let` bind copies of the lambda for each instantiation and mangle the type variant into the name? That would entail updating references and I'm not sure whether this is actually possible in general? What about lambda return values, conditionals and so forth?

**Update 2** I still feel like I did not describe my problem sufficiently. My language is really rather simple and I would like to stick with a simple typing solution. I found an article series that exactly details my problem and even explores the approaches that I envisioned: type spacialization per application and selecting specialized trees using a structured ler naming scheme.

# Answer
You should use a polymorphic lambda calculus, e.g. System F for representing typed terms. Then, when you generalize a let binding, you also insert lambdas which abstract over types, and when you check a function application, you also insert type applications as needed. This is precisely what GHC Haskell does, and is the standard solution.

Now, your concrete example does not fit into pure H-M inference, because you seem to be using an overloaded `+` operation. Unless `+` is implemented for every type or fails at runtime for some types, `(T1, T1) -> T1` is not a valid polymorphic type for `add`.

For a pure H-M example program, elaborating to System F would look something like the following, with input:

```
id := func a begin a end
a  := id 'hello'
b  := id 100

```

And output:

```
id := Func A (func (a : A) begin a end)
a  := id [String] 'hello'
b  := id [Int] 100

```

Where I use `Func A` to mean a lambda binding a type (corresponding to big lambda in System F), and `id [String]` to mean applying the polymorphic `id` to a `String` type. The point of type lambdas and applications is to have an explicit internal representation of polymorphic functions.
> 5 votes

---
Tags: type-theory, type-inference
---


# Question
Title: Automaton recognizing ambiguously accepted words of another automaton
Let $A$ be a nondeterministic automaton. Let $X(A)$ the set of words for which there at least two accepting paths.

In one of the previous exam, for which no answers are available, it is required to prove that there exist a deterministic automaton whose language is $X(A)$. Furthermore, if the original automaton has $k$ states, then the new automaton should have $3^k$ states.

I have tried multiples approaches to no avail:

* Make an automata that keeps track of which path was taken, but the size of the automata grew infinitely because of cycles...
* An automaton for each state I also kept track of which state it came from, but it was just a scaled down version of previous attempt. Which didn't work if the path started to converge early.
* Tried an automaton where I encoded each state with the set of all the states from automaton $A$. And for each state I included whether I went through that state 0, 1 or more than 2 times.

# Answer
> 3 votes
Construct an NFA which will simulate (nodeterministically) two runs of the original NFA on the input. The NFA also remembers one bit – whether the two runs have diverged so far or not. If the bit is off and the NFA chooses two different transitions, then you turn it on. The NFA accepts if both runs accept and the bit is on.

If the original NFA has $k$ states, then the new NFA will have $2k^2$ states. You can convert it to a DFA with $4^{k^2}$ states.

We can reduce the number of states in the corresponding DFA by performing the powerset construction directly. At each step, we will remember, for each step, whether (i) it is impossible to be at that state, (ii) it is possible to be at that state, but there is a unique such run, (iii) it is possible to be at the state, and there are at least two such runs. A state is accepting if there is an accepting states of type (iii), or at least two accepting states of type (ii). This construction uses only $3^k$ states, and so matches your hint.

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


# Question
Title: Does a polynomial solution to weakly-NP Complete problem mean P = NP?
Suppose someone finds a polynomial solution to weakly-NP Complete problem does that mean P = NP.

# Answer
All weakly NP-complete problems are NP-complete by definition, so yes, a polynomial time algorithm would imply P = NP.
> 3 votes

---
Tags: complexity-theory, np-complete, np, subset-sum
---


# Question
Title: Dominating set of given size $k$ in $O(2^k |V| |E|)$
Recently I've encountered an interesting case of dominating set problem: given an unweighted and undirected graph $G(V, E)$ and knowing that it contains a dominating set of size $k$, find any such dominating set in time $O(2^k\ \vert V \vert\ \vert E \vert)$.

During my research, I found only some algorithms to find fixed-size dominating set in a $d$-degenerated graphs, but no such restriction is applied in this problem.

Is there any way to solve that problem in such time?

# Answer
> 2 votes
It is well-known (for a very specific group of people) that dominating set is W\[2\]-complete (for undirected graphs).

You are asking for a *fixed-parameter tractable* algorithm for solving dominating set in general graphs. The class of algorithms admitting such running times comprises the class called FPT.

Unfortunately, most people in the aforementioned group believe that FPT is a strict subset of W\[1\] which again is a strict subset of W\[2\].

To summarize, we don't think that Dominating Set has an FPT algorithm.

Under the assumption that $\text{FPT} \neq \text{W\[2\]}$, there is no $O(f(k) \cdot \text{poly}(|V|, |E|)$ algorithm for *any function $f$ and any polynomial function $\text{poly}$*.

For the Vertex Cover problem, there is such an algorithm, that is, Vertex Cover is in FPT. Clique and Independent Set are W\[1\]-complete, whereas Chromatic Number is in XP, which means that it is above the entire W-hierarchy.

**Why guarantees of yes-instances won't help**

Let $A$ be an algorithm that in running time $f(x)$ (where $x$ is the size of the input) returns a solution of size at most $k$. Algorithm $A$ only works on "yes"-instances. Create an algorithm $A′$ that takes any input, runs $A$ for $f(x)$ steps, and if $A$ hasn't terminated, returns "no". If $A$ returns, $A′$ verifies the solution (in polynomial time) and outputs either "yes" or "no" according to $A$s output.

The algorithm $A$ is an algorithm, so it's not likely to get mad at you for trying to cheat; it has to *do something* for any input, possibly crash and go up in smoke, but there is a nice dichotomy we can use to cheat:

* If $A$ gives you any output, we can verify that the output is a correct solution in polynomial time
* If $A$ fails to give you any (correct) output in its specified running time, the input has to be a no instance.

Hence, if an algorithm works on guaranteed yes-instances, we can create an algorithm that works on any instance.

---
Tags: graphs, np
---


# Question
Title: Number of MUX required for Cache Mapping
I have read that the number of multiplexers required is equal to the number of bits in the TAG field. Is it true? If yes then why?

I know that the size of each multiplexer has to be ***S to 1***, where S is the number of sets in a k-way associative cache (For Direct Mapped, no. of sets = no. of lines). That's because we have to select one of the sets using the set offset (or index) bits.

I'm not being able to reason with the number of multiplexers required though.

# Answer
> 0 votes
A multiplexer can output only a single bit on output line. So, to output one complete tag to the comparator ,

Number of multiplexers required = Number of bits in the tag. (say T)

If there are k lines in one set, then number of tags to output = K,

thus ,

number of multiplexers required = Number of lines in one set (K) x Number of bits in the tag(T).

TOTAL MUX REQUIRED = K\*T

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: QuickSort of linked lists optimised for duplicates
This is an past year question for a school exam that I do not suggested solutions for.

**Problem Description**

Quick Sort is not stable because of need to swap values in array when partition is done. If we store the values to be sorted in a linked list, we can make quick sort stable. Also, we can easily improve the performance of Quick Sort by grouping all the values that are equal to the pivot to the middle so they do not need to be considered during the subsequent partitions. Consider the following code.

```
function ListNode quickSort(ListNode head)
    partition(params1)
    ListNode front = quickSort(params2)
    ListNode middle = params3
    ListNode back = quickSort(params4)
    return combine(front,middle,back)

```

**Task**

Identify what should be `params1,params2,params3,params4`

Use pseudocode to describe the partition method. Make sure that special cases such as when there is a null in parameter is taken care of. Also, the new version of QuickSort is in-place.

I think that quickSort should return the `head` node of the list, but then middle seems strangely placed in the code as I would think of putting it after after partition. Also, I do not know the pseudocode standards for linked list and whether it is similar to the case of the normal one done with arrays. Can anyone help me with this?

# Answer
> 1 votes
The point is that with linked lists you can reorganize them in-place. So, your partition method should return three separate lists: lower, middle and higher. Each list contains nodes from source list, only pointers are manipulated.

---
Tags: algorithms, quicksort, pseudocode
---


# Question
Title: Can a schedule be conflict serializable but not serializable?
A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then, My question is: Can a schedule be conflict serializable but not serializable? Please explain why.

# Answer
NO. As you can see in the following picture, conflict serializable schedules are a subset of serializable schedules, therefore all of them are serializable.
> 0 votes

---
Tags: concurrency, scheduling, database-theory, process-scheduling
---


# Question
Title: Is this algorithm bubble sort or selection sort?
```
#include <iostream>

int main() {
    int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 10; i++) {
        for (int j = 0;  j < 9; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
    // now the array is sorted!

    return 0;
}

```

I've just studied bubble sort and tried to implement that in c++ as the code above.

I've taught my friend the algorithm, but he implemented it as the following code, which worked and sorted the array, but I don't know what the name of algorithm he used. Here is a sample of what he used:

```
#include <iostream>

int main() {
    int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 10; i++) {
        for (int j = i + 1;  j < 10; j++) {
            if (arr[i] > arr[j]) {
                std::swap(arr[i], arr[j]);
            }
        }
    }
    // now the array is sorted!
    return 0;
}

```

Is this selection sort?

# Answer
Yes, the code written by your friend implements the selection sort. It is not exactly how the selection sort is usually implemented, though.

### What is done in your friend's code?

1. At the first iteration where `i=0`, it finds the smallest element by comparing the element at index 0 with all other element, swapping if necessary so that the minimum element so far will stay at index 0.

At the end of this iteration, the smallest element is at index 0.
2. At the next iteration where `i=1`, it finds the next smallest element by comparing the element at index 1 with all other element except the smallest element, swapping if necessary so that the next smallest so far stays at index 0.

At the end of this iteration, the smallest and second smallest element is at index 0 and 1, respectively.
3. At the next iteration where `i=2`, it finds the next smallest elements by comparing the element at index 2 with all other element except the smallest element, swapping if necessary so that the next smallest so far stays at index 2.

At the end of this iteration, the first 3 smallest elements are sorted at index 0, 1 and 2.
4. And so on.
5. Finally, at the beginning of last iteration where `i=9`, the first 9 smallest elements are sorted at first 9 indices. The 10th smallest elements, which is also the largest element in this 10-element array, must have been at the last index.

So the sorting is done.

---

### Your friend implements the selection sort.

Let us check what is selection sort. According to the Wikipedia article, here is the idea of selection sort.

> The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

We can verify that your friend's code implements exactly that idea above. In fact, if you replace `int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};` with `int arr[5]= {11, 25, 12, 22, 64};`, updating the bounds accordingly, your friend's code will produce exactly the same sublists at end of each outer loop as shown in the example in Wikipedia.

Your friends' code is different from how the selection sort is usually implemented. The common implementation uses an index `iMin` to track the minimal element while your friend uses the element at the expected location to track the minimal element.

Your friend's code runs slower than the usual implementation because it uses much more swaps in average although both implementation uses exactly the same number of comparisons, $n(n-1)/2$. On the other hand, it uses no more swaps than a bubble sort.

Your friend's code is simpler to write and ends up even shorter than the common implementation, supporting the claim "selection sort is noted for its simplicity".

You may want to enjoy visualization of various sorting algorithms at Topal.com.

---

### Exercise

1. If `arr[j] > arr[j + 1]` in your code is changed to `arr[j] < arr[j + 1]`, what is the result? Does it implement bubble sort still?
2. If `arr[i] > arr[j]` in your friend's code is changed to `arr[i] < arr[j]`, what is the result? Does it implement selection sort still?
3. Show that your friend's code uses no more swaps than a bubble sort. Give an example when your friend's code uses less swap than a bubble sort.
> 3 votes

# Answer
The first snippet is an inefficient version of bubble sort. Inefficient because more than half of the comparisons it performs are useless (after the first pass, the largest element is put in the last position, and the next loop can stop earlier; and so on). Efficient versions stop at the last swap of the previous pass.

The second snippet may be considered a selection sort because it bring the smallest element in the first position repeatedly, but does it in an inefficient way as it can move many elements on every pass (at worse O(N²) moves in total). True selection sort looks for the smallest element without moving any (at worse O(N) moves).
> 0 votes

---
Tags: algorithms, terminology, sorting
---


# Question
Title: Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2
Given (n) , what is the Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2. Is there any way I can re-write this code just without using nested loop?

```
int counter=0;
    int x=0;

    for (int i =(int) n-1; i>=0 ; i--){

        if(i == x)
            break;

        for (int j = 1; j< (int)n ; j++){

            if (Math.pow(i,2)+Math.pow(j,2) == Math.pow(n,2)){
                counter++;
                x = j;
            }
        }
    }
System.out.print(counter);

```

# Answer
Your approach is to try every possible $x$ and $y$ and see if $x^2+y^2=n^2$. However, $n$ is fixed and, for any $x$, either $n^2-x^2$ is a perfect square or it isn't. You can calculate what $y$ is, instead of looping and trying every possible value.

Actual code is off-topic but it's confusing that you're trying to solve a problem about $x$ and $y$, but you've represented those quantities in variables called `i` and `j`. And even worse that you have a variable called `x` that represents something else entirely. (In fact, I'm not sure it's even correct. You seem to be using `x` to avoid reporting, e.g., $x=3$, $y=4$ and $x=4$, $y=3$ as separate solutions for $n=5$. But they *are* separate solutions and the question, at least as you've summarized it, doesn't say that they should be counted as the same.)
> 3 votes

---
Tags: java
---


title: IEEE754 representation in hexadecimal?

text:
# Question
Title: IEEE754 representation in hexadecimal?
In class, I've heard hexadecimal representation for IEEE754 mentioned and described in 32bit length as a format that consists of one bit for sign, normalized 6-digit fraction (with an implied leading zero) and biased (+64) 7bit exponent, leading me to believe it's not just a made up spec.

However, googling the actual IEEE754-2008 standard, I've found only 5 basic formats for base 2 and base 10 in it (binary32, binary64, binary128, decimal64, decimal128) and some more interchange formats for these two bases, but no mention of representation in base 16. Could that specification be some rejected proposal which is difficult to find now or am I missing something here?

# Answer
> 1 votes
There is the old IBM format :

http://en.wikipedia.org/wiki/IBM\_hexadecimal\_floating\_point

which fits that description, but it's not an IEEE P754 format.

# Answer
> 1 votes
Hexadecimal notation is just a shortcut writing one hexadecimal digit instead of four bits. For example 1A is exactly the same as 00011010. So eight hexadecimal digits give you the same as the binary32 format.

What you describe may be that someone takes one sign bit, 2 hex digits for the 8 bit exponenent, and 6 hex digits for the 23 bit mantissa. That would be possible but a bit misleading.

# Answer
> 0 votes
The description you were given us wrong. It’s one sign but, an 8 bit exponent biased by 127 (so for the number 1.0 the biased exponent is 127), and a 23 bit mantissa with an implicit leading one bit.

There’s also a 64 bit format (11 bit exponent, 52 bit mantissa) and an 80 bit format (15 bit exponent, 64 bit mantissa with explicit leading bit).

---
Tags: floating-point, number-formats
---


# Question
Title: Must a function in lambda-calculus which inputs a boolean function be defined in a certian way?
This question is my best attempt to get at a more general question about what one can get from terms in the lambda calculus.

Using the church encoding, we define booleans by $\texttt{true} = \lambda x,y.x$ and $\texttt{false} = \lambda x,y.y$

Define the set of terms $Bool = \\{\texttt{true}, \texttt{false}\\}$, and let $Bool \to Bool = \\{g \\; | \\; \text{if } b \in Bool \text{ then } g \\; b \in Bool\\}$

Let $f$ be a term with the property that if $g \in Bool \to Bool$ then $f \\; g$ normalizes to a boolean.

Intuitively, I believe $f$ can be either a constant function or it can use $g$. Precisely: **Is it true that any such f satisfies one of the following properties:**

* There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \\; g = b $
* There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \\; g = g \\; b $
* There exists some term $b \in Bool$ so that for any $g \in Bool \to Bool$, $f \\; g = not (g \\; b) $
* EDIT: as Derik points out, the above three cases only capture 6 of the 16 set-theoretic functions of type (Bool -\> Bool) -\> Bool. The point was can $f$ be defined in a way other than those set theoretic ones.

(where $a = b$ means that $a$ normalizes to $b$)

# Answer
If we assume that $g$ normalizes when applied to any Boolean input, then we can apply it to `true` and `false`, and then we can can compute any Boolean function of those two values. That is, we can readily produce all $16$ possible set theoretic functions, $2^{2^2}$. Your schemas only cover $6$ of those.

But the story goes further, your definition of $f\in(Bool\to Bool)\to Bool$ does *not* require that $f$ only apply its argument to Booleans. Similarly, $g\in Bool\to Bool$ does not restrict $g$'s behavior for all other inputs. At this point, there are all kinds of additional possibilities (even when restricting to $Bool\to Bool$ inputs) where $f$ applies its argument to other things and performs some other calculation to ultimately produce a Boolean. So there are many other potential terms. If you want tighter guarantees, you may want to consider looking at typed lambda calculi.

(As a tangent, but an interesting tangent, is the class of sequentially realizable functionals. These include functions which are mathematical functions but which aren't implementable in a "pure" way, i.e. they require things like exceptions or mutable state to be implemented.)
> 5 votes

---
Tags: proof-techniques, lambda-calculus
---


title: Nested word automatons

text:
# Question
Title: Nested word automatons
At the moment I'm trying to understand nested word automatons but I don't get the point quiet right. Let's say I have the alphabet $\Sigma = \\{c,r\\}$ and I want ot recoginize the languge $\mathcal{L} = \\{ \langle c^n r\rangle^n \\}$. On slide 14 of this presentation I found the following automaton which should recognize $\mathcal{L}$.

After reading the last $\langle c$ the automaton is is state $(q\_1,p\_1)$ and, since $\delta\_r: Q \times P \times \Sigma \rightarrow Q$, after reading the first $r\rangle$ it switches to $(q\_2)$. So how does the automaton keep track of reading the same ammount of $\langle c$ and $r\rangle$? Do we have to keep the hierarchical state in mind for each call symbol? If so wouldn't we need a stack again for that?

# Answer
> 2 votes
Please note that the input to a nested word automaton is nested words instead of the usual words.

**A nested word** $n$ over $\Sigma$ is a pair $(a\_1\cdots a\_l; \leadsto)$, where $a\_i\in\Sigma$ and $\leadsto$ is a matching relation of length $l$. Note that if there is no pending call nor pending returns (in which case $\leadsto$ is said to be **well-matched**), then the number of the calls and the number of returns are equal by the definition of a matching relation. This is the case when you use $\\{ \langle c, r\rangle\\}$ as the alphabet of $L$ to represent the nested words.

What the nested word automaton in the question does mostly is, indeed, to check that all $\langle c$'s happens before $r\rangle$'s.

You are encouraged to read the seminal paper *Adding Nesting Structure to Words* by Rajeev Alur and P. Madhusudan. You might be delighted to find it is pretty easy to read, especially the relevant section 3.1.

---
Tags: finite-automata
---


# Question
Title: Find a $\log_2(|V|)$ long cycle where each node is of different color
Here's a question from an algorithms exam by Prof. Noga Alon that I just can't wrap my head around.

Let $G=(V,E)$ be a directed graph where $|V|=n$. Let $k=\lfloor \log\_2(n)\rfloor$. Each node in the graph is in one of $k$ colors. Give an efficient algorithm to determine if there exists a simple cycle of length $k$ in the graph where each node has a different color.

I really don't know where to start with this. I thought about breaking the graph into subsets of nodes of each color and having multiple copies of each subsets in order to force a color change with every edge we traverse but I couldn't get this to work. Any hint is appreciated!

# Answer
> 7 votes
The idea is to use dynamic programming. For every pair of vertices $x,y$ and subset $S$ of colors, you determine whether there is a path from $x$ to $y$ of length $|S|$ (measured in vertices) which uses all colors in $S$, each of them exactly once.

---

What is this good for? Usually our graphs are not colored. The idea of *color coding* is that finding cycles (and other structures) is much easier if vertices or edges are colored: instead of having to remember all vertices visited in the cycle being constructed, it suffices to remember the colors encountered. Therefore we need to *introduce* the colors into our graph. How do we do that? In the simplest possible way: randomly.

Suppose that we want to find a directed cycle of length $k = \ln n$ in a directed graph. We color the vertices of the graph randomly with $k$ colors. If there is a directed cycle of length $k$, then the probability that all of its vertices are colored with different colors is $k!/k^k \approx e^{-k} = 1/n$. Therefore if we try (say) $n\log n$ different random colorings, then it is highly likely that one of these colorings would color the vertices of the cycle with different colors. When that happens, the dynamic programming algorithm outlined above will find the cycle. Conversely, if there is no directed cycle of length $k$, then no coloring would confuse us.

All in all, we obtain a randomized algorithm, running in polynomial time, that finds a cycle of length $k$, if one exists, with high probability.

# Answer
> 1 votes
The hint is in the question:

> Let $k=\lfloor \log\_2(n)\rfloor$

Why? Because then there are at most $n$ subsets of the colours...

---
Tags: algorithms, graphs, colorings
---


# Question
Title: Are there lambda-calculus functions which always output booleans, but are not constant functions?
In labmda calculus, true = $\lambda x,y.x$ and false = $\lambda x,y.y$.

Is there a term $f$ such that for any other term $x$, $f x$ normalizes to true or false BUT $f$ does not have the same output for all inputs?

# Answer
That is not possible. By the "genericity lemma" (Barendregt book, lemma 14.3.24), if $C\[M\] = N$ with $M$ unsolvable, and $N$ normal form, then $C\[L\] = N$ for any term $L$.

So, if $x$ is an *unsolvable* term (like $\Omega=(\lambda w.ww)(\lambda w.ww)$) and $f x = {\sf true}$ (normal form), then $f y = {\sf true}$ for any term $y$. The same holds for $\sf false$ or any other normal form.

The intuition here is that an unsolvable subterm will make the whole term diverge as soon as it is needed for the computation, much like `while (true) {}` hangs the program in imperative programming as soon as the loop is executed.
> 10 votes

# Answer
Yes, there is. Take, for example, the combinator

$iszero := \lambda xyz. z((\lambda xy.x)y)x$

which has the following behavior:

$iszero\ P\ Q\ 0 =\_\beta P\\ iszero\ P\ Q\ k+1 =\_\beta Q$

i.e. the operator expresses "If $n=0$ then $P$ else $Q$".

This definition presupposes an encoding of natural numbers as **Church numerals**: For any n, $n = \lambda xy.x^ny$, where $M^0N$ = $N$ and $M^{n+1}N = M(M^nN)$, i.e. $n$-fold application of $M$: $M(M(M(...N)))$.
So $0 = \lambda xy.y; 1 = \lambda xy.xy; 2 = \lambda xy.x(xy); 3 = \lambda xy.x(x(xy)); ...$.

Now construct the following $\lambda$ term:

$iszero (true) (false)\\ = (\lambda xyz.(z((\lambda xy.x)y))x)(true)(false)\\ =\_\beta (\lambda z. (z((\lambda xy.x)false))true)\\ =\_\beta (\lambda z. (z(\lambda y.false))true)$

This operator will always return a boolean value ($true$ or $false$), but different values depending on the input.

Input $k = 0$:
$ (\lambda z. (z(\lambda y.false))true)(0)\\ =\_\beta (0(\lambda y.false))true\\ = ((\lambda xy.y)(\lambda y.false))true\\ =\_\beta (\lambda y.y)(true)\\ =\_\beta true$

Input $k \> 0$, e.g. $k=1$:
$ (\lambda z. (z(\lambda y.false))true)(1)\\ =\_\beta (1(\lambda y.false))true\\ = ((\lambda xy.xy)(\lambda y.false))true\\ =\_\beta (\lambda y.(\lambda y.false)y)true\\ =\_\beta (\lambda y.false)true\\ =\_\beta false$

So the term $iszero (true) (false)$ will always return one out of $true$ or $false$, but the former output only for inputs $=0$ and the latter for inputs $k\>0$.
> 0 votes

---
Tags: lambda-calculus
---


# Question
Title: Is ambiguity in Programming Language always bad?
Suppose we have a token and our language allows the compiler to build two different derivation trees. However, it can happen that there exists two semantic ways to interpret our token. So ambiguity is not a problem in this case. Am I correct?

# Answer
> 3 votes
There are computer languages with ambiguous grammars. They decide how to compile ambiguous code by applying rules outside the grammar (there’s no law saying that a language has to be defined by a grammar only). The problem is if your *language* is ambiguous - if you have code and cannot tell how it should be compiled, that’s quite useless.

---
Tags: programming-languages
---


title: Generalization of Subgraph Isomorphism

text:
# Question
Title: Generalization of Subgraph Isomorphism
I am wondering how to prove that Subgraph Isomorphism is NP Complete. Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link that demonstrates how Subgraph Isomorphism reduces to CLIQUE, but I can't figure out how to reverse it. Subgraph isomorphism reduction from the Clique problem

Here is a formal example of the problem from DASGUPTA 8.10: Given as input two undirected graphs G and H, determine whether G is a subgraph of H (that is, whether by deleting certain vertices and edges of H we obtain a graph that is, up to renaming of vertices, identical to G), and if so, return the corresponding mapping of V (G) into V (H).

# Answer
> 1 votes
A subgraph is isomorphic to a clique if, and only if, it *is* a clique.

---
Tags: np-complete, clique
---


# Question
Title: How to best maintain a sorted list from a stream of integers?
If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the right. This would amount to $O(N + \log N)$ time. Is there a better data structure that can help me achieve the same in better time? I know we can use a Balanced Binary Search Tree with $O(\log N)$ insertions but I would like to have efficient access on the list.

# Answer
> 6 votes
A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access. Augment the data structure to store, in each node, the number of values stored in the subtree under that node. Then you can find the $i$th largest value in the list in $O(\log N)$ time as well; thus, all basic operations can be done in $O(\log N)$ time.

---
Tags: algorithms, sorting, lists, streaming-algorithm
---


# Question
Title: Putting as many items as possible with weight and size limit
I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice.

Any item has an item weight of `Iw` and item size of `Is`, these are both numerical values. Item sizes are originally translated from the values very small, small, medium, large, extra large to .1, .5, 1, 2, 2.5, respectively.

Imagine you are trying to optimize a box to have as many items in it as possible while being under a weight limit `Tw` and a size limit `Ts`. Also, the distribution of the size types (small, medium, etc) has to be a sort of bell curve where most of the items are medium, a smaller portion are small/large, and the least are extra large/very small.

I am familiar with creating a GA with only one variable, but am not sure how to do it with all of these factors.

# Answer
> 1 votes
Consider the following variant of subset sum problem:

> Given a set of $2n$ positive integers and a positive integer target $W$, is there a subset with size $n$, the sum of whose elements is $W$?

This problem is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $s$ and $t$ values, and the target is always $111\ldots1$).

Now given an instance of this variant $x\_1,\ldots,x\_{2n}$ and $W$, denote $S=\sum\_{i=1}^{2n}x\_i$. We construct $2n$ items $1,\ldots,2n$, where Item $i$ has weight $x\_i$ and size $S-x\_i$, and construct a box with weight limit $W$ and size limit $nS-W$. We can see there is a subset with size $n$ the sum of whose elements is $W$ if and only if we can put $n$ items into the box.

As a result, your problem is NP-hard in general.

---

However, there are only five kinds of sizes in your specific problem, so you can try some brute force method. Suppose you choose $c\_1$ items with very small size, $c\_2$ items with small size, $c\_3$ items with medium size, and $c\_4$ items with large size. You can enumerate all possible values of $c\_1,c\_2,c\_3,c\_4$. For each possible values of $c\_1,c\_2,c\_3,c\_4$, you can then greedily pick items. This algorithm runs in $O(nn\_1n\_2n\_3n\_4)$ time where $n\_1,n\_2,n\_3,n\_4$ are the number of items with very small, small, medium, and large sizes respectively.

# Answer
> 0 votes
This appears to be an instance of the knapsack problem, which cannot be solved by a greedy algorithm.

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


# Question
Title: Algorithm suggestion for ticket routing system using Machine Learning
**Background info**

I'm a beginner in ML, let me start there. I'm trying to implement an intelligent system that can route a ticket (in a ticketing system), to the appropriate place based on a few parameters, 5-10.

**How the algorithm should work**

For example, ticket '1234' gets sent to 'accounting' by human, normally by reading the ticket description and title (finding keywords). The ML algorithm should learn where tickets go based on where similar (based on same keywords) tickets have gone before.

**What I've tried**

I implemented a very simple NN in JavaScript using the sigmoid function to predict discrete yes/no type of outputs. If I remove the sigmoid function, I could predict where the ticket should go, based on keywords turned into parameters, perhaps using linear regression.

**The problem**

I'm not sure how I can turn keywords into number parameters, (or vectors?), that can be fed into a simple linear regression implementation. With my limited knowledge, I'm not sure if linear regression is the way to go but it certainly sounds like it. Linear regression is also a simpler algorithm I'll be able to implement myself.

Is linear regression the way to go? How can I turn an arbitrary-length paragraph (ticket description) into meaningful keywords to be used by the algorithm?

Ideally this would be JavaScript, but I see no tags for JavaScript. Odd.

# Answer
> 1 votes
Linear regression does not seem like the right tool here. This isn't a regression problem; it is a classification problem. Regression outputs a continuous number; you need to output a category (which place the ticket should be routed to; presumably there is a finite list of candidate places).

I would suggest that you learn about natural language processing. The very simplest thing you could try would be naive Bayes with bag-of-words features. Fair warning: I would not expect that you will get especially good results without a lot of knowledge of NLP (and maybe not even then); it's probably going to be challenging to find a good solution for your problem.

---
Tags: machine-learning
---


# Question
Title: Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences
Knuth has a neat algorithm that uses matrix exponentiation to compute the $n$th Fibonacci number in $O(\log\_2 n)$-time . However, there doesn't seem to be a lot of resources on generalizing his idea to other linear recurrences. Is it a generalizable idea, or is it just a special technique only applicable to the Fibonacci recurrence?

(I'm not asking for a closed-form solution, but an efficient method similar to Knuth's technique for Fibonacci numbers).

As a related question, can we speed up other recurrences by rewriting them as linear transformations, and how far can we go in applying this technique?

# Answer
Yes. This generalizes to any linear recurrence. Suppose we have the linear recurrence

$$x\_{n+1} = a\_0 x\_n + a\_1 x\_{n-1} + \dots + a\_k x\_{n-k}.$$

Define the column vector $v\_n = (x\_n,x\_{n-1},\dots,x\_{n-k})^\top$. Then we have the equation

$$v\_{n+1} = M v\_n$$

where the matrix $M$ is given by

$$M = \begin{pmatrix} a\_0 &a\_1 &a\_2 &\dots &a\_k\\ 1 &0 &0 &\dots &0\\ 0 &1 &0 &\dots &0\\ &&&\vdots\\ \end{pmatrix}.$$

It follows that

$$v\_n = M^n v\_0.$$

Therefore you can compute $v\_n$ using $O(\log n)$ matrix multiplications, using a fast exponentiation algorithm for computing $M^n$. This gives an efficient way to compute $x\_n$: first compute $v\_n$ using matrix exponentiation, then extract the first coefficient of $v\_n$ to get $x\_n$.

In fact, we can take this farther. Suppose $M$ diagonalizes, say $M=PDP^{-1}$ where $D$ is a diagonal matrix. Then

$$v\_n = M^n v\_0 = (PDP^{-1})^n v\_0 = P D^n P^{-1} v\_0,$$

so we don't need to perform matrix exponentiation; it suffices to exponentiate each of the diagonal entries of $D$. In fact, expanding terms, you can get an algebraic closed-form expression for $x\_n$. If you apply this to the Fibonacci sequence, you get the closed-form expression in https://en.wikipedia.org/wiki/Fibonacci\_number#Closed-form\_expression (in terms of powers of $(1\pm \sqrt{5})/2$, because those are the elements of $D$); for a general sequence, you get a closed-form expression of the form

$$x\_n = c\_1 \lambda\_1^n + \dots + c\_k \lambda\_k^n,$$

where $\lambda\_1,\dots,\lambda\_k$ are the diagonal entries of $D$ (i.e., the eigenvalues of $M$). This also gives a potentially more efficient algorithm for computing $x\_n$: instead of $O(\log n)$ multiplications of $k\times k$ matrices, we get $O(k \log n)$ operations on numbers.

If $M$ does not diagonalize, you may still be able to use the Jordan normal form of $M$.

See also https://en.wikipedia.org/wiki/Recurrence\_relation#Solving\_homogeneous\_linear\_recurrence\_relations\_with\_constant\_coefficients, which does something similar using the characteristic polynomial of the linear recurrence (which I think coincides with the characteristic polynomial of $M$, or something like that).
> 5 votes

---
Tags: algorithms, recurrence-relation, number-theory
---


# Question
Title: What parts of a programming language can't be defined using Regular Expressions?
I'm trying to understand how the syntax of some programming language is defined.

I know that there are some parts of the syntax of programming languages that can't be defined using regular expressions (such as an equal number of opening and closing braces) and that this is why context-free languages like BNF are needed.

What I'm struggling to understand is how one can tell which parts of the syntax of a language can only be defined using BNF and which parts could also be defined by a regular expression.

At the moment I think only BNF productions that are recursively defined can't be written as a regular expression. For example I think the following BNF can't be written as a regular expression:

```
<variable> ::= <letter> | <variable> <letter> | <variable> <digit>

```

But I think this BNF can be defined using a regular expression:

```
<digit> ::= 0|1|2|3|4|5|6|7|8|9

```

My problem with this is that I think I can write a regular expression for a recursive BNF production like this:

```
<word> ::= <letter> | <word> <letter>

<letter> ::= A|B|...|Z

```

(I'm assuming a letter is a character A-Z)

I would be greatly appreciative if someone could clarify how this works for me.

# Answer
Grammars and regular expressions are both ways to describe a language. Grammars are far more powerful. Context-free grammars are restricted grammars, with less power; regular grammars are further restricted context-free grammars, with less power again.

Regular grammars can describe exactly all regular languages, that is, all languages that can be described by regular expressions.

(Side note: this is only true for the regular expressions taught in computer science, which only use concatenation, union and Kleene star. In programming practice, extended types of regular expressions tend to be used with much more power.)

Regular grammars can be recursive, but only in a very restricted way:

* each right hand side of a rule has at most one nonterminal
* that nonterminal is either always at the *end* of a rule (for right-regular grammars) or always at the *start* (for left-regular grammars)

In your example:

```
<variable> ::= <letter> | <variable> <letter> | <variable> <digit>
<letter> ::= a | b | c | ...
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

```

the first rule isn't regular, but it only contains one recursive nonterminal: `<letter>` and `<digit>` both generate a finite set of strings. Hence, we can expand them into the rule to yield the equivalent set of rules

```
<variable> ::= A | B | ... |
               <variable> A | <variable> B | ... |
               <variable> 0 | <variable> 1 | ...

```

which *is* (left-)regular.

Hence, a regular expression for `<variable>` exists:

`(a | b | c | ...)(a | b | c | ... | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)`$^\*$

There are, in fact, straightforward algorithms for converting regular expressions to regular grammars and vice versa.

So context-free grammars can only generate non-regular languages by containing either right-hand sides with material on *both* sides of a nonterminal, for instance,

```
 <block> :== { <statements> }

```

or rules with multiple "recursive" nonterminals (i.e. of which more than one generates an infinite language).

If they do contain such rules, the language described may still be regular, and it can be really hard to figure out whether it is (it is undecidable).

However, we weren't looking at a grammar and trying to see whether it describes a regular language; we were looking at a language and trying to see whether it is regular.

A general rule I think you may find most useful in practice is to determine whether you can decide whether an utterance (in the case of a programming language: a program) belongs to the language by scanning it from left to right *while never remembering more than a constant amount of information*. The syntax is regular if and only if you can do this.

In practice, you usually see two forms of recursion in languages:

* a construct may contain another construct repeated an arbitrary number of times: this is regular;
* a construct may contain occurrences of *itself* *nested* (that is, with some form of brackets to indicate the nesting) *arbitrarily deeply*: this is not regular, but context-free.

To take C as an example:

* a block opens with a `{` character, followed by arbitrarily many (possibly empty) statements, separated by `;`, and ends with `}`: this is regular, except that
* a statement may itself be a block; thus, blocks can be nested inside blocks arbitrarily deeply: this is not regular.

JSON isn't a regular language for the same reason.

It isn't regular because the `{` and `}` brackets must match up, and while scanning from left to right, it isn't possible to determine this unless you somehow keep track of how many more `{` brackets you've seen than `}` brackets, and this count can be arbitrarily high: no constant amount of information can contain it.

Granted, in practice, you will rarely see C programs or JSON structures with blocks nested more deeply than, say, `MAXINT` times; but in theory, you may, which makes C syntax and JSON syntax non-regular.

I hope this gives you some intuition on how to distinguish regular from non-regular context-free languages in practice. It must be added that many requirements on the syntax of programming languages aren't even context-free: for instance, requiring variables to be defined before they are used is not.
> 9 votes

# Answer
Another example of a non-regular language rule can be found in C. The 4 tokens `x * y ;` can be parsed as a pointer definition or a multiplication. The correct parse depends on *meaning* of `x`. When `x` denotes a type, it's a definition, and when `x` denotes a variable, it's a multiplication. But to distinguish the two, you need to perform a "lookup" process , which can't be expressed in a grammar (regular or otherwise).

\[edit\] Obviously the 4 tokens `x * y;` are an error when `x` is neither a type nor a variable, or a variable which can't be multiplied.
> 2 votes

# Answer
# Pretty much all of it.

It's actually more useful to ask the inverse question: What parts of a programming language *can* be defined using regular expressions?

Terminal Tokens. This is why parser generators and similar tools usually give you regular expressions for defining terminals. String literals and interpolation tend to get a little complicated, but can usually be broken down into a few grammar rules when they don't fit into a regular grammar.
> 0 votes

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


title: Deadlock and safe state

text:
# Question
Title: Deadlock and safe state
I read that system being in safe state doesn't guarantee that deadlock is not possible.

Can someone give me an example where system is in safe state and deadlock is possible?

# Answer
> 1 votes
That is not possible, when a deadlock occurs, the system is in an UNSAFE state. A safe state wouldn't have any purpose if a deadlock could occur.

---
Tags: operating-systems, deadlocks
---


# Question
Title: How to remove a universal quantifier in Lean theorem prover
I am working with two binary relations: g\_o and pw\_o, and I've defined pw\_o below:

`constants {A : Type} (g_o : A → A → Prop)`

`def pw_o (x y : A) : Prop := ∀ w : A, (g_o w x → g_o w y) ∧ (g_o y w → g_o x w)`

I need to prove the following:

`theorem prelim: ∀ x y z : A, g_o x y ∧ pw_o y z → g_o x z :=`

I start with these tactics:

```
begin

   intros,

   cases a with h1 h2,

end

```

And I have this:

```
x y z : A,
h1 : g_o x y,
h2 : pw_o y z
⊢ g_o x z

```

Since pw\_o is defined with a universal quantifier, I'd like to substitute w with x, then I would have (g\_o x y → g\_o x z) ∧ (g\_o z x → g\_o y x). After isolating the first conjunct with the "cases" tactic, I can use modus ponens on that first conjunct and h1. How can I tell Lean to replace w in the definition of pw\_o with x and replace x and y in the definition of pw\_o with y and z, respectively?

# Answer
> 1 votes
I've found an answer to the question I've posed. Here are the tactics I've used:

```
begin
   unfold pw_o,
   intros,
   cases a with h1 h2,
   let h3 : A := x,
   let h4 : (g_o x y → g_o x z) ∧ (g_o z x → g_o y x) := h2 x,
   apply (h4.left h1),
end

```

I've unfolded pw\_o to make the universal quantifier explicit. After I've isolated pw\_o y z as a hypothesis, I've replaced all occurrences of w with x. Since h4.left is a function from g\_o x y to g\_o x z, I've applied it to h1, which is a term of g\_o x y, to obtain a term of g\_o x z, which was the ultimate goal.

---
Tags: proof-assistants, interactive-proof-systems
---


# Question
Title: Hoare logic, proving conjunction rule from basic rules, possible or not?
(This is HW.) Suppose I have these following proof rules given.

I am currently considering if I can prove the conjunction rule (given below) from the above given Hoare logic rules.

My answer would be "no", because from the proof rules of Hoare logic, I can neither use the `Implied` rule to prove it (because from $A$ I cannot infer $A \wedge B$) nor introduce it anywhere from the first four proof rules (the only one which introduces conjunction in the post-condition requires a `while`). I am fairly confident that this line of reasoning is correct, but am I missing anything? For example, can I argue on a the propositional logic level that since I have $P$ as a precondition, and I have $Q\_1$ and $Q\_2$ as postconditions, I can simply introduce conjunction on the propositional logic level (instead of inferring purely on Hoare logic)?

# Answer
> 4 votes
Your reasoning is fine as far as the *derivability* of this rule. To respond to the latter part of your last paragraph, if the rules you've listed are all the rules available, then those are the only rules you can use. A derivation is a tree of applications of rules. You need to be able to state what rule you're using at each node in that tree. A(n explicit) proof that this rule was derivable would be an actual derivation, i.e. tree of rule applications.

There's a different and (slightly) harder question that you probably were *not* asked which is whether the Conjunction Rule is *admissible*. That is, could the Conjunction Rule be added without causing any problems, i.e. unsoundness.

---
Tags: formal-methods, hoare-logic
---


# Question
Title: Can Dijkstra's algorithm be modified to return paths with ascending edge-id's?
Say that each edge in a directed graph is labelled with an ID. I want to run Dijkstra on the graph to find the shortest path between $source$ and $destination$, with the additional restriction that the shortest path must be in order of ascending ID's. For example, if the path is from $ A \to B \to C $, then $ID(Edge\_{AB}) \< ID(Edge\_{BC})$.

Is this feasible in polynomial time with some modification of Dijkstra?

# Answer
It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not dense, however, it will require extra amount of memory.

Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an $O(N \log N)$ complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with $O(M)$ complexity where $M$ is the number of edges.

**The method:**

1. Apply usual Dijkstra on the problem and find the shortest path.
2. Create an array of $M$ numbers initially assigned by -1.
3. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1.
4. Scan the array for 1's to find the path in ascending order.

Note that, this is an $O(M)$ algorithm instead of $O(N)$. However, if the above assumptions are satisfied, it will work better than $O(N)$. So, it depends on how much your graph is dense.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to achieve Dijkstra's O(X+Y) in time complexity if edge weights always is 1 or 2?
If we were to have a connected directed graph that has **X** edges and **Y** vertices and all the edge weights are either 1 or 2. Would it be possible to somehow achieve a time complexity of **O(X+Y)** using Dijkstra's algorithm, when finding the shortest path between the two given vertices **A** and **B** from the graph.

# Answer
If all edge weights are $1$ or $2$ you can have a linear time algorithm to find shortest path. First perform a BFS and for every edge $(u,v)$ of weight $2$ add an vertice at the middle $w$ so that you now have two edges of weight one $(u,w)$ and $(w,v)$.

After this BFS your new graph have all it edges of weight $1$ and have at most $2X$ edges.

Now perform an other BFS on this graph to find the shortest path. It gives you a complexity of $O(2X+Y)$. Thus the total complexity is $O(X+Y)$
> 2 votes

---
Tags: graphs, time-complexity
---


# Question
Title: In an FSA, can you have more than one transition for the same symbol from a single state?
My textbook asks:

> Consider the sets of strings on $\\{0,1\\}$ where the 4th symbol from the right end is different from the leftmost symbol. Construct an accepting FSA.

The answer it provides is below. However, I don't understand how you can have one transition for *0*,*1* and another for *1* from the same state. What does this mean?

# Answer
The FA in the image is an NFA as clearly a DFA cannot have more than one move for a symbol from a particular state. Also, it doesn't have any moves for state $q\_5$ nor for $q\_{10}$.
> 2 votes

---
Tags: automata, finite-automata
---


title: Confused about pumping lemma

text:
# Question
Title: Confused about pumping lemma
Here I have the method for pumping lemma to prove that a language $L$ is not regular:

1. Suppose to the contrary that L is regula, then $\exists$ DFA $A$, s.t. $L(A) = L$.
2. Let $n$ be the number of states in $A$. So, $\forall w ∈ L(A)$, if $|w| \ge n$, then $w = xyz$, where $x$, $y$, and $z$ as in Pumping Lemma.
3. Choose a suitable $w \in L$, where $|w| \ge n$.
4. Find an $i$, such that $xy^iz \not\in L$. Since $xy^iz \in L(A)$, $L(A) \neq L$.
5. 4 contradicts 1, so 1 cannot be true and therefore $L$ cannot be regular

First of all, what are we trying to prove here in other words? That the language $L$ cannot be represented by a FSM, therefore cannot be considered "regular" because a regular language is only regular if it can be represented by a FSM?

Second, how am I supposed to find "$n$" which is the number of states in $A$? Is this also known as the pumping length?

What is the proper way in which we are supposed to break up the string chosen string $w \ge n$ into 3 parts ($xyz$)?

For example this teacher broke it up in this way:

$$\begin{align\*} w &= a^{n}ba^{n+2}\\ i &= 2 \\ xy^2z &= a^{n+∣y∣}ba^{n+2} \end{align\*}$$

How is the above equation equivalent? Why is he choosing $|y|$ and adding to to $n$?

And why would any of this prove that $L$ is not regular? I'm really confused about the whole thing.

# Answer
> First of all, what are we trying to prove here in other words? That the language L cannot be represented by a FSM, therefore cannot be considered "regular" because a regular language is only regular if it can be represented by a FSM?

Indeed. Although there are varying definitions for regularity (e.g., you may define the regular languages based on regular expressions), they are all equivalent. Hence, you only need to prove your language fails to satisfy one of the equivalent requirements to be regular. In the case of the pumping lemma, you argue on the basis of DFAs.

> Second, how am I supposed to find "n" which is the number of states in A? Is this also known as the pumping length?

You are not supposed to find anything. In the classical variant of the pumping lemma, the number of states only appears explicitly in its proof. In the statement itself, there is only mention that such a number $n \in \mathbb{N}\_0$ exists.

> What is the proper way in which we are supposed to break up the string chosen string w \>= n into 3 parts (xyz)?

The pumping lemma specifies what conditions should hold for $x$, $y$, and $z$. There are three of them. And, as $n$, when proving a language contradicts the lemma (to show it is not regular), you don't get to choose $xyz$; rather, you have to show your claim *no matter what $x,y,z$ are* (as long as they suffice the conditions from the lemma).

In your example, the word has prefix $a^n$, while one of the pumping lemma's requirements is $|xy| \le n$. Hence, there is no other option for $xy$ except for it to be a prefix of $a^n$, which is why you can extend this prefix to $a^{n + m|y|}$ for any $m \in \mathbb{N}\_0$. (Remember: $y$ is the part that can be "pumped".)
> 3 votes

---
Tags: finite-automata
---


# Question
Title: Find m smallest elements in an array of size n where m = n/2
So we have an unsorted array, we need to find the first $m$ elements in ascending order (or $m$ smallest elements) where $m = \mathrm{array.size}/2$ (or $n/2$). How would we do this in linear $O(n)$ time.

What I was thinking of doing was use the SELECT algorithm to find the kth smallest element until $k = m$, but this way the complexity would be $n/2 \cdot O(n) = O(n^2)$.

# Answer
Find the median in $O(n)$ time. Then go over the array and take out all elements smaller than the median.
> 2 votes

# Answer
You can create a min heap ($O(n)$) and then perform extract min m times. ($O(mlogn)$). Time complexity will be $O(n) + O(nlogn)$.
> 1 votes

---
Tags: algorithms, time-complexity, sorting, selection-problem
---


# Question
Title: Amortized time complexity for double stack emulated queue
Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many elements are in the $stack$, and can be accessed in constant time.

I want to emulate a $queue$ by using two stacks $queue = (stack\_{push}, stack\_{pop})$ with two operations $insert$ and $remove$

$insert(queue, e)$ is implemented as:

```
insert(queue, e) {
    push(stack_push, e)
}

```

$remove(queue)$ is implemented as:

```
remove(queue) {
    if (stack_pop.size > 0) {
        pop(stack_pop)
    } else {
        while(stack_push.size > 0) {
            push(stack_pop, pop(stack_push))
        }
        pop(stack_pop)
    }
}

```

It is obviously that $insert$ takes constant time and $remove$ takes $O(n)$ time in worst case. (where n is the size of the queue).

Now considering an sequence of queue operation with length $n$ (pop an empty stack is allowed), I want to get the amortized time complexity of this queue structure. My guess is that the amortized time complexity is $O(1)$, since it **seems** that the worst case of the sequence is first $insert$ n-1 elements then $remove$, so the total cost is $O(n)$ then the amortized time is $O(n)/n = O(1)$. However I cannot figure out how to prove it.

My question is that is the amortized time complexity of the queue's operation really $O(1)$ and how to prove it?

# Answer
In the `remove` operation, every iteration of the `while` loop pops an element from `stack_push`, and this dominates the running time of `remove`. We can charge each such iteration to the `insert` operation which pushed the very same element to `stack_push`. This way we deduce that the amortized running time of both operations is $O(1)$.

You can formalize the above argument in various ways. As an example, if you perform $A$ `insert` operations and $B$ `remove` operations, then the argument above shows that you `push` at most $2A$ elements and pop at most $A+B$ elements. Hence the total running time is $O(A+B) = A \cdot O(1) + B \cdot O(1)$.
> 1 votes

---
Tags: algorithms, time-complexity, amortized-analysis, stacks, queues
---


title: Signed and unsigned numbers

text:
# Question
Title: Signed and unsigned numbers
How would the ALU in a microprocessor differentiate between a signed number, -7 that is denoted by 1111 and an unsigned number 15, also denoted by 1111?

# Answer
The short and simple answer is: it doesn't. No modern mainstream CPU ISA works the way you think it does.

For the CPU, it's just a bit pattern. It's up to you, the programmer, to keep track of what that bit pattern means.

In general, ISAs do not distinguish between different data types, when it comes to storage. (Ignoring special-purpose registers such as floating registers in an FPU.) It's just a meaningless pattern of bits to the CPU. However, ISAs *do* have different kinds of instructions that may interpret the bit pattern in different ways. For example, arithmetic instructions such as `MUL`, `DIV`, `ADD`, `SUB` interpret the bit pattern as some kind of number, whereas logical instructions such as `AND`, `OR`, `XOR` interpret it as an array of booleans. So, it is up to, the programmer, (or the author of the interpreter or compiler if you use a higher-level language) to choose the correct instructions.

There may very well be separate instructions for signed vs. unsigned numbers, for example. Some ISAs also have instructions for arithmetic with binary-coded decimals.

However, note that I wrote "modern mainstream ISA" above. There are in fact non-mainstream or historic ISAs that work differently. For example, both the original 48-bit CISC ISA of the IBM AS/400 as well as the current POWER-based 64-bit RISC ISA of the system now called IBM i, distinguish between pointers and other values. Pointers are always tagged, and they include type information and rights management. The CPU knows whether a value is a pointer or not, and only the privileged i/OS kernel is allowed to manipulate pointers freely. User applications can only manipulate pointers they own to point at memory they own using a small number of safe instructions.

There were also some historic ISA designs that included at least some limited form of type-awareness.
> 17 votes

# Answer
Short version: it doesn't know. There's no way to tell.

If `1111` represents -7, then you have a *sign-magnitude representation*, where the first bit is the sign and the rest of the bits are the magnitude. In this case, arithmetic is somewhat complicated, since an unsigned add and a signed add use different logic. So you'd probably have a `SADD` and a `UADD` opcode, and if you choose the wrong one you get nonsensical results.

More often, though, `1111` represents -1, in what's called a *two's-complement representation*. In this case, the ALU simply doesn't care if the numbers are signed or unsigned! For example, let's take the operation of `1110 + 0001`. In signed arithmetic, this means "-2 + 1", and the result should be -1 (`1111`). In unsigned arithmetic, this means "14 + 1", and the result should be 15 (`1111`). So the ALU doesn't know whether you want a signed or an unsigned result, and it doesn't care. It just does the addition as if it were unsigned, and if you want to treat that as a signed integer afterward, that's up to you.

EDIT: As Ruslan and Daniel Schepler quite rightly point out in the comments, some operands still need separate signed and unsigned versions, even on a two's-complement machine. Addition, subtraction, multiplication, equality, and such all work fine without knowing if the numbers are signed or not. But division and any greater-than/less-than comparisons have to have separate versions.

EDIT EDIT: There are some other representations too, like *one's-complement*, but these are basically never used any more so you shouldn't have to worry about them.
> 45 votes

# Answer
One of the great advantages of two’s-complement math, which all modern architectures use, is that the addition and subtraction instructions are exactly the same for both signed and unsigned operands.

Many CPUs do not even have multiply, divide or modulus instructions. If they do, they must have separate signed and unsigned forms of the instruction, and the compiler (or the assembly-language programmer) chooses the appropriate one.

CPUs also generally have different instructions for signed or unsigned comparisons. For example, x86 might follow a `CMP` with `JL` (Jump if Less than) if the comparison should be signed, or `JB` (Jump if Below) if the comparison should be unsigned. Again, the compiler or the programmer would choose the right instruction for the data type.

A few other instructions often come in signed and unsigned variants, such as right shift or loading a value into a wider register, with or without sign-extension.
> 10 votes

# Answer
It doesn't. The processor relies on the instruction set to tell it what type of data it is looking at and where to send it. There's nothing about 1s and 0s in the operand itself that can inherently signal to the ALU whether the data is a char, float, int, signed int, etc. If that 1111 is going to an electric circuit that's expecting a 2s complement, it's going to be interpreted as a 2s complement.
> 7 votes

# Answer
I'd like to give an addition to the answers already made:

In most other answers it is noted that in twos-complement arithmetic the result is the same for signed and unsigned numbers:

```
-2 + 1 = -1     1110 + 0001 = 1111
14 + 1 = 15     1110 + 0001 = 1111

```

**However**, there are exceptions:

```
Division:
  -2 / 2 = -1     1110 / 0010 = 1111
  14 / 2 = 7      1110 / 0010 = 0111
Comparison:
  -2 < 2 = TRUE   1110 < 0010 = TRUE
  14 < 2 = FALSE  1110 < 0010 = FALSE
"Typical" (*) multiplication:
  -2 * 2 = -4     1110 * 0010 = 11111100
  14 * 2 = 28     1110 * 0010 = 00011100

```

(\*) On many CPUs the result of a multiplication of two n-bit numbers is (2\*n) bits wide.

For such operations the CPUs have different instructions for signed and unsigned arithmetic.

This means the programmer (or the compiler) must use other instructions for signed and for unsigned arithmetic.

The x86 CPU for example has an instruction named `div` for doing an unsigned division and an instruction named `idiv` for doing a signed division.

There are also different "conditional" instructions (conditional jumps, set-bit-on-condition) as well as multiplication instructions for signed and unsigned arithmetic.
> 4 votes

---
Tags: arithmetic, binary
---


# Question
Title: Set of DAG vertices disconnecting a vertex from forbidden vertices
Let $v$ be a vertex with in-degree 0 in an (acyclic) DAG $G$, and let $F$ be a subset of $G$'s vertices (the "forbidden") vertices. Now suppose $U$ is a set of vertices such that every path from $v$ to $F$ intersects $U$.

Is there a commonly-used term for such sets? I was thinking about using the term "Front", but a (cursory and lazy) search tells me that's not a popular term. I can't use "cut", because that's reserved for sets of *edges* with the similar property (cutting off $v$ from $F$; usually $F$ is the subgraph of all vertices reachable from $A$ but not in $A$).

Also, suppose that $U$ is minimal, in the sense that for every $u$ in $U$, there's a path from $v$ to $F$ which intersects no other vertex of $U$. Is there a commony-used term for *this* kind of sets?

If it helps, I'm willing to refer to $v$ as a "source" and to $F$ as the set of "sinks".

# Answer
Wikipedia says that, for an undirected graph, you can say:

* $A$ is the **vertex separator** for $v$ and $F$.
* $A$ is the **separating set** for $v$ and $F$.
* $A$ is the **vertex cut** for $v$ and $F$.

perhaps these terms are used for digraphs as well, even though "connected components" are not quite the same thing in digraphs.

**edit:** @PålGD suggests the variant "separator", similar to the second option.
> 1 votes

---
Tags: terminology, dag, minimum-cuts
---


# Question
Title: How to judge the searching precision of Particle Swarm Optimization?
As the title mentioned, how can I judge the searching precision of PSO? Is this depending on the velocity of the particles? I would like to give an example to clarify my question: For a 2-D searching, the precision of grid ergodic searching is the searching step. But what the precision should be using PSO searching. From the position update formula of PSO:

$x\_i \leftarrow x\_i+v\_i$

So, we can assume the precision of PSO searching is the maximum of velocity of particles? Is this right? Generally, we set the maximum of particle velocity is about 10% to 20% of the position scale. But with this setting, we can still obtain a good precision with PSO, which contradicts previous assumption. So the searching precision of PSO is? Or it can be expressed as a function of maximum velocity and other parameters?

It seems that PSO can realize arbitrary precision... Because if there are sufficient particle numbers and iteration times, the PSO can approach to the actual solution.

# Answer
> 0 votes
If by "precision" you mean the error in the result of PSO (i.e., the difference between the value that PSO outputs and the true global optimum), the error can be arbitrarily large. PSO is a heuristic. There are no guarantees that it finds the global optimum, or even that it gets close -- and there is no formula in terms of parameters (like velocity) for how large the error will be. The error depends on the optimization problem you're solving and on the shape of the loss surface.

---
Tags: computability, optimization
---


title: Unifying Accept States in NFA

text:
# Question
Title: Unifying Accept States in NFA
I recently read the first question and answer in this homework solution https://cseweb.ucsd.edu/classes/sp08/cse105/hw2s.pdf However, I am not sure if for example, you have two accepting states originally, one in which you leave the accepting state if you read 1 and the other in which you do not leave the accepting state no matter the input then how would one unite the two states. Your help is appreciated.

# Answer
You can unite them exactly as said in the solution, "simply add a new final state to the original automaton, add epsilon transitions from every old final state to the new final state, and change every old final state into a regular state."

Suppose $N$ is the original NFA at a final state $F$. Suppose it can go to one of states $E\_1, \cdots, E\_m$ without any input if there is an epsilon transition from $F$. Suppose on input symbols $s$, $N$ changes to one of states $S\_1, \cdots, S\_n$.

Let $N'$ with its unique final state $U$ be the new NFA as constructed above from $N$. When $N'$ is at its regular state $F$, what will happen?

1. It can stay at $F$ without further input.
2. It can go to any one of $E\_1, \cdots, E\_m$ as before because of the possible epsilon transition.
3. On input $s$, it will go to one of $S\_1, \cdot, S\_n$.
4. It can go to $U$ without any further input because of the epsilon transition from $F'$ to $U$.

Note that in case 2, 3 and 4 where $N$ has moved to state $s'\in\\{E\_1, \cdots, E\_m, S\_1, \cdots, S\_n\\}$, $N$ can move to another state without further input if there is epsilon transition from $s'$. Furthermore, $N$ can move to still another state without further input if there is still epsilon transition. And so on.

In particular, if $N'$ stays at $F$ on input $s$, it can go to $U$ without any further input.

Yes, an epsilon transition functions like teleporting magically.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Network throughput with random delay selected from uniform distribution
**Background:**

I am working with IoT devices which broadcast status messages over a wireless channel periodically and at a rather high rate (500-5000 Hz). Receiving every message is not crucial but the more that are received, the better. I previously had nodes continuously synchronise clocks in order to adhere to a TDMA schedule, but this added significant algorithmic complexity to an application where 100% successful transmissions is not required. I am therefore trying a new approach based on random transmissions.

**Problem Setup:**

Let there be $N$ nodes, and let each node broadcast a status message of duration $A$ at least $d$ microseconds after its previous transmission, and no more than $D$ microseconds later. The exact delay for each packet is selected randomly and uniformly from the range $\[d, D\]$.

If packet $k$ is transmitted from a node at time $t\_k$, then the transmission time of the node's next packet $k+1$ is given by $t\_{k+1} = t\_k + \mathcal{U}(d,D)$.

The minimum delay $d$ is a constant given by the time required for the IoT device to acquire a new measurement and schedule the next packet.

The maximum delay $D$ is a variable which should be tuned to maximise network throughput (akin to ALOHA).

**Problem:**

I'm trying to derive an expression for the network throughput.

I can't find any material on ALOHA with periodic transmissions, and can only find material where the probability of transmitting is poisson, and where each transmission is independent of the last.

Thank you for your help in pointing me in the right direction.

# Answer
Let $f(t)$ be the probability distribution function for the probability that the current cycle (from the moment when node 1 broadcast the last message to the moment when node 1 will start broadcasting the next message) has duration $A+t$.

For $d\leq t\leq D$, $f(t)$ must be proportional to $A+t$. We can use the fact that $\int\_d^D f(t)\mathrm{d}t=1$ to deduce that $f(t)=\frac{A+t}{\lambda}$ for $d\leq t\leq D$, where $\lambda=D(\frac{D}2+A)-d(\frac{d}2+A)$. $f(t)=0$ if $t\>D$ or if $t\<d$.

Denote by $P\_s$ the probability that node 1 is not broadcasting at any time during a given time period of duration $A$. It can be shown, by considering the conditional probability that node 1 does not broadcast during the given time period given that node 1 is in a cycle of length $t$ at the start of the time period, that $P\_s=\int\_A^D f(t) \frac{t-A}{t+A} \mathrm{d}t=\frac{1}{\lambda}\left(\frac{\max(A,D)^2}2-A\max(A,D)-\frac{\max(A,d)^2}2+A\max(A,d)\right)$.

The probability that a given message is transmitted successfully is $P\_s^{N-1}$. The throughput is then $\frac{NP\_s^{N-1}}{A+\frac{D+d}2}$, since the average length of a cycle is $A+\frac{D+d}2$.
> 1 votes

---
Tags: probability-theory, randomized-algorithms, computer-networks
---


# Question
Title: Min-cut in a network with zero flow from source to sink
The max-flow min-cut theorem guarantees that the min-cut of a directed network equals the maximum flow. And we can compute $S$ and $T$, are disjoint subsets containing source node and sink node respectively from the residual graph.

What will be $S$ and $T$ if the max-flow from source to sink is 0, that is, there is no directed path from $s$ to $t$? Is $S$ going to be the singleton set {s} or its the empty set $\phi$ and $T$ be the vertex set $V$?

# Answer
No, your gut feeling is not correct.

Consider the following flow network with source $s$ and sink $t$, where the capacity of every edge is 1. The max-flow from source to sink is 0. The s-t cut $(\\{s,A\\}, \\{B,t\\})$ is a minimum cut since the only connecting edge $(B, A)$ goes from sink side to source side.

$$ s \longrightarrow A \longleftarrow B \longrightarrow t$$

You could learn several lessons from this simple problem. One is that source and sink are symmetric in some strong sense. It looks like your gut feeling does not respect this symmetry. Another lesson is that a few simple examples should be included in your repository. Always try constructing some simple or extreme examples when you want to check a proposition of unknown truth value.
> 3 votes

---
Tags: network-flow, ford-fulkerson
---


title: amortized analysis of max heap

text:
# Question
Title: amortized analysis of max heap
Q) Consider an ordinary binary max-heap data structure with n elements that supports insert and extract-max in $O(log(n))$ worst-case time. Give a potential function $\Phi$ such that the amortized cost of insert is $O(log(n))$ and the amortized cost of extract-max is $O(log(n))$, and show that it works.

---

**solution**

The formula of amortized cost is

$a\_n = c\_n + \Phi(D\_n) - \Phi(D\_{n-1})$

Where the potential function: $\Phi (D\_n) = n log(n)$.

for insert:

$= c\_n + \Phi(D\_n) - \Phi(D\_{n-1}) \leq log(n) + n log(n) - (n-1)log(n-1) \leq 3 log(n+1) = O(log(n))$

So, the amortized cost of insert is $O(log(n))$

extract max:

$a\_n = c\_n + \Phi(D\_n) - \Phi(D\_{n-1}) \leq log(n) + n log(n) - (n+1)log(n+1) = log(n) + n(log(n)) - n log(n+1) - log(n+1) \< 0$

So, the amortized cost of extract-max is $O(1)$

---

Assuming this is correct. Could someone explain how they got the potential function?

# Answer
When doing amortized analysis with a potential function, the potential function appears out of nowhere. One way to come up with a potential function is to try picking some function, and then see if the calculation goes through. If that doesn't work, one can try adjusting the potential function to make the calculation go through. Sometimes we might let $\Phi(\cdot)$ be a placeholder, see what properties it needs to have to make the proof go through, and then try to come up with a function that has those properties.

In other words -- there is not necessarily any systematic way to find a potential function that works. You might need to use trial-and-error, or a lucky guess, or other methods.
> 0 votes

---
Tags: amortized-analysis
---


# Question
Title: Algorithm to convert a fixed-length string to the smallest possible collision-free representation?
I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which produces a string of length 4, however, I'm not sure it's a suitable tool for the job (I want to prevent collisions).

Basically, if the input is 000-000-0000 (without the dashes), I want the output to be something like 4xg4. In this use case, the advantage is that I have 10 digits, thus I could "convert" them to something smaller that uses letters as well.

Are you aware of any algorithm implementation for this?

# Answer
As ratchet freak says, you have ten decimal digits, which *should* give $10^{10}$ possible values. But in practice, there are a few more restrictions. The format of a North American telephone number looks something like this:

```
[2-9][0-8]\d - [2-9]\d\d - \d\d\d\d

```

This gives 8\*9\*10 * 8\*10\*10 * 10\*10\*10\*10 values. In addition, the fifth and sixth characters can't both be 1, which removes 1% of these. This means there are 5,702,400,000 possible telephone numbers. (Let's call this number $T$.)

If you want to encode these using an alphabet with $b$ different characters, you'll need a code $\lceil \log\_b T \rceil$ characters long. So if you want a code four characters long, you'll need $b \geq 275$. If you want a code five characters long, you'll need $b \geq 90$. And if you want a code six characters long, you'll need $b \geq 43$.

Unfortunately, this is the best you can do, unless you have additional information about what numbers you'll be getting. This comes down to the *pigeonhole principle*, a remarkably straightforward theorem that's quite useful in CS. It's mathematically impossible to use fewer characters than this without ever having any collisions. You can make collisions extremely unlikely, but never fully prevent them.

(You can also make *some* of the codes be shorter without collisions, but as a consequence some of them will have to be longer. Again, pigeonhole principle.)

P.S. Note that, while base64 also produces a six-character string (since 64 is between 43 and 90), you can take advantage of the fact that you only need 43 to choose a "nicer" character set. For example, you can get rid of `o`, `O`, `0`, `Q`, `I`, `l`, and `1` to cut down on confusion in writing. My suggestion would be `23456789ABCDEFGHJKLMNPRSTVXYZabdeghknpqrt-=`.
> 15 votes

# Answer
You have 10 base10 digits. This is $10^{10}$ possible values.

Encoding this in an alphabet with 64 tokens you need $\lceil \log\_{64}(10^{10}) \rceil = 6$ characters.

If you encode it in straight binary you only need $\lceil \log\_{2}(10^{10}) \rceil = 34$ bits total. 4 bytes + 2 bits.

Unless there is a pattern in the number itself this is the best you can do.

Note that this looks at the number in a vacuum. If you encode more than just that number you can use arithmetic encoding to use some of the "spare room" the rounding creates.
> 11 votes

# Answer
Draconis already gave an excellent answer of the specific theoretical limitations of your question. However, I figured it wouldn't hurt to show an explicit implementation of such an encoding schema.

As Draconis covered we need an alphabet of at least 90 letters in order to encode a North American based telephone number in 5 characters or less. As luck would have it standard ASCII has 95 printable characters, of which one is the space character and thus unsuitable for encoding (using the restriction that all elements be, well, visible). This gives us four extra characters, so for ease of reading I am removing the quotation characters ('"\`) and capital I as it may be confused for lower case L.

The algorithm itself is fairly simple, but there are some major caveats. Naively we could just convert the telephone number into a base 10 number and then convert it to a base 90 representation, but our solution relies upon the reduced variations of a North American telephone number, otherwise we would need an alphabet of at least 100 characters. Consequently the naive implementation would actually fail for "large" inputs. So instead we will convert the telephone number to base 10 with some reductions to get it in the right form.

To be exact, the first (counting from right to left) seven digits will be converted as normal, but we will subtract $2\cdot 10^6$ to account for the seventh digit not being allowed to be zero or one (in effect, we are shifting \[2-9\] down to \[0-7\]). Then the next three digits will be converted with similar restrictions and multiplied by $8 \cdot 10^6$ instead of $10^7$ to account for the seventh digit's having only 8 possible values, not ten.

Sample Python implementation included below

```
charset = ''.join([chr(i) for i in range(33,127) if i not in [34, 39, 73, 96]])
def encodeTel(t, charset):
    n = ''.join(t.split('-'))
    num = int(int(n[3:]) - 2e6 + ((int(n[0])-2)*90 + int(n[1:3]))*8e6)
    encoded = []
    base = len(charset)
    x = num
    if x == 0:
        encoded.append(charset[0])
    while x > 0:
        encoded.append(charset[x % base])
        x //= base
    return ''.join(encoded[::-1])

```

Sample output:

```
In [1]: encodeTel('989-999-9999', charset)
Out[1]: '|l8,~'
In [2]: encodeTel('200-200-0000', charset)
Out[2]: '!'

```

(Note: I haven't actually checked if the given function absolutely has no collisions, but it shouldn't have any and a cursory check didn't find any in the first 85 million valid telephone numbers or so)
> 2 votes

---
Tags: algorithms, data-compression, base-conversion
---


# Question
Title: Find a CFG for $\{a^ib^jc^k \mid i,j,k\ge0 , \text{if } j=1 \text{ then } i=k\}$
I've tried but I can't figure out any solution. Is there any hint for me to solve the question?

# Answer
> 1 votes
$ S =\>S\_1 \mid S\_2 \mid S\_3 $

$ S\_1 =\>AC $

$ S\_2 =\> aS\_2c \mid b $

$ S\_3 =\> AbbBC $

$ A =\>aA \mid epsilon $

$ B =\>bB \mid epsilon $

$ C =\>cC \mid epsilon $

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


# Question
Title: Are there decision problems outside of NP?
Consider any problem in NP-hard, then it has a polynomial reduction from a problem in NP in polynomial time. Though, it isn't clear by this definition whether there are decision problems in NP-hard that are not in NP.

Are there any known ones?

# Answer
The nondeterministic time hierarchy theorem shows that, e.g., $\mathrm{NP}\subsetneq\mathrm{NEXP}$, so any $\mathrm{NEXP}$-complete problem is $\mathrm{NP}$-hard but not in $\mathrm{NP}$. For a more extreme example, the halting problem is $\mathrm{NP}$-hard but not in $\mathrm{NP}$.
> 5 votes

---
Tags: computability, time-complexity
---


title: Rooted Tree Isomorphism Algorithm

text:
# Question
Title: Rooted Tree Isomorphism Algorithm
I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:

Let $S\_{u}$ be the number of vertices in the rooted subtree of vertex $u$. Namely, the size of the subtree of $u$. Now Let $L\_{i}$ = {$S\_{u}$ : $lvl(u)$ = $i$}. Here, $lvl(v)$ denotes the level of $v$. Also the height of a tree is the maximum level of any of its nodes.

Now the conjecture:

Let $H\_{1}$ and $H\_{2}$ be the heights of the rooted trees $T\_{1}$ and $T\_{2}$, respectively. $T\_{1}$ and $T\_{2}$ are isomorphic if and only if $H\_{1} = H\_{2}$ and for every integer $i \in \[ \\,1,H\_{1}\] \\, $, the multiset $L\_{i}$ of $T\_{1}$ and that of $T\_{2}$ are the same.

Apparently this conjecture is false because i implemented a C++ program (to solve a competitive programming task) that is based on it, but it failed system tests. Still, it may be an implementation fault, so i'd like to know if there are any counterexamples to this conjecture.

# Answer
Nice conjecture on tree isomorphism.

However, here is a counterexample.

---

**Exercise.** Construct a counterexample using a binary tree.
> 3 votes

---
Tags: trees, graph-isomorphism
---


# Question
Title: Edit Distance Algorithm (variant of longest common sub-sequence)
I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming.

The problem is defined as follows:

suppose that you are making a spell-checker with suggestions for misspelled words. You would like to be able to find the words that are closest to the string of non-word letters that a user has input.

These words can differ from the typed string by

1. missing a letter
2. having an extra letter
3. having a letter replaced with another letter

the costs are:

$c\_i$, the cost of an insert

$c\_d$, the cost of a deletion

$c\_r$, the cost of a replacement

with the intention of beginning with a recursive approach that can be converted into a dynamic program, the idea is to build up from substrings.

```
let T(j,k) denote minimum cost to transform
substring A[1...j] to substring B[1...k].

then there are four ways to convert A[1...j]
into B[1...k]

1. delete the jth character of A[1...j] and
convert the first j-1 characters of A into the
first k characters of B.  This equals cost cd +
T(j-1, k)

2. convert the first j characters of A into the
first k-1 characters of B, and insert a kth
character into B[1...k-1].  This equals cost ci
+ T(j, k-1)

3. replace the jth character of A with the kth
character of B and convert the first j-1
characters of A into the first k-1 characters
of B.  This equals cost cr + T(j-1,k-1)

4. If characters A[j] = B[k], just convert
A[1..(j-1)] into B[1..(k-1)]
This has cost T(j-1,k-1)

This can be written as a recursion equation,
taking the minimum over all four alternatives
at each step:

T(j,k) = minimum of:
    {    T(j-1, k) + cd
         T(j,k-1) + ci
        T(j-1,k-1) if A[j] = B[k]
      T(j-1, k-1) + cr if A[j] != B[k]
    }

```

The question is this: suppose we're to add a "swap" function which corrects two letter which are typed in the wrong order. How would we modify the euation for the cost of changing string A into string B if the the cost of a swap is $C\_s$?

My thought is:

```
T(j-1, k+1) if A[j,k] = B[k,j] ?

```

# Answer
> 1 votes
the additional cost of adding a swap function should be:

T(j-2,k-2) + Cs , if A\[j-1\]=B\[k\],and A\[j\]=B\[k-1\]

I found the answer by studying the Damerau–Levenshtein distance modification of the classic edit distance problem.

Source: https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein\_distance

---
Tags: dynamic-programming, edit-distance
---