# Question
Title: Can/Do multiple processes run simultaneously on a multi-core system?
I understand context switches and threading on a single core system, but I'm trying to understand what happens in a multi-core system. I know multiple threads from the same process can run simultaneously in a multi-core system. However, can multiple processes run simultaneously in such a system as well?

In other words, in a dual core processor: \- How many processes can run simultaneously(without context switching) if all processes are single threaded? \- How many processes can run simultaneously if there are 2 processes and both are multi-threaded?

# Answer
> 1 votes
This question is more related to the difference between a thread and a process. Here is a hint: When it comes to kernel scheduling structures, the only thing the kernel looks at is threads, not processes.

A process is easier to understand as a group of threads. All processes have to have at least one thread, and it is that thread that is scheduled in the operating system, not the process.

So, with this understanding, in a dual core system with two processes each containing a thread each, there are two threads total that are scheduled on the two cores.

# Answer
> 1 votes
Yes multiple processes can run simultaneously (without context-switching) in multi-core processors.

If all processes are single threaded as you ask then 2 processes can run simultaneously in a dual core processor.

The same for multi-threaded processes as you ask, 2 processes again, one for each core could run at the same time.

You can verify the above by using the command line 'top' in linux systems or the 'Task Manager' in Windows. Launch two CPU-intensive processes for a dual core processor and see how they get close to 100% for each cpu core and a third process gets in the way of that 100%. For a quad core the same occurs with 4 processes and the fifth and so on.

Do not confuse multi-core with multi-thread support. 1 core may be able to run just 1 or more threads (if it is single-threaded core or multi-threaded core respectively). For example, AMD FX 8350 has 8 cores each able to run a single thread of a process while Intel i7 3770K for example has 4 cores each able to two threads of a process. But somewhere here we are getting beyond what you asked so I hope this covers it!

# Answer
> 1 votes
Define "run".

As I am typing this, my MacBook has about 150 processes running, with a total of maybe 800 threads (rough guess checking Activity Monitor).

Since this MacBook has two cores without hyperthreading, at any given time two threads and no more can be executing (actually using the CPU). Any number of threads could be ready for execution (that is they would be running apart from the fact that both cores are already busy), if there are threads ready to run but not running, the OS will from time to time pause on of the two running threads and let one of the other ready threads run. But of the 800 threads, most are *not* ready, but are waiting for something (like waiting for work to appear that they can perform).

There is no restriction to the number of different processes that running threads and ready threads could belong to.

There will be *some* limitation to the number of processes and threads, but that limitation will be somewhere in the thousands, and hugely bigger than the number of threads that can be executing.

---
Tags: computer-architecture, parallel-computing
---


title: When to free physical registers

text:
# Question
Title: When to free physical registers
When we do register renaming to avoid WAR and WAW hazards while executing instructions, how can we know that there is no need for a physical register anymore and we can put it back in the free list?

# Answer
> 4 votes
I find the simplest way to think about this problem is to consider a machine that has two Register Alias Tables (RAT). These tables simply store the physical register identifier associated with each architectural register.

The two tables sit in the retirement stage (the Retirement Register Alias Table or RRAT), and the renaming stage. Retirement and renaming both happen *in*-order, no matter how the execution stages work. The Retirement-RAT represents the architectural/non-speculative state of the machine. The renaming RAT represents the speculative state of the machine (the state the machine will have if all of the speculative decisions made before the current instruction were to be found to have been correctly predicted).

Think about the state of the Retirement Register Alias Table just before the retirement of an instruction that writes to (architectural) register $R$. At this point the Retirement Register Alias Table contains a mapping from $R$ to $P\_0$, the *previous* physical register that was assigned to architectural register $R$, and the next instruction to retire will have a different assignment from $R$ to $P\_1$. Since retirement happens in-order, we know that all instructions that could have referenced physical register $P\_0$ have already retired, and thus physical register $P\_0$ can be returned to the free list.

Many (most) actual out-of-order designs do something more complicated than what I've described here (instead of Register Alias Tables mapping from architectural to physical registers, there are CAMs mapping from physical to architectural registers which allows quicker recovery from mis-speculations), but the reasoning techniques are the same: renaming and retirement both happen *in*-order, and you can use that fact to reason about which registers can be returned to the free list.

---
Tags: computer-architecture
---


# Question
Title: Chess Knight minimum moves to destination on an infinite board
There are tones of solutions for Knights tour or shortest path for Knights movement from source cell to destination cell. most of the solutions are using BFS which seems the best algorithm.

Here is my implementation using HashMap:

```
    public class Knight_HashMap {

    static HashMap<String, Position> chessboard = new HashMap<String, Position>();
    static Queue<Position> q = new LinkedList<Position>();
    static int Nx, Ny, Kx, Ky, Cx, Cy;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("insert Board dimentions: Nx, Ny");
        Nx = sc.nextInt();
        Ny = sc.nextInt();
        System.out.println("inset Knight's location: Kx, Ky");
        Kx = sc.nextInt();
        Ky = sc.nextInt();
        System.out.println("insert destination location: Cx, Cy");
        Cx = sc.nextInt();
        Cy = sc.nextInt();
        sc.close();

        // Assume the position for simplicity. In real world, accept the values using
        // Scanner.
        Position start = new Position(Kx, Ky, 0); // Positionition 0, 1 on the chessboard
        Position end = new Position(Cx, Cy, Integer.MAX_VALUE);

        chessboard.put(Arrays.toString(new int[] { Kx, Ky }), new Position(Kx, Ky, 0));

        q.add(start);

        while (q.size() != 0) // While queue is not empty
        {
            Position pos = q.poll();
            if (end.equals(pos)) {
                System.out.println("Minimum jumps required: " + pos.depth);
                return;
            } else {
                // perform BFS on this Position if it is not already visited
                bfs(pos, ++pos.depth);
            }
        }

    }

    private static void bfs(Position current, int depth) {

        // Start from -2 to +2 range and start marking each location on the board
        for (int i = -2; i <= 2; i++) {
            for (int j = -2; j <= 2; j++) {

                Position next = new Position(current.x + i, current.y + j, depth);

                if (isValid(current, next)) {
                    if (inRange(next.x, next.y)) {
                        // chessboard.put(Arrays.toString(new int[] { next.x, next.y }), next);
                        // Skip if next location is same as the location you came from in previous run
                        if (current.equals(next))
                            continue;

                        Position position = chessboard.get(Arrays.toString(new int[] { next.x, next.y }));
                        if (position == null) {
                            position = new Position(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE);
                        }
                        /*
                         * Get the current position object at this location on chessboard. If this
                         * location was reachable with a costlier depth, this iteration has given a
                         * shorter way to reach
                         */
                        if (position.depth > depth) {

                            chessboard.put(Arrays.toString(new int[] { current.x + i, current.y + j }),
                                    new Position(current.x, current.y, depth));
                            // chessboard.get(current.x + i).set(current.y + j, new Position(current.x,
                            // current.y, depth));
                            q.add(next);
                        }
                    }
                }

            }

        }

    }

    private static boolean isValid(Position current, Position next) {
        // Use Pythagoras theorem to ensure that a move makes a right-angled triangle
        // with sides of 1 and 2. 1-squared + 2-squared is 5.
        int deltaR = next.x - current.x;
        int deltaC = next.y - current.y;
        return 5 == deltaR * deltaR + deltaC * deltaC;
    }

    private static boolean inRange(int x, int y) {
        return 0 <= x && x < Nx && 0 <= y && y < Ny;
    }

}

class Position {

    public int x;
    public int y;
    public int depth;

    Position(int x, int y, int depth) {
        this.x = x;
        this.y = y;
        this.depth = depth;
    }

    public boolean equals(Position that) {
        return this.x == that.x && this.y == that.y;
    }

    public String toString() {
        return "(" + this.x + " " + this.y + " " + this.depth + ")";
    }
}

```

This works well with small dimension but with 10^9 x 10^9 I face `outOfMemory` exception. I also tried with java 2d array, ArrayList, HashMap alongside with a LinkedList as Queue. but for that dimension 10^9 x 10^9 with any data structure, I face `outOfMemory` exception.

Is there possibility of optimization to avoid `outOfMemory` or anyother way/data structure to handle such huge dimension?

*Note:* I should mention this question is from BAPC17 contest named ***Knight's Marathon***

# Answer
> 2 votes
thanks to matt timmermans by his hint I realized for infinite chess boards no search algorithm BFS, DFS, A\*, Dijkstra should be used. just calculate diagonal symmetry and imagine that start point as (0,0). just 2 corners should be hardcoded. adopted from here

```
System.out.println((int) distance(ENDx - STARTx, ENDy - STARTy));
public static double distance(int x, int y) {
        // axes symmetry
        x = Math.abs(x);
        y = Math.abs(y);
        // diagonal symmetry
        if (x < y) {
            int t = x;
            x = y;
            y = t;
        }
        // 2 corner cases
        if (x == 1 && y == 0) {
            return 3;
        }
        if (x == 2 && y == 2) {
            return 4;
        }

        // main formula
        int delta = x - y;
        if (y > delta) {
            return (delta - 2 * Math.floor((float) (delta - y) / 3));
        } else {
            return (delta - 2 * Math.floor((delta - y) / 4));
        }
    }

```

# Answer
> 5 votes
The easiest way to solve this problem is to greedily move in the best direction until you get within 100 squares or so, and then A\* from there.

Figuring out exactly how close you can get before you have to switch to A\* is an interesting problem, but 100 squares away will surely be fine, and A\* from there fits into a reasonable amount of memory.

Also note that the greedy portion will only involve 1 or 2 types of moves, and it's not hard to figure out how many of each type you will do without making an individual decision for each one.

EDIT: Since this is the CS stack I guess I should prove that it works. OK:

By symmetry I only need to consider two cases:

Case 1 -- 2 \>= dx/dy \>= 1/2

In this case, the greedy portion will choose between move near the diagonal. Each move reduces the manhattan distance to target by 3, and all other moves will decrease the manhattan distance by at best 1.

Lets say the length of the longest path of greedy moves is N. That path will get to a position at most 3 moves away from the target, so the best path length is at most N+3.

Now, if I use only N-m moves from the greedy path, then I will be left at a position at manhattan distance at least 3m, and it will take at least 3m moves to correct that, so the best achievable path length would be N-m+3m. If that is gonna be \< N+3, then m \< 2, so the shortest path includes at least N-1 moves from a longest greedy path.

Case 2 -- 1/2 \>= dx/dy \>= -1/2:

In this case, the greedy portion will consist of moves near the horizontal. Each greedy move will reduce the x distance by 2, and all other moves will reduce it by at most 1.

Again the longest greedy path (length N) will get within 3 moves. If we make N-m greedy moves, we are left at x distance at least 2m, and require 2m moves to fix it. If the best path consists of only N-m greedy moves, we need N+m \< N+3, so the bast path can have at least N-2 elements from the longest greedy path.

Conclusion:

We can do much better than getting within 100 squares. Calculate the moves in the longest greedy path, and remove 2 moves of each type (up to the total number of moves of that type, if it contains less), and we will be left with only moves that can be part of a shortest path.

That will get us within 8 squares, and A\* from there will not be expensive.

# Answer
> 5 votes
There is a closed form solution for finding the minimum number of moves the chess knight needs to move a specified displacement on the infinite chess board. Let $g$ be the requisite displacement expressed as a Gaussian integer; the real part of $g$ will be the horizontal displacement, and the imaginary part of $g$ will be the vertical displacement. Then we may write

$$g = ((1-i)g+(2-i)d)(2+i) - (g+(2+i)d)(2-i). $$

Here, $d$ can be any Gaussian integer; the value of $d$ which minimizes the number of knight moves is $d=Cint((2i-5)g/10)$, where $Cint$ is the closest Gaussian integer of the argument. The first term yields the requisite counterclockwise moves, and the second term yields the requisite clockwise moves. The real and imaginary parts of the counterclockwise and clockwise coefficients together yield the total minimum requisite moves of the chess knight, while simultaneously specifying all minimal paths.

N.B. Reply to amass.jack

I am an originator of this formula. I do not yet know of any prior publication. However, I have generated lecture notes for my talk at Acacia Creek to be given on the third Wednesday in February, as well as additional notes with numerous worked examples. These notes set forth the fundamental theory providing a foundation for the formula. Robert Word, Ph.D.

I have encountered difficulties in activating the present interface to post a reply to you, for unclear reasons. Hence, I copied the same reply into a number of related Facebook groups dealing with Mathematics, in case you might happen across them.

# Answer
> 0 votes
How far does it scale currently? If you get close, some tweaks may help. If you approach doesn't scale at all (which I suspect), you'll need to reconsider the approach in general.

Some ideas:

1. BFS uses more memory than DFS (e.g. A\*), as you need to keep more data in memory. For this problem, you could prioritize moves that go into the general direction.
2. String keys seem to be quite wasteful. Consider using a specialized data structure for sparse 2d arrays (I have implemented one here, you'll probably find more / better ones on the net). Or use a Position2D hash key.
3. Do you need all this data in Position?
4. Can you exploit the structure of the moves in some way? Are there some constraints that you can exploit? Do you need the full grid?

---
Tags: algorithms, shortest-path, searching, board-games, space-analysis
---


title: Running Time for Finding Maximum

text:
# Question
Title: Running Time for Finding Maximum
Consider the algorithm findMax that finds the maximum entry in an integer array.

**Algorithm** findMax($A$)
***Input***: An integer array $A$
***Output***: The maximum entry of $A$

```
1. m <- A[0]
2. for i <- 1 to A.length - 1 do
3.     if A[i] > m then
4.        m <- A[i]
5. return m

```
1. Show that there are constants $c\_1,d\_1,c\_2,d\_2 \in \mathbb{N}$ such that $c\_1n + d\_1 \leq T\_{findmax(n)} \leq c\_2n + d\_2$ for all $n$, where $n$ is the length of the input array.
2. Argue that for every algorithm A for finding the maximum entry of an integer array of length $n$ it holds that $T\_A$$(n)$ $\geq n$.

**NOTE**: The (worst-case) running time of an algorithm A is the function $T\_A: \mathbb{N} \rightarrow \mathbb{N}$ where $T\_A$$(n)$ is the maximum number of computation steps performed by $A$ on an input of size $n$.

---

1. My intuition was that $c\_1$ and $c\_2$ correspond to the number of times the next element of the array is greater than the current maximum, but I don't see how to fit it in the equation.

**1** \- executed $1$ time
**2** \- executed $n$ times
**3** \- executed $(n-1)$ times
**4** \- executed $c$ times - - - best case: $0$ times / worst case: $(n-1)$ times
**5** \- executed $1$ time

In the total sum of steps:

* Step 1 + Step 5 = 2 times
* Steps 2,3,4 $\leq 3n$ times

Therefore, $c\_1 = 1$, $d\_1 = 2$, $c\_2 = 3n$, $d\_2 = 2$.

2. For the second question, would it be enough to show that the best-case scenario (array sorted in non-increasing order) takes at least $n$ steps?

# Answer
> 2 votes
### Question 1

I think you are overcomplicating things, the question is about $\mathcal{O}$-notation, you don't need any meaning attached to these constants. Try making your life easy and pick simple ones:

You only need a lower bound, so just set $c\_1 = d\_1 = 1$, clearly $n + 1 \leq T\_{\text{findMax}(n)}$.

Similarly you only need an upper bound, set $c\_2 = 4$ and $d\_2 = 42$, giving you $4n + 42 \geq T\_{\text{findMax}(n)}$.

### Question 2

It's not clear how $T\_A$ is defined, so it's hard to answer Question 2.

Assume there is an algorithm $A$ with $T\_{A(n)} = t \< n$. So this algorithm is restricted to read/compare at most $t$ elements of $a\_1,\dots,a\_n$ and therefore there is always a sequence $a\_1,\dots,a\_n$ where the algorithm will fail, ie. the actual maximum is not among the $t$ elements. $\Rightarrow\\!\Leftarrow$

---
Tags: algorithms, algorithm-analysis, time-complexity, asymptotics, runtime-analysis
---


# Question
Title: Grammar of words with exactly $k$ prefixes in another grammar
Given a context-free grammar $G$, how can one systematically construct a grammar $G\_k$ such that

$$ L(G\_k) = \\{w \in \Sigma^\* : |\text{Pref}(w) \cap L(G)| = k\\} $$

where $\text{Pref}(w)$ is the set of $|w|+1$ prefixes of $w$? Assume $G$ is unambiguous, if needed.

# Answer
Unfortunately there is no such construction, as the context-free languages are not closed under this operation.

Consider the language $\\{ a^nb^n \mid n\ge 1\\} \cup \\{ a^kb^nc^n \mid k,n\ge 1 \\}$.

The language that has two prefixes in this language is $\\{ a^nb^nc^n \mid n\ge 1\\}\cdot \\{a,b,c\\}^\*$, which is not context-free.
> 3 votes

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


# Question
Title: How to calculate time complexity of a randomized search algorithm?
Example: Finding an element from a sorted array

Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the array and performs the following operation:

```
if (value == A[randomIndex])
   // element found
else if (value < A[randomIndex])
   // check the left subarray of the randomIndex
else
   // check the right subarray of the randomIndex

```

This is similar to binary search but instead of selecting a **mid index** of the low and high index, we simply select a **random index** between low and high index.

Can anyone please provide the time complexity for this algorithm in **worst, average and best case** with a simple explanation for each?

# Answer
Best case is $O(1)$, that is when you find the element in the first check.

Worst case is $O(n)$, and it happens when the element is in the first position, and in each check you get the last position, thus going through the whole array.

Average case is a little bit more tricky to get, since we need to solve a recurrence to get the expected value. Let $T(n)$ be the expected time for an array of size n. The pivot is chosen randomly, so each posible pivot has a probability $p = \frac{1}{n}$. So, we have this:

$T(n) = T(1)/n + T(2)/n + ... + T(n-1)/n + 1$

We add that 1 at the end, because that's the constant time we have for checking at each step. Now we multiply each side by n:

$nT(n) = T(1) + T(2) + ... + T(n-1) + n$

Which also gives:

$(n-1)\*T(n-1) = T(1) + T(2) + ... + T(n-2) + (n-1)$

So we can subtract those equations and we get

$n\*T(n) - (n-1)\*T(n-1) = T(n-1) +1$

$n\*T(n) = (n-1)\*T(n-1) + T(n-1) +1$

$n\*T(n) = n\*T(n-1) + 1$

$T(n) = T(n-1) + 1/n$

And "unrolling" this equation, we have:

$T(n) = 1 + 1/2 + 1/3 + ... + 1/n$

And the right side of the equation is the nth harmonic number. We can show that the nth harmonic number is $\Theta(\log n)$ So we have that the average time for the algorithm is $\Theta(\log n)$
> 6 votes

# Answer
Best Case time complexity is when you randomly choose an element and it comes out to be the desired element. In this case, time complexity is constant, i.e., **O(1)**

Worse case is when the very first or last element gets selected randomly every time and the desired element lies at the end or beginning of the array, respectively! For example, consider the array {9,8,6,4,5}. Suppose we need to find 5. Worse case scenerio is: 9 is selected randomly. We consider the right array. 8 is selected now. again we consider the right array. 6 is selected next, so on and so forth until we reach 5. Here, we have traversed through every element of the array so the **complexity will be O(n)**.
> 0 votes

---
Tags: algorithms, time-complexity, asymptotics, search-algorithms
---


# Question
Title: Is there a name for this priority queue data structure?
While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of some set, and each internal node is the $\max$ of its two children. I came up with a *BuildHeap* algorithm that's $O(n)$, a *GetMax* algorithm that's $O(1)$, an *Insert* algorithm that's $O(\log n)$, and a *Delete* algorithm that's $O(\log n)$. The number of nodes in this "heap" is $2n-1$ where $n$ is the number of elements in the underlying set. The structure is simpler than a binary heap.

Is there a name for this data structure?

\[edit\]

Code:

```
import Data.List
import Data.Ord

data Heap a = Leaf a | Branch a (Heap a) (Heap a) deriving Show

getMax :: Heap a -> a
getMax (Leaf x) = x
getMax (Branch x _ _) = x

leaf :: Ord a => a -> Heap a
leaf = Leaf

branch :: Ord a => Heap a -> Heap a -> Heap a
branch h1 h2 = Branch (max (getMax h1) (getMax h2)) h1 h2

buildHeap :: Ord a => [a] -> Heap a
buildHeap xs = fst $ buildSubHeap (length xs) xs
  where buildSubHeap 1 (x:xs) = (Leaf x, xs)
        buildSubHeap n xs = let (leftSubHeap, remainder1) = buildSubHeap (div n 2) xs
                                (rightSubHeap, remainder2) = buildSubHeap (n - div n 2) remainder1
                            in (branch leftSubHeap rightSubHeap, remainder2)

insertIntoHeap :: Ord a => a -> Heap a -> Heap a
insertIntoHeap x (Leaf y) = branch (leaf x) (leaf y)
insertIntoHeap x (Branch m h1 h2) = branch h2 (insertIntoHeap x h1)

deleteInsignificantElement :: Ord a => Heap a -> Heap a
deleteInsignificantElement (Branch _ (Leaf x) (Leaf y)) = Leaf (max x y)
deleteInsignificantElement (Branch _ h1 h2) = branch (deleteInsignificantElement h2) h1

getInsignificantElement :: Ord a => Heap a -> a
getInsignificantElement (Branch _ (Leaf x) (Leaf y)) = min x y
getInsignificantElement (Branch _ h1 h2) = getInsignificantElement h2

replaceMax :: Ord a => Heap a -> a -> Heap a
replaceMax (Leaf x) y = Leaf y
replaceMax (Branch m h1 h2) y | getMax h1 == m = branch (replaceMax h1 y) h2
                              | getMax h2 == m = branch h1 (replaceMax h2 y)
                              | otherwise = undefined

deleteMax :: Ord a => Heap a -> Heap a
deleteMax heap = replaceMax (deleteInsignificantElement heap) (getInsignificantElement heap)

data HeapObserver a = Singleton a | PushHeap a (Heap a) deriving Show

popHeap :: Ord a => Heap a -> HeapObserver a
popHeap (Leaf x) = Singleton x
popHeap heap = PushHeap (getMax heap) (deleteMax heap)

undown :: Down a -> a
undown (Down x) = x

heapsort :: Ord a => [a] -> [a]
heapsort [] = []
heapsort xs = map undown . flattenHeap . buildHeap . map Down $ xs
  where flattenHeap heap = case popHeap heap of
                           Singleton y -> [y]
                           PushHeap y ys -> y : flattenHeap ys

example_list = [234,234245,13235,14223,12,5,41,24,132,4134,25,234, 94875937, 34059, 784, 34875, 234, 765, 909]

main :: IO ()
main = print (heapsort example_list == reverse (sort example_list))

```

# Answer
> 6 votes
This is essentially a Segment tree which is a data structure that augments an array with a binary tree as you describe such that:

* You have fast set and get at any index
* You have fast "aggregate" queries on ranges
* You can support fast update queries on ranges, for some combinations of updates and queries

The $j$th node at height $k$ in the tree "summarizes" a subarray $\[j\*2^k, (j+1)\*2^k)$ of the original array. Since each element of the array appears in only logarithmically many such subarrays, we can do updates in $O(\log n)$ time.

The range queries can use any associative operation. In your example the operation is $\max$, but other examples include sum, product, even standard deviation (via sum and sum of squares).

---

I originally called this a Fenwick Tree (aka Binary Indexed Tree), which is a similar structure but which compresses the tree into only exactly $n$ storage with no overhead(but loses access to the original array).

# Answer
> 1 votes
You've just reinvented a range-query structure. This is an instance of the more general idea that, if you put all data at only the leaves of a binary tree, you can use internal nodes to represent substructures, and it will work for any kind of structure that can be recursively defined with an $O(1)$ recursive initialization.

In this case, you can see that the structure is just an unordered set with a maximum, which is obviously $O(1)$ recursively definable. It is also clear that you can support Insert and DeleteMax and $O(1)$ GetMax, but not $O(\log n)$ Search. Additionally, if you think a bit you should be able to figure out how to support $O(\log n)$ MergeHeap.

---
Tags: data-structures, terminology, heaps, priority-queues
---


title: Mathematical Problem Solving

text:
# Question
Title: Mathematical Problem Solving
Will a study of the mathematical proof of a (data structure and algorithm based) problem, when posed as a proposition, highlight peculiar properties of the problem which may help in designing an optimal algorithm?

I think that proofs should yield interesting insights, and therefore can be used in designing algorithms. Since the program is expected to return a *true response* for every input, proof must be, in some way, built into the program. Is there any text I can refer to in this regard which will help in real problem solving?

# Answer
> Will a study of the mathematical proof of a problem \[..\], highlight peculiar properties of the problem which may help in designing an optimal algorithm?

Often they do. But not necessarily (unless you're a scholar of constructivism), for example when using the probabilistic method to show that a solution to said problem exists, then the proof will not help you designing any algorithm since it does not give you a construction.

> Since the program is expected to return a true response for every input, proof must be, in some way, built into the program.

That would be nice if it were the case, but often proving correctness (see formal methods) of an algorithm is rather difficult and/or a real pain. That said, there *is* such a thing as proof-carrying code which does exactly that, but the proofs are not given to you for free.
> 4 votes

---
Tags: algorithms, computability
---


# Question
Title: ML functions from polymorphic lists to polymorphic lists
I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type `'a -> 'b`. Now I've been experimenting a bit with functions of type `'a list -> 'b list`. There are some obvious simple examples:

```
let rec loop l = loop l
let return_empty l = []
let rec loop_if_not_empty = function [] -> []
                                   | l -> loop_if_not_empty l

```

What I can't figure out is how to make a function that does something other than return the empty list or loop (without using any library function). Can this be done? Is there a way to return non-empty lists?

Edit: Yes, if I have a function of type `'a -> 'b`, then I can make another one, or a function of type `'a list -> 'b list`, but what I'm wondering here is how to make the first one.

# Answer
> 6 votes
Well, something known as *parametricity* tells us that if we consider the pure subset of ML (that is, no infinite recursion, `ref` and all that weird stuff), there is no way to define a function with this type other than the one returning the empty list.

This all started with Wadler's paper “Theorems for free!”. This paper, basically, tells us two things:

1. If we consider programming languages that satisfy certain conditions, we can deduce some cool theorems just by looking at the type signature of a polymorphic function (this is called the Parametricity Theorem).
2. ML (without infinite recursion, `ref` and all that weird stuff) satisfies those conditions.

From the Parametricity Theorem we know that if we have a function `f : 'a list -> 'b list`, then for all `'a`, `'b`, `'c`, `'d` and for all functions `g : 'a -> 'c`, `h : 'b -> 'd` we have:

```
map h ∘ f = f ∘ map g

```

(Note, `f` on the left has type `'a list -> 'b list` and `f` on the right is `'c list -> 'd list`.)

We are free to choose whatever `g` we like, so let `'a = 'c` and `g = id`. Now since `map id = id` (easy to prove by induction on the definition of `map`), we have:

```
map h ∘ f = f

```

Now let `'b = 'd = bool` and `h = not`. Let's assume for some `zs : bool list` it happens that `f zs ≠ [] : bool list`. It is clear that `map not ∘ f = f` does **not** hold, because

```
(map not ∘ f) zs ≠ f zs

```

If the first element of the list on the right is `true`, then on the left the first element is `false` and vice versa!

This means, our assumption is wrong and `f zs = []`. Are we done? No.

We assumed that `'b` is `bool`. We've shown that when `f` is invoked with type `f : 'a list -> bool list` for any `'a`, `f` must always return the empty list. Can it be that when we call `f` as `f : 'a list -> unit list` it returns something different? Our intuition tells us that this is nonsense: we just can't write in pure ML a function that always returns the empty list when we want it to give us a list of booleans and might return a non-empty list otherwise! But this is not a proof.

What we want to say is that `f` is *uniform*: if it always returns the empty list for `bool list`, then it *has to* return the empty list for `unit list` and, in general, any `'a list`. This is exactly what the second point in the bullet list in the beginning of my answer is about.

The paper tells us that in ML `f` must take *related* values to *related* ones. I'm not going into details about relations, it is enough to say that lists are *related* if and only if they have equal lengths and their elements are pair-wise related (that is, `[x_1, x_2, ..., x_m]` and `[y_1, y_2, ..., y_n]` are related if and only if `m = n` and `x_1` is related to `y_1` and `x_2` is related to `y_2` and so on). And the fun part is, in our case, since `f` is polymorphic, *we* can define *any* relation on the elements of lists!

Let's pick any `'a`, `'b` and look at `f : 'a list -> 'b list`. Now look at `f : 'a list -> bool list`; we've already shown that in this case `f` always returns the empty list. We now postulate that all the elements of `'a` are related to themselves (remember, we can choose any relation we want), this implies that any `zs : 'a list` is related to itself. As we know, `f` takes related values to related ones, this means that `f zs : 'b list` is related to `f zs : bool list`, but the second list has length equal to zero, and since the first one is related to it, it is also empty.

---

For completeness, I'll mention that there is a section on impact of general recursion (possible non-termination) in the Wadler's original paper, and there is also a paper exploring free theorems in the presence of `seq`.

# Answer
> 4 votes
Let's get back to simpler objects: you cannot build an proper object of type `'a` because then it would mean this object `x` can be used wherever `'a` would fit. And that means everywhere: as an integer, an array, even a function. For example that would mean you can do things like `x+2`, `x.(1)` and `(x 5)`. Types exist *exactly* to prevent this.

This the same idea that apply with a function of type `'a -> 'b`, but there are some cases where this type can exists: when the function *never* returns an object of type `'b`: when looping or raising an exception.

This also apply to functions that return a list. If your function is of type `t -> 'b list` and that you build an object of type `t` and apply it to this function, then that means that if you successfully access an element of this list then you will access to an object that have all types. So you can't access any element of the list: the list is either empty or ... there is no list.

However the type `'a list -> 'b list` appears in usual exercises but that's only when you already have a function of type `'a -> 'b`:

```
let rec map (f : 'a -> 'b) =
  function
  | [] -> []
  | x :: xs -> f x :: map f xs

```

But you probably know this one.

```
val map : ('a -> 'b) -> 'a list -> 'b list

```

# Answer
> 2 votes
*Parametricity Theorem* from the “Theorems for Free!” paper tells us that ML terms have a very special property: if we view a term’s type as a relation on values of this type, then this term’s value will be related to itself. Here is how to view types as relations:

* A function type `'a -> 'b` corresponds to the relation defined by saying that two functions are related if they take related values to related values (assuming `'a` and `'b` correspond to some relations).
* A list type `'a list` corresponds to the relation defined by saying that two lists are related if they have the same length and their matching elements are related (assuming `'a` corresponds to some relation).
* *(Now the most interesting part.)* A polymorphic type corresponds to the relation defined by saying that two polymorphic values are related if we can choose *any* two types, *any* relation between the elements of these types, replace all instances of the type variable with this relation, and the resulting values will still be related.

Here is an example. Suppose we have a term `foo : 'a -> 'a`. The Parametricity Theorem says that `foo` is related to itself. What this means is that we can choose any two types, say, $A\_1$ and $A\_2$, choose absolutely any relation $\mathbf{A}$ between elements of this type, and if we take any $a\_1 : A\_1$ and $a\_2 : A\_2$, such that they are related according to $\mathbf{A}$, then $\operatorname{foo} a\_1$ and $\operatorname{foo} a\_2$ will also be related according to $\mathbf{A}$:

$$ a\_1 \sim\_\mathbf{A} a\_2 \Rightarrow \operatorname{foo} a\_1 \sim\_\mathbf{A} \operatorname{foo} a\_2. $$

Now if we take the relation $\mathbf{A}$ to be not an arbitrary relation, but a function $f : A\_1 \to A\_2$, the above becomes:

$$ f(a\_1) = a\_2 \Rightarrow f(\operatorname{foo} a\_1) = \operatorname{foo} a\_2, $$

or, in other words:

$$ f(\operatorname{foo} a\_1) = \operatorname{foo} (f(a\_1)), $$

which is exactly the free theorem for the `id` function: `f . id = id . f`.

---

If you perform similar steps for your function `foo : 'a list -> 'b list`, you’ll get that you can choose any two types $A\_1$ and $A\_2$, any relation $\mathbf{A}$ between their elements, any two types $B\_1$ and $B\_2$, any relation $\mathbf{B}$ between their elements, then take any two lists, first made of elements of $A\_1$, second made of elements of $A\_2$, apply your function to both lists (getting a list of $B\_1$ in the first case and a list of $B\_2$ in the second), and the results will be related, if the inputs were related.

Now we use this to prove that for any two types `A` and `B` the function `foo` returns an empty list for any input `as : A list`.

* Let $A\_1 = A\_2 = $ `A` and let $\mathbf{A}$ be the identity relation, thus any list of $A$ is trivially related to itself.
* Let $B\_1 = $ `Ø`, $B\_2 = $ `B` and $\mathbf{B}$ any relation between them (there is only one, the empty one, but it doesn’t matter).
* `as` is related to itself (as we chose the identity relation on `A`), thus `foo as : Ø list` is related to `foo as : B list`.
* We know that two lists can be related only if their lengths are equal and we also know that the first of the resulting lists must be empty, as there can be no elements of the `Ø` type.

Therefore, for any `A`, `B` and `as : A list` we have that `foo as : B list` has to be an empty list.

---
Tags: programming-languages, typing, functional-programming
---


# Question
Title: Longest-path in a graph, where the path should be 'straight'
Is there any existing work done on finding paths that are geometrically straight?

---

I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of which has a defined position in euclidean space (they're taken from a picture). Specifically, I want to find all straightish paths longer than X, but finding the longest may be simpler and basically equivalent.

Essentially, this is a path-finding problem in a non-directed, non-planar graph, where the path's destination isn't known, and the path itself must be straight, for an arbitrary and somewhat loose definition of 'straight'.

While I've found path-finding algorithms that use graphs whose vertices have defined positions, they generally work by just using those positions to give each edge a weight, after which the positions are ignored. I'm not sure that couldn't be done here, but I think it'd require a complicated edge-weight function that somehow takes into account the weights of previous edges in the current path.

---

Perhaps you could consider it a directed graph, where edges go only geometrically away from the source node/existing path - edges that double-back towards the start can't be taken. Marking them as such may be linear. Finding all complete paths (that is, starting at a source and ending at a sink) in a directed acyclic graph is polynomial. So while all the implementations I've tried so far range from 'very inaccurate' to 'quite inaccurate and also slow', I wouldn't expect the problem to be harder than polynomial.

---

---

Edit:

Because the graph is derived from an image, the lines will generally never be perfectly straight, and while straightness is usually visually obvious, my current algorithms have measured straightness by minimizing the change in angle from point to point, or by minimizing the geometrical width of the convex hull of either the entire path, or of sections of the path individually in turn. Width being measured perpendicularly to the straight-line distance between the first point in a path and the last. The problem with either of those though, is that each point has to be processed many times (I think $N^3$), and it feels less than elegant, and more like brute force.

---

The source of the problem is measuring fibers in an image, where the image looks kinda like a large game of pick-up sticks - hundreds of straight fibers, of varying lengths, cris-crossing frequently. Vertices in the graph are at endpoints, intersections, and discontinuities (i.e. potential endpoints). I'd guess that machine learning techniques, or other methods of image-processing, may be better suited for the problem, as it boils down to recognition of simple objects in an image, but the purpose of my question is more to learn about graphs, rather than just solve that problem.

# Answer
## Idea 1: Short paths are straight paths

In Euclidean space, a straight path is usually a short path.

So I would compute shortest paths between every pair of points in the graph. This can be done in $O(|V|^3)$ time with the Floyd-Warshall algorithm, which is suitable for dense graphs, or $O((|E|+|V|)|V|\log|V|)$ time by running Dijkstra's algorithm starting from each vertex in turn, which is faster for sparse graphs.

You can then evaluate each vertex pair according to whatever "straightness" criteria you like -- e.g. average/maximum angle formed or maximum perpendicular distance, balancing these against the length of the path somehow -- and choose the overall maximum.

For a quick heuristic, you could randomly subsample the points and solve the smaller subproblem. Repeat this several times to build a list of candidate (source, sink) pairs, then run Dijkstra on each candidate in the full graph to pick the overall winner.

## Idea 2: Partition edges by angle

The above should work well if it's OK for the line to be quite jagged at a small scale. But if smoothness at a small scale is important, another approach comes to mind: Partition the edges into **angle buckets** (e.g. all edges making an angle of 0-5 degrees with the horizontal, all edges making an angle of 6-10 degrees, etc., for 360/5 = 72 buckets overall). For each bucket, solve a separate subproblem that contains all vertices, but only the edges in that particular bucket. Every path in such a graph necessarily contains only edges that have very similar directions. (If you choose sufficiently fine buckets, you might find that the graph fragments into many small, line-like components, which will speed things up greatly as they can be solved independently.)

In fact it's not necessary to *partition* the edges; it's probably desirable to have some bucket overlap, so that an edge typically appears in more than one subproblem.
> 2 votes

---
Tags: algorithms, graphs, computational-geometry, approximation
---


# Question
Title: Iterative Fibonacci algorithm correctness proof, finding loop invariants
The algorithm take in an integer $n$ and outputs the $n$th number in the Fibonacci sequence ($F\_n$). The sequence starts with $F\_0$. I am trying to prove the correctness assuming valid input:

```
int Fib(int n) {
    int i = 0;
    int j = 1;
    int k = 1;
    int m = n;
    while(m >= 3){
        m = m-3;
        i = j +k;
        j = i+k;
        k = i + j;
    }
    if(m == 0 ){
        return i;
    }
    else{
        if(m == 1){
            return j;
        }
        else{
            return k;
        }
    }
}

```

For a reminder, a loop invariant is a claim which holds every time just before the loop condition is checked. It holds even when the loop condition is false. I've established and proven one loop invariant that $m \geq 0$. This helps me show that the algorithm terminates since when the loop exits since $m$ is either 0, 1, or 2. However, **I'm stuck on finding another loop invariant that would help me show that the algorithm produces the correct Fibonacci number**.

One pattern I found is that the result of returning i, j, or k is due to the result of the initial value of $m$ $\\% 3$. Depending on the remainder, either i, j, or k is returned. I tried expanding this idea further but led myself to a dead end. I'm thinking I need to find some way to express $F\_n = F\_{n-1} + F\_{n-2}$ in terms of i, j and k in order to prove that the program outputs correctly. Am I on the right track with remainders or is there something I'm missing?

# Answer
> 2 votes
Assume n=0, n=1 or n=2. For your program to be correct, you need i = Fib(0), j = Fib(1) and k = Fib(2). Now assume 3 ≤ n \< 6. For your program to be correct, you need i = Fib(3), j = Fib(4) and k = Fib(5) after the first iteration. Check that.

Let d = n-m. Then before the first iteration, d = 0 and after the first iteration, d = 3. With what I wrote above I think you need i = Fib(d), j = Fib(d+1), k = Fib(d+2) before each iteration. Now all you need is put everything together.

Of course you could compile the code, use a debugger, and check which values are actually calculated let's say if n = 10 (or do it by hand). It would help a lot if you actually understood what the program does.

# Answer
> 2 votes
It kind of depends on what formalism you want to use for this proof.. But the core-idea which holds for pretty much any such formalism is the following:

Suppose you establish some invariant $I$ you will want to be able to make the following conclusion

$$ m \< 3 \land I \implies X $$

where $X$ tells you that the values $i,j$ and $k$ have the right values.

You are on the right track with the argument $I = I' \cup \\{ m = n \mod 3 \\}$, however $I' = \\{m \geq 0\\}$ is *way too weak* to establish that $\texttt{Fib}(n)$ returns the $n$th Fibonacci number.

---

Try the following:

* Find some existential (for some value, eg. $z$) claim about the relationship of $n$ and $m$ (seems like you already did so)
* Now use that value $z$ to show $\\{ k = F\_z, i = F\_{z-2}, j = F\_{z-1} \\}$1

I hope this will help you!

1: Depends on your claim about $m$ and $n$, could also be shifted $\\{ k = F\_{z+2}, i = F\_z, j = F\_{z+1} \\}$ as in gnasher729's answer which is simpler. The core idea is the same.

---
Tags: algorithms, correctness-proof, induction, loop-invariants
---


# Question
Title: How many neurons is needed for UAT to hold?
The universal approximation theorem states that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of Rn, under mild assumptions on the activation function.

How many neurons is needed? For a function in 3 variables and one output. And how many adjustable parameters does that give in the neural network?

# Answer
> 1 votes
There is not a particular number. You have to decide how much you want to approximate your function.

UAT, in informal language, means that neural network can approximate any given function f when given appropriate parameters (which are to be found experimentally; their learnability isn't a question here!).

If you have a function of 3 variables, then a neural network with 20 neurons may approximate it far better than one with the 10 neurons. It is possible that after a certain number of neurons, the difference between the outputs, i.e., (F - f) becomes very less.

I answer this question following Occam's razor, thus not mentioning any un-necessary terms. Please ask, if you have any additional or specific questions in it.

---
Tags: neural-networks
---


# Question
Title: What does it mean " The outer level page table need not be page aligned?
The question is in context to multilevel page table. I was trying to solve numerical on multi-level paging and noticed that page size might not be same at all levels. I came across the point "Outer level page tables need not be page aligned to inner page tables".

Question 1: Does this mean that outer level page tables need not have same page size as inner page tables?

Question 2: If the sizes at different levels of paging are different, then will an outer page table's entry have to contain the exact frame address, i.e., frame number + offset, because page sizes are different across all levels?

# Answer
> 2 votes
Having different subtable sizes for different levels of a multilevel page table just means that a different number of bits from the virtual address will be used. The size of each level's subtable is independent of the sizes of subtables in other levels. (Yes, "outer level page tables need not have same page size as inner page table".)

Each subtable would be aligned to its size and pointers to that table in earlier levels could exploit this to elide zero bits in the address. The index would still be provided by the selection of virtual address bits. (No, outer page tables entry will **not** have to contain frame number + offset.)

For example, with a 47-bit virtual address space with a 50-bit physical address space (8-byte PTEs), an 8 KiB subtable with entries pointing to a 16 KiB subtable whose entries point to a 64 KiB subtable that points to 8 KiB pages:

```
root 8KiB subtable entry physical address
   PA[49:13] = root_pointer[39:0]
   PA[12:03] = VA[46:37] // 8 KiB subtable index
   PA[02:00] = 000       // PTE is 8-byte aligned
16 KiB subtable entry physical address
   PA[49:14] = pointer_to_16KiB_subtable[38:0]
   PA[13:03] = VA[36:26] // 16 KiB subtable index
   PA[02:00] = 000
64 KiB subtable entry physical address
   PA[49:16] = pointer_to_64KiB_subtable[36:0]
   PA[15:03] = VA[25:13] // 64 KiB subtable index
   PA[02:00] = 000
page address
   PA[49:13] = PTE_in_64KiB_subtable[36:0]
   PA[12:00] = 0_0000_0000_0000  // 8 KiB aligned page

```

The above example assumes a fixed size associated with each level. With variable sizes, the size of the targeted subtable would have to be included with its pointer.

The subtable size could be determined by a subtable size number such that three bits would support eight different subtable sizes or using a single extra bit with the size boundary marked by the first set bit starting from the least significant bit (e.g., aa...aa\_1000 would indicate a subtable eight times larger (three bits before the set bit) than the smallest size supported). The former allows additional alignment bits of larger subtables to be used to extend the physical address space or provide more metadata; the latter saves bits (two in the example) that can be used for metadata or larger physical addresses even for the smallest subtables. Supported subtable sizes could also be dependent on the level of the subtable or even the sizes (or other metadata provided) in previous levels, though that seems inappropriately complex.

---
Tags: operating-systems, virtual-memory, paging
---


# Question
Title: Time complexity of Dijkstra's algorithm for sparse graph
I'm not sure I understand the answer to this question:

> **Question 9.**
>
> What is the running time of Dijkstra's algorithm in a graph that is sufficently sparse - in particular, $E=o(V^2/\log V)$, where $V$ is the number of vertices and $E$ the number of edges. Assume that we are implementing the min-priority queue with a binary min-heap. Choose the anwser the that gives the tightest correct bound.
>
> 1. $O(V^2)$
> 2. $O(V^2+E)$
> 3. $O(E^2)$
> 4. $O((V+E)\log V)$
> 5. $O(V\log V)$
>
> Answer: 4 $O((V+E)\log V)$

As I understand it, the algorithm runs in $O((E+V) \log(V))$ with binary heap. Thus when, $E = V^2/\log(V)$, shouldn't the overall time complexity be $O(V^2)$?

# Answer
Discrete Lizard's answer explains various aspects of the question.

Here is an explicit calculation when $E=o(V^2/\log V)$.

$$\lim\_{V\to\infty}\frac{(E+V)\log V}{V^2}=\lim\_{V\to\infty}\frac{E}{\dfrac{V^2}{\log V}}+\lim\_{V\to\infty}\frac{V\log V}{V^2}=0+0=0$$

That means $O((E+V)\log V)\subsetneq O(V^2)$. So $O((E+V)\log V)$ is a tighter bound than $O(V^2)$ when $E=o(V^2/\log V)$.
> 2 votes

# Answer
First of all, note that the question does not claim $E=V^2/\log V$, but $E=o(V^2/\log V)$, which is different, see for example this table on Wikipedia.

The running time of Dijkstra with a binary heap is indeed $O((E+V)\log V)$. The question basically asks whether we can find a tighter upper bound if we know that the graph is sparse, meaning there are relatively few edges.

The answer is no. The main point is that as we know that $E=o(V^2/\log V)$, we certainly *can* 'fill in' the upper bound we know for $E$ and see that $O(V^2)$ is now an upper bound for the running time. However, if you do that, then you are replacing a 'known' quantity by an upper bound, which means your upper bound can only become less tight. (You can verify that the bound is chosen so that this happens here)

Another way to look at it is that 'filling in' $E$ means you are throwing away the information on the actual number of edges (which is exactly $E$) and replace it by an estimate for this number. This makes your total estimate less accurate.
> 1 votes

---
Tags: algorithms, runtime-analysis, shortest-path
---


# Question
Title: Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue
we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete\_min, O(log |V |) for insert/ decrease\_key, so the overall run time is O((|V|+|E|)log|V|).

Now let's modify the Dijkstra to stop once it reaches T (Destination) from S(Start). The given performance is:

Understand that we don't need to explore the full G in the modified Dijkstra run. Can someone explain why it is the diamond shape(the 45 degree rotate of a perfect square)?

What does it means with the **radios** of |m|+|n|, (typo of radius ?)

What is m and n in this case? (m means vertices? n means edges?) seems to me that $(|m|+|n|)^2$ is half of the vertices and edges visited，which is half of the Diamond/Square. Then not sure how is it is computed.

added new pic for the additional questions

# Answer
In the example, we can assume the start cell $s$ is the origin in a plane consisting of square cells with Descarte coordinates. That is, $s$ is $(0,0)$. The coordinate of destination cell, $t$ is $(m,n)$. The distance of any two cells is given by the taxicab geometry. That is, the distance between cells $(p\_1,p\_2)$ and $(q\_1,q\_2)$ is $$d((p\_1,q\_2),(q\_1,q\_2))=|p\_1-p\_2|+|q\_1-q\_1|$$ In particular, $d(s,t)=|m|+|n|$.

At the last step of running Dijkstra's algorithm with source cell $s$ when we visit cell $t$, all cells whose distance to $s$ is smaller than $d(s,t)$ must have been visited. Some of the cells whose distance to $s$ is $d(s,t)$ may have also been visited. If you color all cells that are no more than $d(s,t)$ away from $s$, you will get a diamond shape whose boundary cells $(p,q)$ are given by the following equations.

$$ \begin{align} p+q = d(s,t) &\text{ where }p\ge0, q\ge0. \text{ This is the top right segment.}\\ p-q = d(s,t) &\text{ where }p\ge0, q\le0. \text{ This is the bottom right segment.}\\ -p+q = d(s,t) &\text{ where }p\le0, q\ge0. \text{ This is the top left segment.}\\ -p-q = d(s,t) &\text{ where }p\le0, q\le0. \text{ This is the bottom left segment.}\\ \end{align}$$

That diameter shape is, in fact, a circular disk with center $(0,0)$ and radius $|m|+|n|$ in the taxicab geometry. Yes, as you pointed out, "radios" should be "radius".

How many cells are there in the diamond shape? The diamond shape is actually a square the length of whose diagonals is $2(|m|+|n|)$. So its area is $(2(|m|+|n|))^2/2=2(|m|+|n|)^2$, which is about the number of cells in the it asymptotically.

---

**Exercise.** The exact number of cells in a disk with radius $r$ in the taxicab geometry is $2r^2+2r+1$. In particular, there are 13 cells in a disk with radius 2.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, asymptotics, performance
---


# Question
Title: Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?
As an example, here are all possible trees for the case $k=3$:  On each node written is its arity (= the number of children).

While this should be solvable by dynamic programming, I think there was a combinatoric result on this (either exact or a rather fine grained upper bound). Does anybody know it?

---

Edit:

The size of the tree is the number of nodes it has, so the biggest tree would be the one with the maximum number of nodes.

# Answer
> 4 votes
Let $B(n)$ be the size of the largest tree, where the arities of each path from root to leaf add up to $n$.

If the root of such a tree has arity $k$, then the paths for each of the $k$ subtrees must add up to $n-k$. As the subtrees must be optimal, the tree has size $1+k\cdot B(n-k)$.

A formula for $B(n)$ just maximizes that expression over $k$, using the previous values $B(n-1), B(n-2),\dots$.

I tried to do this by hand, and found (with the help of @Sudix, thanks) $1,2,3,5,7,11,16,23,34,\dots$. This seems to be A239288 in Sloanes Online Encyclopedia of Integer Sequences. The recursion given there is similar, but not exactly the same.

The explanation of the sequence there is: "Maximal sum of x0 + x0\*x1 + ... + x0\*x1\*...\*xk over all compositions x0 + ... + xk = n". That indeed is the same sequence: if the sequence of arities along the path from the root is x0, x1,..., xk these should sum to n, and the number of nodes indeed is the given formula.

Another remark at Sloane is interesting: "For n \>= 8 the solution becomes cyclic: a(3n + k) = 3 + 3a(3n - 3 + k)". This seems to suggest that for values larger than 24 the root of the tree always has three children.

---
Tags: trees, combinatorics
---


# Question
Title: Merging two splay trees whose ranges may overlap in $O(\log N)$
I have two splay trees, $A$ and $B$.

When every element in $A$ is smaller than every element in $B$, we can merge them in $O(\log N)$.

My question is; when all elements of $A$ are not necessarily smaller than all elements of $B$, how can we still merge $A$ and $B$ in $O(\log N)$?

What I have already tried:

Splay $A$'s largest element, splay $B$'s smallest element. The root $R\_A$ of $A$ doesn't have a right child anymore, and the root $R\_B$ of $B$ doesn't have a left child anymore. Compare $R\_A$ and $R\_B$. If $R\_B$ is bigger than $R\_A$, make $R\_B$ the right child of $R\_A$, which fails when $R\_A$ is larger than $R\_B$.

# Answer
No, you cannot merge two splay trees whose ranges may overlap in $O(\log N)$, where $N$ is the total number of nodes. You may have to move at least $\Theta(N)$ nodes in general or average situations.

It contains no information at all when we know "whose ranges may overlap". The ranges of any two splay trees may overlap.

It contains no information at all when we know all elements of A are not necessarily smaller than all elements of B. That is the same as all elements of A are not necessarily larger than all elements of B.
> 1 votes

---
Tags: splay-trees
---


title: Church numerals without functions

text:
# Question
Title: Church numerals without functions
This is really a second part to my first question, but I felt that this was different enough from the first part that it merited its own question.

So, using Church numerals, we define

$3 = {\lambda} f. {\lambda}x.f(f(f(x)))$,

and

$4 = {\lambda} f. {\lambda}x.f(f(f(f(x))))$.

We can then add with an expression like

$3\ g\ (4\ g\ z)$

And this reduces to:

$(g (g (g (g (g (g (g\ z)))))))$.

But, of course, this is not how we would define $7$ in the scheme above. $7$ would be

${\lambda}g.{\lambda}z.(g (g (g (g (g (g (g\ z)))))))$.

Why is it still legitimate to call the application $3\ g\ (4\ g\ z)$ "7" when we can no longer perform functions with it?

# Answer
This is just a shorthand, leaving off some things that aren't really needed to understand the concepts. If you want your $7$ to be written as a function again, all you need are a couple more implicit lambdas. Here's how I'd write the Church addition with those lambdas in place:

$$3 + 4 = \lambda g . \lambda z . 3 g (4 g z) = \lambda g . \lambda z . 7 g z$$

But we also know that:

$$\lambda k . f k = f$$

Therefore:

$$\lambda g . \lambda z . 7 g z = 7$$
> 4 votes

---
Tags: lambda-calculus, church-numerals
---


# Question
Title: If a deterministic finite automaton recognizes a language, must that language contain every accepting input?
May a DFA recognize a language which is a proper subset of the set of all accepted inputs?

For instance, if there is a DFA which decides if an input $W$ has $w\_0 = w\_n$, can it recognize a language $L$ where there is some $\sigma \in \Sigma$ that does not exist in any element of $L$?

# Answer
### No.

The language (only one!) recognized by a DFA is the set of *all* inputs it accepts.

The definition of a DFA also includes its alphabet, so you have to consider that an intrinsic part of the DFA. If you change the alphabet at all, you now have a new and different DFA, which potentially recognizes a different language.
> 3 votes

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


# Question
Title: How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
> Prove that if $L, G$ are regular languages over $\\{a,b,c\\}$ then $H=\\{w\in L|\exists x\in G: |x|=2\cdot |w|\\}$ is a context-free language?

I think this could be a good exercise and the conditions are very simple.

Because $L,G$ are regular they have corresponding DFA's: $$ L=\bigg(\sum,Q\_1, q\_{01,\delta\_1, F\_1}\bigg)\\ G=\bigg(\sum,Q\_2, q\_{02,\delta\_2, F\_2}\bigg) $$

Then we can build a pushdown automaton $M$ for $H$:

$$ M=\bigg(Q\_1\times Q\_2\times \\{0,1,2\\}\cup \\{q\_f\\}, \sum,\\{A, S\\},\delta, (q\_i,q\_j,0),S,F\_1\times F\_2\times\\{2\\}\bigg),\quad q\_i\in Q\_1, q\_j\in Q\_2, q\_f\in F\_1\times F\_2\times\\{2\\}, S \text{ is the starting symbol on the stack} $$

$\delta$ can be defined as follows: first we read $w\in L$ and add two stack symbols for each letter read. Also we put the special symbol $B$ which we will need later: $$ \delta((q\_i,q\_j,0),\sigma, S)=((\delta\_1(q\_i, \sigma), q\_j, 0), AABS)\\ \delta((q\_i,q\_j,0),\sigma, A)=((\delta\_1(q\_i, \sigma), q\_j, 0), AAA) $$ Then we guess the start of $x\in G$: $$ ((q\_i,q\_j,0),\epsilon, A)=(q\_i, q\_j, 1), A) $$ Then we delete symbols off the stack one by one: $$ \delta((q\_i,q\_j,1),\sigma, A)=(q\_i,(\delta\_2(q\_j, \sigma), 1), \epsilon) $$ If there're no more characters to read from $x\in G$ then we should see a $B$ on the stack, which means that $|x|=2\cdot |w|$ and we're in accepting state: $$ ((q\_i,q\_j,1),\epsilon, B)=(q\_i, q\_j, 2), \epsilon) $$ Because a PDA exists for $H$ then $H$ is context-free.

---

Is my proof good, especially the $\delta$ function?

# Answer
> 4 votes
Let $\sigma$ be the substitution $\sigma(a) = \sigma(b) = \sigma(c) = \\{a,b,c\\}$, and let $h$ be the homomorphism $h(\sigma) = \sigma\sigma$.

Your language is just $$ h^{-1}(\sigma(G)) \cap L. $$ In other words, your language is regular.

You can also see this using a product automaton. Given automata for $L,G$, consider an NFA on $Q\_L \times Q\_G$, with starting state $(q\_{0L},q\_{0G})$, accepting states $F\_L \times F\_G$, and transition function $$ \delta((q\_L,q\_G),\sigma) = \\{ (\delta\_L(q\_L,\sigma),\delta\_G(q\_G,\sigma \tau)) : \tau \in \Sigma \\}. $$

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


# Question
Title: Is there a systematic way to know when to alpha-transform free variables?
So, using Church numerals, we define

$3 = {\lambda} f. {\lambda}x.f(f(f(x)))$,

and

$4 = {\lambda} f. {\lambda}x.f(f(f(f(x))))$.

We can then add with an expression like

$3\ g\ (4\ g\ z)$

And this reduces to:

$(g (g (g (g (g (g (g\ z)))))))$

... but *why?*

$g$ is a free variable in each expression, and my understanding is that you must ${\alpha}$-convert free standing variables in unrelated expressions. Shouldn't we instead end up with something like

$(g (g (g (g\_2 (g\_2 (g\_2 (g\_2\ z)))))))$?

# Answer
> 5 votes
The answer here is the same as in the other question: one thing is missing here!

Your addition result should be:

$$3 + 4 = \lambda g . \lambda z . 3 g (4 g z) = \lambda g . \lambda z . 7 g z$$

Note that $g$ is now a lambda parameter, not a free variable! So now if you want to apply this to something, it'll get substituted in the same everywhere:

$$7 q r = (\lambda g . \lambda z . 7 g z) q r = q q q q q q q r$$

# Answer
> 4 votes
Free variables never get $\alpha$-converted, only bound variables can.

In the term $(\lambda x.\ xy)$ we can rename the bound variable $x$ to any other variable (except $y$, since that would cause a name clash). For instance, we can obtain $(\lambda z.\ zy)$. Instead, we can never rename $y$, since that is free, not being under any $\lambda y$.

By contrast, in $(\lambda y.\ \lambda x.\ xy)$ we can $\alpha$-convert both variables to any other pair of (distinct) variables. This is because now they are both bound.

In the OP's example, $g$ is free, so no renaming is possible. At most, we can $\alpha$-convert $f$ and $x$, but not $g$.

---
Tags: lambda-calculus, variable-binding, church-numerals
---


title: address spaces of changing processes

text:
# Question
Title: address spaces of changing processes
I read that the mapping for user-space processes is changed after each process switch. By mapping I mean the translation from virtual addresses to "real" memory address. I thought that processes are loaded into RAM and are held there (that's what the RAM is for). So the addresses in "real" memory addresses shouldn't change too much over time, because the process is held in RAM.

Where am I mistaken?

# Answer
> 0 votes
Processes don’t use real RAM addresses. If they did, virtual memory couldn’t possibly work.

If the data is actually in RAM, then the data of process A at A’s location 1000 is not the same and therefore not stored in the same place as the data of process B at B’s location 1000

So the mapping must change when we switch from process A to process B. Address 1000 must be mapped to different addresses in RAM or not in RAM at all.

And processes are not loaded into RAM, they are loaded into address space, that is a mapping between address space and RAM or virtual memory is set up. This allows having processes larger than RAM and allows switching between processes with large amounts of data quickly.

---
Tags: operating-systems, virtual-memory
---


# Question
Title: Calculating the average waiting time of tasks
I have proposed a load balancing algorithm for a group of homogeneous processing devices and now I want to measure **the average waiting time** to see if my algorithm is successful in decreasing the waiting time. I have considered number of tasks on each device as the load of that device.

Imagine at first there are 54 tasks that is distributed like this between devices:

> device1 = 32
>
> device2 = 20
>
> device3 = 2

And after load balancing **15 tasks are transferred from device1 to device3** and these values change to:

> device1 = 17
>
> device2 = 20
>
> device3 = 17

Now I want to calculate and compare average waiting time before and after the load balancing, but I'm confused about which tasks to consider.

Should I consider all 54 tasks and measure the waiting time of all these 54 tasks

Or

should I only consider 15 tasks that were transferred and calculate the waiting time of these 15 tasks before and after load balancing?

# Answer
> 0 votes
From the two options, the first is the (only) reasonable approach. The second one is absolutely useless; details follow:

1. If you are trying to **minimize** the waiting time of the tasks that were shifted, then the best algorithm simply reschedules *no tasks at all*. The total time of transferred tasks is zero and, thus, optimal. Even if you require at least one task to be transferred, the best algorithm then simply picks the one with the least running time and transfers it to the least loaded queue. In both cases it could hardly be said the algorithm does something useful.
2. If you are trying to **maximize** the waiting time of the tasks which were rescheduled, then consider the algorithm which permutates *all* tasks between the devices. This naturally maximizes said measure and, again, hardly qualifies as a sensible load balancing algorithm.

---
Tags: algorithm-analysis
---


# Question
Title: efficiently find connected components in undirected graph considering transitive equivalence
I have a set of nodes and a function `foo(u,v)` that can determine whether two nodes are equal. By "equal" I mean transitive equivalence: `If 1==2 and 2==3 then 1==3` and also: `If 1==2 and 1!=4 then 2!=4`

When given a set of nodes I can find all **connected components** in the graph by passing **every possible combination** of nodes to `foo(u,v)` function and building the needed edges. Like this:

```
import networkx as nx
import itertools
from matplotlib import pyplot as plt

EQUAL_EDGES = {(1, 2), (1, 3), (4, 5)}

def foo(u, v):
    # this function is simplified, in reality it will do a complex calculation to determine whether nodes are equal.
    return (u, v) in EQUAL_EDGES

def main():
    g = nx.Graph()
    g.add_nodes_from(range(1, 5 + 1))
    for u, v in itertools.combinations(g.nodes, 2):
        are_equal = foo(u, v)
        print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')
        if are_equal:
            g.add_edge(u, v)

    conn_comps = nx.connected_components(g)
    nx.draw(g, with_labels=True)
    plt.show()
    return conn_comps

if __name__ == '__main__':
    main()

```

the problem with this approach is that I get many redundant checks that I would like to avoid:

```
1==2  # ok
1==3  # ok
1!=4  # ok
1!=5  # ok
2!=3  # redundant check, if 1==2 and 1==3 then 2==3
2!=4  # redundant check, if 1!=4 and 1==2 then 2!=4
2!=5  # redundant check, if 1!=5 and 1==2 then 2!=5
3!=4  # redundant check, if 1!=4 and 1==3 then 3!=4
3!=5  # redundant check, if 1!=5 and 1==3 then 3!=5
4==5  # ok

```

I want to avoid running in O(n^2) time complexity. What is the correct way (or maybe an existing function in any python library) to efficiently find all connected components by a custom function?

# Answer
> 1 votes
Using depth-first search, compute the connected components, by constructing a mapping that maps each node in a connected component to the first node you visited in that component. This is linear in the number of nodes and edges. Preserve that mapping. Two nodes are equivalent if and only if they map to the same node.

---
Tags: algorithms, graphs
---


# Question
Title: Complexity of Estrin polynomial evaluation
The Estrin model for polynomial of degree $n$ is well known. But the reading of the Knuth (vol 2) or the original's paper Estrin do not help (or I miss it). I am not able to determine the complexity of the algorithm for the number of multiplication. The main equation is:

$$ \begin{align} c\_i^{(0)} &= a\_i + x\_0 a\_{i+1}, \\ c\_i^{(n)} &= c\_i^{(n-1)} + x\_0^{2^n} c\_{i+2^n}^{(n-1)}, \\ P(x\_0) &= c\_0^{(n)}. \end{align} $$

and it leads for a polynomial of degree 10 to

$$ \begin{align} P(x\_0) &= a\_0 + a\_1 x\_0 \\ &+ x\_0^2(a\_2 + a\_3 x\_0) \\ &+ x\_0^4(a\_4 + a\_5 x\_0 + x\_0^2 (a\_6 + a\_7x\_0)) \\ &+ x\_0^8(a\_8 + a\_9 x\_0 + x\_0^2 a\_{10}) \\ \end{align} $$

For the additions: $n$

For the multiplication, it could be $n + \lfloor \log\_2 n \rfloor$.

Can somebody confirm?

Best,

++t

# Answer
> 2 votes
The question is not particularly clear, but if I'm correct to assume that you're asking about Estrin's scheme for polynomial evaluation then Wikipedia confirms that it uses $n + \lfloor \lg n \rfloor$ multiplications.

---
Tags: algorithm-analysis
---


# Question
Title: $f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$
I'm trying to prove that for arbitrary $c \> 0$,

$f(n) = o(n^c) \rightarrow \exists \epsilon \> 0 \ s.t. f(n) = O(n^{c-\epsilon})$

Intuitively, this seems to be true to me (little-o implies some gap "between" $f(n)$ and $n^c$ that we can formally express as $\epsilon$). However, I'm having some trouble formalising this argument.

What I've done so far:

$f(n) = o(n^c) \rightarrow \exists c\_0, n\_0 \> 0 \ s.t. \forall n \geq n\_0, 0 \leq f(n) \< c\_0 n^c$

Suppose (for a contradiction) that no such $\epsilon$ fulfilling the above condition exists.

Then we have

$\forall \epsilon \> 0, \exists n \geq n\_0 \ s.t. f(n) \geq c\_0 n^{c-\epsilon}$

I'm not sure how to proceed from here.

# Answer
This is false. Consider for example $$ f(n) = \frac{n^c}{\log n}. $$
> 3 votes

# Answer
Yuval's counterexample $f(n)=\dfrac{n^c}{\log n}$ shows that there may not exist $\epsilon \> 0$ such that $f(n) = O(n^{c-\epsilon})$ although $f(n) = o(n^c)$.

In fact, there is a general proposition.

---

(**Gap between $o$ and $O$**). Let $f\_\epsilon(n)$ be a nondecreasing positive function on $\Bbb N$ parameterized by $\epsilon\ge0$ such that $f\_{\epsilon\_1}(n)\ge f\_{\epsilon\_2}(n)$ and $f\_{\epsilon\_2}(n)=o(f\_{\epsilon\_1}(n))$ if $\epsilon\_1\<\epsilon\_2$. In plain words, $f\_\epsilon(n)$ becomes bigger when $\epsilon$ becomes smaller. Then there exists a function $f(n)$ such that $f(n)=o(f\_0(n))$ and $f(n)\not=O(f\_\beta(n))$ for any $\beta\>0$.

Proof. Let $k\>0$ be an integer. Since $f\_{\frac1k}(n)=o(f\_{\frac1{k+1}}(n))$ and $f\_{\frac1k}(n)=o(f\_0(n))$, there exists constant $c\_k\>0$ such that $f\_{\frac1{k}}(n)\le \frac1k(f\_{\frac1{k+1}}(n))$ and $f\_{\frac1{k}}(n)\le \frac1k(f\_0(n))$ if $n\>c\_k$. We can assume $c\_k\lt c\_{k+1}$; otherwise, we can replace $c\_{k+1}$ by $\max(c\_k+1, c\_{k+1})$ recursively.

Let $f(n)$ be defined as the following. $$f(n) = f\_{\frac1k}(n) \text{ when }c\_k\le n\lt c\_{k+1}.$$

We can verify that $f(n)=o(f\_0(n))$ and $f(n)\not=O(f\_\epsilon(n))$ for any $\epsilon\>0$.

---

Here are a few related exercises.

**Exercise 1.** Show that $\log n=o(n^\epsilon)$ for any $\epsilon \>0$.

**Exercise 2.** Show that $n=o(e^{\epsilon n})$ for any $\epsilon \>0$.

**Exercise 3.** Show that $n=o(e^{\epsilon n^c})$ for any $\epsilon \>0$ and $c\gt 0$.
> 1 votes

---
Tags: asymptotics, master-theorem
---


# Question
Title: Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem
I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the element, while I have implemented it using a recursive approach. Which approach is better in terms of space complexity, and scalability for large arrays?

```
//Quick union method for Union-find algorithm. Lazy approach

import java.util.Scanner;

public class QuickUnionUF {

    private int [] id;
    public QuickUnionUF(int N)
    {
        id= new int[N];
        for(int i=0; i<id.length;++i)
        {
            id[i]=i;
        }
    }

    public int root(int p)
    {
        if(id[p]==p) return p;
        else return(root(id[p]));
    }

    public boolean isConnected(int p, int q)
    {
        return (root(p)==root(q));
    }

    public void union(int p, int q){
        int proot= root(p);
        int qroot= root(q);

        id[proot]= qroot;
    }

}

```

For the root function, the professor has used -

```
public int root(int p) {
        while (p != id[p])
            p = id[p];
        return p;
    }

```

https://algs4.cs.princeton.edu/15uf/

# Answer
The time complexity for both versions is exactly the same. It is linear in terms of the distance between $p$ and the $root$.

Space complexity is a little different. It's easy to see that the iterative version will use constant space. The recursive function will use linear space on paper (each recursive call must store some information about the current function call, for instance in a call stack via stack pointer).

This might give problems, if the distance between $p$ and $root$ is very long. Image a tree with $id\[0\] = 0$ and $id\[p\] = p - 1$ for $p \> 0$. Then finding the root for a large element $p$ might exceed the allocated stack and crash the program.

However in practice the situation might look a bit different. Depending on the programming language, the compiler/interpreter, configuration this linear space can be optimized to constant space. The concept that allows such an optimization is called **tail recursion**. E.g. `gcc -O3` will generate exactly the same assembler code for both versions: example. But be careful, not all languages, compiler / interpreter have these optimizations implemented.
> 1 votes

---
Tags: algorithms, algorithm-analysis, space-complexity, union-find
---


# Question
Title: Variant of the "Stable Roommates Problem" when room has not 2 but "n" mates
I'm looking at the name of a variant of the **Stable Roommates Problem**, when the **rooms have more than 2 mates**, ie for example 6 to 8. Does this problem has a specific name? A well-known algorithm?

*To summarize, the problem is the following*: Given a set of $n$ people, and a symetric $n\times n$ affinity matrix between each person, find an optimal disjoint set partition of the people into $m$ groups of a given size, maximizing the global "affinity score" (the sum of each pair affinity in each group).

**Why this question?** I'm organizing a wedding ceremony with around 60 people, grouping people into tables of 6 to 8. Each person pair has an affinity weight, ranging from $-\infty$ (they can't stand each other) to $+\infty$ (they better be together).

This question is somehow related, but unfortunatly does not have any answer.

# Answer
The stable roommates problem is to find a perfect matching in a non bipartite graph which is "stable". "Perfect" means that every one is assigned to a pair. "Stable" means that it does not exist 2 persons which would prefer to be together instead of their assignement. Note that the stable roommates may have no solution.

Now about your problem, the point is to define the "stable" statement on groups of 6 or 8. And as you said, you want to maximize the global affinity score which is quite different from looking for a stable situation.

Globally your problem is a "graph partition" which is NP-complete, and there is no "efficient" way to find a solution better than try all combinations. Some heuristic algorithms can provide very good results nevertheless.
> 1 votes

---
Tags: algorithms, sets, clustering
---


# Question
Title: Are the following Big Oh Notations equivalent?
In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent.
$\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$

$\mathcal{O}((log(n))^{-1})$ can be rewritten as
$\mathcal{O}(1/(log(n)))$ which is
$\mathcal{O}(1)/ \mathcal{O}(log(n))$ . This can be simplified to
$1/ \mathcal{O}(log(n))$
which is the same as the RHS. Would this be a possible solution? Any mistakes that are pointed are welcome.

# Answer
> 2 votes
This kind of thing just doesn't work. For example, one of your intermediate terms is $O(1)/O(\log n)$. However any function $f$ can be written as $g/h$ where $g=O(1)$ and $h=O(\log n)$. If $f=O(1)$, then let $g=f$ and $h=1$. If $f=\Omega(1)$, then let $g=1$ and $h=1/f$.

For a more formal treatment, try to rewrite each of your statements that involve big-$O$ in terms of "There are constants $k$ and $n\_0$ such that, for all $n\geq n\_0$, $f(n)\leq k\\,g(n)$." You'll probably find that it's not even clear what these formal statements should be and that, if you manage to figure that out, then some of the formal statements will be false.

The underlying point you've overlooked is that big-$O$ provides upper bounds but, if you have a quotient $a/b$ then upper-bounding that quotient requires upper-bounding $a$ and *lower*-bounding $b$. Big-$O$ can't express that lower bound.

---
Tags: asymptotics, landau-notation, upper-bound
---


# Question
Title: Constructing a PDA with an unequal number of a/b
I'm looking at this pdf for problems: http://www.public.asu.edu/~ccolbou/src/355hw5solf10.pdf

I found question 3g to construct a pushdown automata for the following:

{$ {a^i b^j}$ | ${i \neq j}$}

The solution they provided is below:

The issue is, when I use JFLAP to test out, I get `aabb` to pass - when it should just be `aabbb`, `aaabb`, etc.

I looked around, and found another solution that also failed:

Can someone explain to me why these fail on JFLAP and if they are right or wrong? The PDA I'm looking for can accept even if there are objects on the stack. Perhaps these two rely on the fact that acceptance is only reached if there is nothing on the stack?

# Answer
> 1 votes
The intuition is push the number of $a$'s then pop while reading $b$'s. The result should be non-zero: either there are still items on the stack (which we can check), or the stack has been emptied before the end of the string.

There is a problem with instructions like "$b/\varepsilon/\varepsilon$". This instruction means "read $b$ and do not push nor pop". The middle $\varepsilon$ is misleading. It does **not** mean that the stack is empty. It just means the PDA does not look at it.

The solution is to start by pushing a nice bottom-of-stack symbol $Z$ at the start of the computation. When we see a $Z$ we know the bottom has been reached.

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


# Question
Title: How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?
> Prove that if $L$ is regular over $\Sigma=\\{0,1,2\\}$ then the following language over $\\{0,1,2,\\$\\}$ is also regular: $$ G=\\{\\$x\\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } 01 \text{ with }\\$\\$ \\} $$ For example, if $10112\in L$ then $\\$1\\$\\$12\\$\in G$.

I think this can be solved using closure properties of regular languages.

1) Let $H=\\$L\\$$. $H$ is also regular because it's concatenation.

2) Let $h:\Sigma\to \Sigma^\*$ be defined as follows: $$ h(\\$)=h(0)=h(1)=\\$ $$ Then: $$ G=h^{-1}(H)\cap \\$(\Sigma^\*\\$\\$\Sigma^\*)^+\\$ $$ which is regular because $h^{-1}$, intersection and regular expressions are closed in regular languages.

---

I wonder if my proof using closure is correct or automaton should be built in this case? In addition **if** I managed to think of a regular expression to describe $G$ then this alone would've proved that $G$ is regular?

# Answer
> 1 votes
Unfortunately, your argument breaks down at step 2). For example, let $L=\\{01\\}$. Then
$G =\\{\\$\\$\\$\\$\\}.$
$H=\\{\\$01\\$\\}$.
$h^{-1}(H)=\emptyset$ since every word in the range of $h$ contains neither 0 or 1.
$h^{-1}(H)\cap \\$(\Sigma^\*\\$\\$\Sigma^\*)^+\\$=\emptyset.$
However, $G$ is not empty.

---

> If I managed to think of a regular expression to describe G then would this alone have proved that G is regular?

Of course. However, it looks like it is not immediate to figure out a regular expression for $G$ even if we have been given the regular expression for $L$ and DFA for $L$.

---

Here is a way to show $G$ is regular by DFA.

Let the DFA for $L$ be $(\Sigma,Q, q\_0,\delta\_L, F)$.

Define (an incomplete) DFA $D$ with alphabet $\\{0,1,2,\\$\\}$, states $Q\times \\{s\_0, s\_1, o\\}$, initial state $(q\_0, s\_0)$, accepting state $F\times\\{s\_0, o\\}$, transition function $\delta\_D$ such that
$\delta\_D((q, s\_0), 0)= (\delta\_L(q, 0), o) $
$\delta\_D((q, s\_0), 1)= (\delta\_L(q, 1), s\_0) $
$\delta\_D((q, s\_0), 2)= (\delta\_L(q, 2), s\_0) $
$\delta\_D((q, s\_0), \\$)= (\delta\_L(q, 0), s\_1) $

$\delta\_D((q, s\_1), \\$)= (\delta\_L(q, 1), s\_0) $

$\delta\_d((q, o), 0)= \delta\_L(q, 0), o) $
$\delta\_d((q, o), 2)= \delta\_L(q, 2), s\_0) $
$\delta\_d((q, o), \\$)= \delta\_L(q, 1), s\_1) $

Here is how we can understand the states

* state $(q,o)$ corresponds to the states that are reached by words that end with $0$.
* state $(q,s\_1)$ corresponds to the states that are reached by words that end with odd number of $\\$$'s.
* state $(q,s\_0)$ corresponds to the states that are reached by words that end with $1$ or $2$ or even number of $\\$$'s.

We can check that $G=\\$L(D)\\$$.

---

**Exercise.** Prove that if $L$ is regular over $\Sigma=\\{0,1\\}$ then the following language over $\\{0,1,2\\}$ is also regular. $$ G=\\{x\mid \exists w\in L: x\text{ is derived from }w\text{ by substituting } 00 \text{ and } 11 \text{ with } 2 \text{ from left to right} \\}$$ For example, if $w=1000111110$, then $x=1202210$.

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


# Question
Title: Binary Tree Multithreaded Time Complexity
Let's say you want to get the value of all nodes in a binary tree (order doesn't really matter). If in each thread, you spawn two more threads to deal with the left subtree and the right subtree, then wouldn't the big O time complexity be O(log n). I was under the impression that you could never traverse an entire tree in less than O(n) since you'll have to search each node. However, it seems like by using multithreading, one can reduce the amount of nodes to be searched in half at each node.

Would the space complexity still be the same O(n)? Also, if the the time complexity really is O(log n), are there any optimizations that could possible make it a bit faster?

# Answer
> 2 votes
> \[..\], then wouldn't the big $\mathcal{O}$ time complexity be $\mathcal{O}(\log n)$

People often forget that big-$\mathcal{O}$ notation only is meaningful in a certain context, here this becomes obvious:

You are probably used to count some set of instructions (like comparing, adding etc.) as one unit - called unit cost model \- each instruction happening sequentially. In that model you're right, traversal and outputting every vertex of a binary tree is $\Omega(n)$ (ie. you cannot do better than linear).

However when talking about parallel algorithms and their complexity things change, first of all you will need to specify $p$ how many processors you use1. You will also need to specify whether multiple processors have exclusive or concurrent access for reading/writing.

You were probably talking about the CREW (concurrent read, exclusive write) PRAM and assumed $p = n$ in your question:

> you could never traverse an entire tree in less than $\mathcal{O}(n)$

In total all the processors will have looked at $\mathcal{O}(n)$ vertices in the binary tree, this does not change and is called the *work*.

You were right that the time complexity (refered to as *depth*) is $\mathcal{O}(\log n)$ for that algorithm.

---

To illustrate my point even more, assume that the binary tree is given as an array with a certain order and still using $n$ processors with a CREW machine. Now, every (numbered) machine can simply lookup the value at its position in that array.

This algorithm has still $\mathcal{O}(n)$ work, but $\mathcal{O}(1)$ depth.

### Conclusion

Always be aware of the context (eg. what model, what input format) since this has a great influence on the complexity. Once you introduce parallelism things become different and it's important to be precise about what assumption you make and how many processors an algorithm uses.

---

1: From now on I will assume a parallel random-access machine since it's very simple but still useful.

---
Tags: time-complexity, binary-trees, parallel-computing
---


# Question
Title: Are all countable partial functions computable?
I know all computable partial functions are countable. Wondering if it is the the other way around as well.

# Answer
You must be mistaken about a definition. It is not that any single computable partial function is countable. Rather, the set of all computable partial functions is a countable set. (There isn't any such thing as a countable partial function.)
> 2 votes

# Answer
By a countable partial function, you probably mean a partial function that can be specified by a finite amount of information. But even if you asked your question in that form, people would probably still tell you that "can be specified" is unclear, instead of trying to explain why the answer your question is: "No, there are non-computable functions which can be specified by a finite amount of information!"

The prototypical example of such functions are the partial functions from the arithmetical hierarchy, i.e. the functions computed by a Turing machine with access to an oracle for deciding whether an explicitly written down (by the Turing machine) "sentence in the first order language of arithmetic" is true or false.

Very few people would still protest that it is not clear whether those functions really "can be specified", since we have to assume that every "sentence in the first order language of arithmetic" is either true or false, for those functions to be well-defined. Computation in the limit provides even less objectionable examples of non-computable partial function which can be specified by a finite amount of information. In fact, those questions of "definability" were once investigated in the context of recursion theory.
> 0 votes

---
Tags: computability
---


# Question
Title: Origin of a story about a computer in the 50's recommending offing Pensioners
There's a story I've heard a few times in various computer science talks, usually offered as a cautionary tale, that goes something like this:

> In the late 50s, the British gov't purchased an early computer, and tried to build a computer model of the gov'ts budget, including every variable and factor they could think of. They then had it run an analysis to find the best ways to save money. The surprising result was they should decrease spending on traffic lights and cross-walks.
>
> This confused the researchers, since these items were a very small fraction of the total budget, much less then what the computer claimed could be saved by eliminating them. Upon further examination, they found that the source of the savings wouldn't be due to the direct cost of traffic lights, but were due to the increase in pensioners being killed trying to cross the street, thus saving the gov't X millons of dollars.

Even if the story is apocraphyl (which I sort of assume is the case) does anyone know what the original source is?

# Answer
The story is clearly made up.

There was no AI in the 1950's that could have come up with that.

There is no AI today and for many years that could come up with that.

Actually, an AI wouldn't come up with this idea at all. You would need a very well calibrated combination of AI and AS (Artificial Stupidity) to achieve this result.
> 1 votes

---
Tags: history
---


title: Proving $A^\ast = A$ on a given set

text:
# Question
Title: Proving $A^\ast = A$ on a given set
I am working on some set theory and am trying to prove how a set can have the property $A^\* = A$.

For set $A=\\{0^n1^n \mid n \ge0\\}$, I still do not understand exactly what $A^\*$ is. For example, I thought $A^\*$ is the enumeration of the set $A$ so

$A^\* = \\{\epsilon,01,0011,000111,00001111,....\\}$

Any helping in at least understanding what $A^\*$ is for this problem would be much appreciated!

# Answer
What you have written (i.e., $\\{ \varepsilon, 01, 0011, 000111, \ldots \\}$) is simply *$A$ itself*.

(Assuming $A^\ast$ is the Kleene star operation) you cannot prove $A = A^\ast$ because **it is not correct**.

The Kleene star $A^\ast$ is defined as the union of the powers $A^i$, where $A^0 = \\{ \varepsilon \\}$ and $A^{i+1} = A^i \cdot A = \\{ w \cdot w' \mid w \in A^i, w' \in A \\}$. An inductive argument easily shows: $$A^i = \\{ w\_1 \cdots w\_i \mid w\_1, \ldots, w\_i \in A \\} = \\{ 0^{n\_1} 1^{n\_1} \cdots 0^{n\_i} 1^{n\_i} \mid n\_1, \ldots, n\_i \ge 0 \\}$$

Since $A^\ast$ is the union over all such $A^i$, we obtain $$A^\ast = \\{ 0^{n\_1} 1^{n\_1} \cdots 0^{n\_i} 1^{n\_i} \mid i, n\_1, \ldots, n\_i \ge 0 \\},$$ which is obviously *not* equal to $A$.
> 2 votes

---
Tags: sets, kleene-star
---


# Question
Title: Algorithm : Visiting all stations in minimum time with additional constraints
I was given this question and not sure how to solve this. This is a DP minimization problem ?

Problem :

There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to travel from Station i to Station j (1 \leq i, j \leq N)$. Note that di,j=dj,i may not hold.

You are now at Station 1. From here, you have to visit all the stations exactly once. We assume that you have already visited Station 1. However, due to your schedule, there are M restrictions that must be satisfied. The format of each restriction is as follows:

Station si must be visited before Station ti. (1≤i≤M) Find the minimum time required to visit all the stations. Note that the last station to visit can be any of the stations.

Constraints 1≤N≤14 0≤di,j≤108 (1≤i,j≤N) di,i=0 (1≤i≤N) 0≤M≤N(N−1)⁄2 1≤si,ti≤N (1≤i≤M) si≠ti (1≤i≤M) There exists a path visiting all the stations under the given restrictions. Input Input is given from Standard Input in the following format:

N d1,1 … d1,N : dN,1 … dN,N M s1 t1 : sM tM Output Print the minimum time required to visit all the stations.

```
Sample Input 1
Copy
4
0 2 3 4
1 0 3 4
1 2 0 4
1 2 3 0
3
1 2
2 3
3 4
Sample Output 1
Copy
9
Due to the restrictions, we can only travel as follows: Station 1 → Station 2 → Station 3 → Station 4.
Thus, the answer is 2+3+4=9 and we should print 9.

Sample Input 2
Copy
3
0 1 20
1 0 20
10 20 0
0
Sample Output 2
Copy
21
Sample Input 3
Copy
1
0
0
Sample Output 3
Copy
0
Sample Input 4
Copy
14
0 28448202 94752369 6965437 42744902 7560126 75090662 8843627 69061140 64249326 57690728 42986477 48404113 88716403
73013281 0 37847212 34428188 25009906 3614271 82144791 23149022 94211619 56083883 547750 35036479 37794350 85146222
6400137 79121726 0 32137663 86550075 54343753 78531432 1169605 56872598 61793842 30013621 61824448 76242267 78181546
44000464 19945953 92672933 0 8488951 29783495 42361540 61448706 5092013 39670396 92639393 26910058 56878215 83406982
42411559 55713387 40842605 80915875 0 90870302 16746891 41698332 92400406 79586785 76734482 54938846 14817854 44262797
25618079 82961670 3220380 37882710 77238264 0 30285694 94010597 3313434 25248938 6148456 57383107 80041226 52974537
45702192 36993407 35034648 13099849 97787850 79254364 0 44172314 73023554 53984059 83657376 26813141 8449228 85695371
89466424 82640627 2816597 1216033 21988152 90828105 83428522 0 216303 46837120 30499660 38938821 68789759 30497390
14240720 49216529 36512207 64082795 92391305 70382708 28258331 4979511 0 884770 66017741 51457552 4005017 50751247
15122265 49804986 83078215 87707425 56873145 88791801 34219986 77073154 82798626 0 7386614 49058658 3482690 55300190
96344094 77929649 15796809 35347942 46688706 15359332 64653788 87407203 42689175 98416950 0 83290181 47967318 90377000
27375431 9920337 23971212 20418378 68812572 23746130 78728346 72070698 1939257 87280009 11983259 0 37799770 16442015
85303335 55565703 5694284 91866847 29725710 98189375 17777160 81031919 59126600 83771749 67762666 68788386 0 75480673
54861272 25070911 78287445 76137950 81268769 83585267 49252003 71439588 98965870 54719898 78225858 25335948 85354514 0
7
12 7
1 7
8 5
11 3
14 6
4 13
8 9

```

> Update: Cannot find the reference to the original problem but assumes this is from AtCoder.

# Answer
> 2 votes
Considering the "you have to visit all stations minimizing time", this is a Travelling salesman problem (see https://en.wikipedia.org/wiki/Travelling\_salesman\_problem).

The additional constraints on sequencing correspond to scheduler optimization.

I think the full problem is called "Sequential Ordering Problem". It is NP complete as both of its components. To answer your question, I think dynamic programming is not adapted to this type of problem. Indeed dynamic problem allows to decide recursively multiple choices like "yes" or "no". For instance have a look at the Knapsack problem (https://en.wikipedia.org/wiki/Knapsack\_problem) which can be nicely solved with DP.

**EDIT** (**credit to j\_random\_hacker** for this solution): In fact the Held-Karp algorithm (https://en.wikipedia.org/wiki/Held%E2%80%93Karp\_algorithm) is a DP solution for TSP problems. It builds iteratively optimal subsequences for all subsets testing all combinations. Among these combinations, just do not consider the ones that do not respect precedence constrains.

For N stations, it has a $O(2^N N^2)$ cost instead of the brute force solution having $O(N!)$. This at the price of a significant space cost $O(2^N N)$. Every independant precedence constrain reduces by a factor 2 the number of combinations to evaluate.

---
Tags: algorithms, graphs, dynamic-programming
---