# Question
Title: How to derive max amount of items from DP table of Knapsack problem?
I have a little bit changed algorithm for 1-0 Knapsack problem. It calculates max count (which we can put to the knapsack) as well. I'm using it to find max subset sum which \<= target sum. For example:

```
weights: 1, 3, 4, 5, target sum: 10
result: 1, 4, 5 (because 1 + 4 + 5 = 10)

weights: 2, 3, 4, 9 target sum: 10
result: 2, 3, 4 (2 + 3 + 4 = 9, max possible sum <= 10)

```

I use 2 DP tables: one for calculating max possible sum (`dp`) and one for max possible amount (`count`).

**The question is: how I can derive chosen values from the both tables?**

Example:

```
weights: [3, 2, 5, 2, 1, 1, 3], target_sum: 10
indexes:  0, 1, 2, 3, 4, 5, 6

dp:
0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1: [0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3]
2: [0, 0, 2, 3, 3, 5, 5, 5, 5, 5, 5]
3: [0, 0, 2, 3, 3, 5, 5, 7, 8, 8, 10]
4: [0, 0, 2, 3, 4, 5, 5, 7, 8, 9, 10]
5: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
6: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

count:
0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2: [0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2]
3: [0, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3]
4: [0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4]
5: [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5]
6: [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5]
7: [0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5]

```

Here, items with weight `[3, 2, 1, 3, 1]` should be derived (because they have max possible count) instead of (for example) `[5, 2, 3]`.

**Some notation explanations:**
`dp` means the same as in original Knapsack problem: `i` \- for the items, `j` for the weight. The value in the `dp[i][j]` mean the sum of chosen items (weights) which have sum \<= `j`.

Each cell in the `count` corresponds to `dp` and shows max possible amount of items (with total weight = `dp[i][j]`)

**How chosen items could be derived efficiently?**

I know how to derive just any items from the `dp` (e.g. not the max amount of them) by reconstructing it from the bottom-right cell. Also, I've found a hack which allows to derive the items if input is sorted. But I'm looking for the way which allows to do that without soring. Is it's possible?

---

The code which constructs these two tables doesn't matter much, but here it is:

```
def max_subset_sum(ws, target_sum):
    n = len(ws)
    k = target_sum

    dp = [[0] * (k + 1) for _ in range(n + 1)]
    count = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, k + 1):
            curr_w = ws[i - 1]
            if curr_w > j:
                dp[i][j] = dp[i - 1][j]
                count[i][j] = count[i - 1][j]
            else:
                tmp = round(dp[i - 1][j - curr_w] + curr_w, 2)
                if tmp >= dp[i - 1][j]:
                    dp[i][j] = tmp
                    count[i][j] = count[i - 1][j - curr_w] + 1
                else:
                    dp[i][j] = dp[i - 1][j]
                    count[i][j] = count[i - 1][j]

    return get_items(dp, k, n, ws)

def get_items(dp, k, n, ws):
    # The trick which allows to get max amount of items if input is sorted
    start = n
    while start and dp[start][k] == dp[start - 1][k]:
        start -= 1

    res = []
    w = dp[start][k]
    i, j = start, k
    while i and w:
        if w != dp[i - 1][j]:
            res.append(i - 1)
            w = round(w - ws[i - 1], 2)
            j -= ws[i - 1]
        i -= 1

    return res

```

Also, I have weird attempt to get max amount of items. But it's produces incorrect result which sums to `9`: `[3, 1, 1, 2, 2]`

```
def get_items_incorrect(dp, count, k, n, ws):
    start = n

    res = []
    w = dp[start][k]
    i, j = start, k
    while i and w:
        # while dp[i][j] < ws[i - 1]:
        #     i -= 1
        while ws[i - 1] > j:
            i -= 1
        if i < 0:
            break

        max_count = count[i][j]
        max_count_i = i

        while i and w == dp[i - 1][j]:
            if count[i - 1][j] > max_count:
                max_count = count[i - 1][j]
                max_count_i = i - 1
            i -= 1

        res.append(max_count_i - 1)
        w = round(w - ws[max_count_i - 1], 2)
        j -= ws[max_count_i - 1]

        i = max_count_i - 1

    return res

```

Sorry for the long read and thank you for any help!

---

**UPDATE 04/14/2021**

I found an error in generating `count` table: it will generate the same as in this post if the input is sorted. If input isn't sorted it will contains not max count. Will try to fix it.

# Answer
There are many ways to do this. One way is that you can create another table $T$ of size $7$ x $10$ such that entry $T\[i\]\[j\] = 1$ if item $i$ is picked in the optimal solution of sum $\leq j$; otherwise $T\[i\]\[j\] = 0$. You can create this table while filling entries for *count* and *dp* tables.

Now, to derive the chosen items that have maximum count, you start from the bottom-right cell, i.e., $T\[7\]\[10\]$.

* If $T\[7\]\[10\] = 1$, means you picked $7^{th}$ item. Suppose the weight of $7^{th}$ item is $w$. To get the next item, you now move to entry $T\[6\]\[10-w\]$...and so on.
* On the other hand, if $T\[7\]\[10\] = 0$, you simply move to $T\[6\]\[10\]$ since $7^{th}$ was not picked. You can proceed likewise.

---

Note: Constructing *dp* table might not be of any use to you.
> 0 votes

---
Tags: algorithms, dynamic-programming, knapsack-problems
---


# Question
Title: Decidability of languages with dfa/turing-machines
For any alphabet and any natural number k, a language of strings at least k is decidable.

So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has every string of 1's and 0's that are 5 or more characters at length (ie 01101, 011011 belong to language, while 011,10,1100 does not). Can such language be decidable and how so?

# Answer
> 1 votes
The easy and immediate way to see this is to note that the language of strings of length at most $k$ is finite, therefore it is regular. Regular languages are closed under complementation (just switch the accept and reject states), so your language of strings of length greater than $k$ is also regular.

---
Tags: turing-machines, computability, undecidability, semi-decidability
---


# Question
Title: How best to allocate stock buys and sells when using specific id to maximize long term capital gains
Setting aside the fact that tax lots (using specific id) should usually be assigned at the time of the trade (for stocks in the USA), let's assume instead we want an algorithm to optimally allocate them once we have the whole list of trades in hand for a single security. Each trade comprises: date-time, number-of-shares, total-dollar-amount and can be either buy or sell.

Our goal is to maximize the capital gains allocated to long term rather than short term, defined when a matching buy and sell are more than a year apart. A capital gain is the proceeds from the sale of the shares less the cost of those shares.

Example:

Buys

100 shares on Jan 01 2020 total cost \\$100

200 shares on Aug 01 2020 total cost \\$125

Sells

150 shares on Sep 01 2020 total proceeds \\$110

150 shares on Mar 01 2021 total proceeds \\$185

Total capital gain is \\$(185+110-125-100) ie. \\$70 which will be partly short term and partly long term such that short term capital gains + long term capital gains = \\$70.

What's the optimal algorithm to allocate tax lots when doing it in retrospect, ie.

What is a general algorithm identifying which share purchase to match to each share sold in order to maximize the long term capital gain portion?

So output might be something like, for the 150 shares sold on 9/1/2020, 100 should come from the first buy, 50 from the second buy. For the 150 sold on 3/1/2021, all 150 come from the 2nd buy.

# Answer
There's a natural greedy algorithm. Scan through the buy/sell orders in chronological order. At each sell order:

* Sell as many shares that would be classified as long-term as possible, until you've sold the number required by the sell order.
* If you still need to sell more shares, and there are no more shares that would be classified long-term sales, sell the youngest (newest / most recently bought) shares first.

I suggest trying to verify whether that leads to a correct algorithm or not. See How to prove greedy algorithm is correct.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Do we include Transmission delay in Round trip time?
Is RTT = $2\*T\_{Propagation delay}$ only. Or we include Transmission delay to send packets as well. Some examples include Transmission delay some not. I'm confused. Can anyone help.

# Answer
Suppose you have two computers (A and B) both connected to a switch with cut-through forwarding. When you are interested about RTT between computer A and computer B, you'll omit transmission delay, because the switch transmits the frame to B as it arrives from A, so transmission delay is not significant. Now, suppose that our switch uses store-forward, in this case, when the frame arrives, the switch will first store it completely, and then sends it to B, so we have to deal with transmission delay.
> 4 votes

# Answer
Ideally, TRTT should be 2\*Tpropogation \+ Ttransmission.
> 0 votes

# Answer
RTT is defined as the time it takes for a **small packet** to travel from client to server and back to client. It includes queueing delay, propagation delay and packet processing delay but doesn't include transmission delay. If we talk about TCP 3-way handshake or a request packet from client to server then the size of the packet involved isn't worth counting the transmission delay.

"To this end, we define the round-trip time (RTT), which is the time it takes for a small packet to travel from client to server and then back to the client. The RTT includes packet-propagation delays, packet queuing delays in intermediate routers and switches, and packet-processing delays"

Computer Networks: A Top Down Approach" by James F Kurose Above referenced book
> 0 votes

---
Tags: computer-networks
---


title: Number of possible min heaps

text:
# Question
Title: Number of possible min heaps
> The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is --------------

According to me, the answer should be 48. The first element 1 is fixed as root. The next level contains elements 2 and 3. The third level contains 4,5,6,7. Therefore, the total no. of cases should be 4! * 2!=48.

But my solution manual says that the answer should be 80.

Am I correct? If not, what am I doing wrong?

Thanks in advance

# Answer
The flaw in your approach is that you assume that the second level contains only $2$ and $3$. The following examples is min heap with $3$ not in the second level.

```
     1
   /    \
  2      5
 / \    / \
3   4  6   7

```

The solution is available here.

**Solution:** The root of the tree has to be the minimum element, therefore $1$ is at the root.

Now we need to find the possible ways to fill the left and right subtrees with the remaining $6$ elements. Each of the subtrees contain three elements. For the left subtree we can choose $3$ elements from $6$ elements in $\binom{6}{3}$ ways and the remaining three elements fill the right subtree.

Now in each of these subtrees the root would be the minimum of the three elements that comprise each of these subtrees. However, the two lowest elements in each of these subtrees can be interchanged. Therefore each of the subtrees can exists in two different configurations.

Therefore the total possible configurations would be:

$\binom{6}{3} \times 2 \times 2 = 80$.
> 4 votes

# Answer
The second level can contain other numbers than 2 and 3. See for example

```
      1
     / \
    2   5
   / \
  3   7
 / \
4   6

```

It is also unclear if you count isomorphic trees. See this question for a related answer.
> 2 votes

---
Tags: data-structures, combinatorics, heaps
---


# Question
Title: Throughput increase/decrease by how much percent
I am learning computer architecture and organization. I am stuck in the following question. Can someone please help me?

> The stage delays in a 5-stage pipeline are 300, 200, 100, 400 and 350 picoseconds. The second and third stages are merged into a single stage with delay 350 picoseconds. The throughput increase/decrease by ………… (percent).

This is what I tried:

Throughput of 1st case T1: 1/max delay =1/200
Throughput of 2nd case T2: 1/max delay= 1/350
%age increase/decrease in throughput: (T2-T1)/T1 * 100
= (1/350 - 1/200)/(1/200)\*100
= -42.8
So the throughput decreases by 42.8%.
But the correct answer is given to be 0. I don't understand why?

# Answer
The max delay isn't 200 and 350. In both cases, there is also a stage with a delay of 400ps, the clock speed is limited by that stage as well. The clock speed cannot be faster than 1/400ps = 2.5GHz either way, otherwise the slowest stage would break.
> 1 votes

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: How is this reduction of 3-SAT to Half-SAT not valid?
I am studying algorithms and there is a question in CLRS called the Half-SAT problem

> We are given a 3-CNF formula with n variables and m clauses where m is even. We wish to determine whether there exists a truth assignment to the variables of f such that exactly half the clauses evaluate to zero and the other half to 1. Prove that the half 3-SAT problem is NP-Complete.

What is to stop me from taking any input f to 3-SAT and adding m clauses (y or y or y) where y is not in the original m clauses. The transformation of input and output is clearly polynomial time.

And, given a solution to 3-SAT, there must be a satisfying solution to Half-SAT (the solver sets y to false). If there is not a solution to 3-SAT this means that one of the original m clauses is not satisfied these clauses are disjoint from the new clause, so either m - 1 or 2m - 1 clauses are True.

Yet all the solutions online are more complicated which makes me think I am missing something obvious.

# Answer
> 1 votes
As mentioned in the comments, this reduction is incorrect because it is necessary to have equivalence. While we may have 3-SAT =\> Half-SAT we do not have !3-SAT =\> !Half-SAT or Half-SAT =\> 3-SAT (the contrapositive). A proper reduction would need to do something like so:

Add m + 1 clauses (y or y or y)

Add a contradictory clause (y or not y)

Now exactly half of the clauses are True iff there is a solution to 3-SAT.

---
Tags: np-complete, reductions, satisfiability
---


# Question
Title: Why does the Huffman coding algorithm produce a valid tree?
I am not asking about the Huffman Code, but the most widely described algorithm for generating one, also described on the english wikipedia: https://en.wikipedia.org/wiki/Huffman\_coding#Compression

Now, I am not really concerned with the code being optimal or not, because many proofs for this can be found, but there is one thing that bothers me - why can I be sure, that for any path on the Huffman Code tree, no string constructed from labels is a prefix of another string in the tree?

Considering a simple tree (source: http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/huffman.php):

It has these codes: E - 0 U - 10 D - 01 L - 110 C - 1110 M - 11111 Z - 11110 K - 11111,
and it is obvious, that none of these codes is a prefix of another. However, I am looking for a general proof that this is true for any Huffman tree, which for some reason I am unable to find. I would be grateful for any sources.

# Answer
Let $v$ be a vertex of the tree. If $\pi\_v$ is the path from the root of the tree to $v$, then the string $s(v)$ constructed from the labels of $\pi\_v$ is unique (if you really want, you can prove this by induction on the depth of $v$).

If $s'$ is a proper prefix of $s(v)$ then there is a node $u$ in $\pi\_v$ such that $s(u)=s'$ and, by the above observation, this node is unique. Moreover, $u$ cannot be a leaf (since it precedes $v$ in $\pi\_v$).

This means that, for each leaf $v$ there is no prefix of $s(v)$ that matches the code $s(v')$ of another leaf $v'$. Since the symbols only appear as leaves of the tree, this means that the code is not ambiguous.
> 6 votes

---
Tags: correctness-proof, data-compression, huffman-coding
---


title: Is radix sort in-place or out-place?

text:
# Question
Title: Is radix sort in-place or out-place?
Generally, we can implement algorithms in-place and out-of-place.

However, I can't say for certain that radix sort can be implemented in both ways.

# Answer
It depends on the definition of in-place algorithm you are using.

* if in-place just means that the algorithm transforms the input without returning a new array, then yes;
* if you also want to use no additionnal data structure, or limit the additionnal space usage to be $o(n)$, then no, because of the creation of the arrays `count` and `output`.

There are different meanings to an in-place algorithm, as stated here.
> 1 votes

---
Tags: algorithms, sorting, python, in-place
---


title: Algorithm for winning solitaire

text:
# Question
Title: Algorithm for winning solitaire
Is there an algorithm that could check whether it is possible to win in the current situation in solitaire? That is, can we remove all cards from the table in a certain number of moves?

Description of the game:

Two decks of cards (36 pieces each) are connected and shuffled, and then they are laid out in 8 piles of 9 cards each. Possible work only with the top cards in each of the piles, namely, transfer one or several consecutive cards of a lower value to a card of a larger one (suits are not taken into account). If there are 9 cards in one of the piles in the correct order (ace-king-queen-jack-10-9-8-7-6), then this set is removed. If all the cards are removed from one pile, it can still be used and any card can be placed on top

# Answer
There sure is. Some sort of backtracking program will do the job. If you want the minimal number of moves, perhaps the (memory expensive) way to go is breadth first search. Maybe you can squeeze some performance out of it by adding conditions to cut off impossible branches or stop expanding when the current path is longer than the current best, or heuristics to search more promising moves first.

The eight queens puzzle is the typical example of backtracking in a much simpler setting, the cited page has a sample Pascal program (readable enough for any C-savy person). Dijkstra wrote a highly detailed discussion of the program, see his "EWD316: A Short Introduction to the Art of Programming".
> 2 votes

---
Tags: algorithms, game-theory
---


# Question
Title: Why did Apple include dedicated a neural network "processor" in standard consumer products?
Not sure if this is the right place, but I guess it is better than Reddit and I couldn't find any discussion.

I was wondering why Apple include a neural network "processor" and can't help but **feel** that is a waste as a prospective ML Engineer, so it is very likely that I am missing / in ignorance of something so wanted to ask what it is.

Two reasons come to my mind:

1. Apple will allow a distributed cloud computing on its products (Feels expensive if that is the only reason.).
2. Improved security. All personal bio-data (fingertip, face, speech) will be stored locally, while processing will be done on wholly local or quasi-local with some calculation going to servers safely.

Does anyone have any idea?

# Answer
Having a powerful machine learning chip in your device allows you to do things that you probably have not thought of. Things like improving the images that your camera is taking. Cutting out the background and replacing it with a boring beige background, very valuable if you are in a video conference and want to show your face to people but not your home.

Or a nice one: Most people in a video conference look at the screen, not at the camera, so when their image is transmitted, it seems that you can't look in the other persons eyes. Very nice if you have an ML chip how can change the image as if you were looking straight into the camera, without taxing your battery.

Something not done (yet) would be improving sound quality, for example removing background noise and filling in gaps when sound transmission fails, and totally cool would be removing people's accents, so that I can understand someone with a strong Scottish or Indian accent without problems.

You are about in the same situation as someone in the early 1980's asking what the advantages of a graphical user interface would be.
> 1 votes

# Answer
It is used for:

* Image analysis, and specially face recognition and search photos library.
* Language detection, text recognition and analysis ( to identify concepts in a text ). Used for advanced search in text
* Speech recognition
* Sound analysis, for efficient filtering and removal of noise in conversations and sound recognition ( Be able to differentiate musical instruments, or sounds like a crowd applauding or a baby crying ).

I also found interesting to read, in the developer documentation, that neural network engine was also used for - apparently - simple usage pattern detection. Not that this could not be done another way, but neural network is naturally good at it. To detect at what time/day you use an application, or listen our podcasts, in which order, and many others little habits on we have on our phone to try to make it behave as expected at the right time and place.
> 1 votes

---
Tags: machine-learning, computer-architecture
---


# Question
Title: Why is the Turing machine rather than the finite automaton the main model for computation if computers have finite memory?
Any physical computational device clearly has finite memory. On the other hand the input can be external and could therefore potentially be infinite. This idea is perfectly captured by the deterministic finite automata (DFA), so why do we use the Turing machines instead?

Let's consider a popular example. The language $$L = \\{a^nb^n, n\in \mathbb{N} \\} $$ is recognizable by a Turing machine, but not by a DFA. Suppose that you are getting a string from a server, and you need to determine whether it belongs to $L$ or not. I'd say you can't do it, because you might, in fact, run out of memory.

# Answer
First, I want to clear a misconception:

> On the other hand the input can be external and could therefore potentially be infinite.

Usually unless specified otherwise for some purpose, we do not consider TM inputs to be infinite, only *unbounded* in length (similar to DFA input strings, as a normal DFA cannot accept or reject a string that never ends). This distinction might be hard to grasp, but it will be useful. If you're curious, you can read up on $\omega$-automata, a class of automatons specifically modeling problems with infinite-length inputs.

It is true that an *individual* computer is, strictly speaking, more akin to an extremely big DFA than a TM. However, by modeling algorithms as TMs, we are trying to make a more general statement about computability, one that transcends individual computers. The theory of computation seldom concerns itself with the need to establish that a particular student laptop, ancient server or supercomputer can perform a particular computation.

Rather, by modeling a problem as a TM and comparing it to a real computer, we're establishing that the computation is possible in the sense that while a given machine might not be able to actually finish it, the only obstacles are the impractical logistics of acquiring a machine with enough RAM/paper/tape/you-name-it and possibly waiting impractically long, too. Alternatively, we're establishing that a given computer or model (eg. a programming language) can be used to simulate a Turing Machine and therefore compute anything computable under the same logistic constraints. And since the inputs are *finite*, the amount of memory you need to scrounge up (for a working, terminating algorithm) is finite too.

So yes, the TM does conveniently ignore that a given computer has a bounded memory, but since it doesn't need to represent a "given" computer but *any* computer, this slip is easy to forgive and doesn't prevent the comparison from serving its purpose. If you need to make formal proofs about a single computational device with bounded memory where the finite amount of states is likely to present an interesting issue, a DFA-equivalent model might indeed be better.
> 2 votes

---
Tags: turing-machines, finite-automata, computation-models
---


# Question
Title: can't quit understand one step of the recurrence time complexity calculation
I solved the question T(n) = T(sqrt(n)) + 1 but can't quit understand one step of the solution

I don't understand the transition in (1). how did we conclude that T(m) = T(m/2) + 1 from the previous step that m is in the power?

# Answer
It obviously is not correct. To fix it, define $S(m)=T(2^m)$, and then we would have $S(m)=S(m/2)+1$. Now, continue with the proof replacing everywhere $T(m)$ with $S(m)$. After you solve what $S(m)$ is, substitute $m=\log(n)$ in the solution to get what $T(n)=T(2^m)=S(m)$ is.
> 1 votes

---
Tags: time-complexity, recursion
---


# Question
Title: How to prove that one problem belongs to class P?
Is there any formal method to prove that one problem belongs to Complexity Class $\mathbb{P}$?

For example, how can we prove that the problem of finding $n^k$ belongs to Class $\mathbb{P}$? We can use the fact that each multiplication can be done in unit time.

If you present an algorithm that can solve this problem with $\mathcal{O} (\log n)$ time, can it be a proof?

# Answer
> 2 votes
Yes. In fact, any algorithm that runs in polynomial time counts. For examle, even an $O(n^8)$ would suffice! Therefore, there is no real need to optimize your algorithms to such extremes.

---
Tags: algorithms, complexity-theory, time-complexity, asymptotics, complexity-classes
---


title: Show that NL ⊆ P

text:
# Question
Title: Show that NL ⊆ P
Can somebody please explain this in simple terms. I don't understand Sipser's way of explaining it.

He says this is a corollary to PATH is NL-complete which I do not understand either.

Can somebody please explain everything in a simple manner to me?

> Theorem 8.25 shows that any language in NL is log space reducible to PATH. Therefore, any language in NL is polynomial-time reducible to PATH, which in turn is in P, by Theorem 7.14. We know that every language that is polynomial-time reducible to a language in P is also in P, so the proof is complete.

# Answer
> 2 votes
$\textsf{PATH}$ is in $\textsf{NL}$, because to solve it, you just need to keep in memory the current vertex you are in, and guess (non-deterministicaly) the next one on the path until you reach your destination. Since you keep the current vertex $v$, numbered from $0$ to $|V| - 1$, you need a memory space corresponding to the binary encoding of $v$, which is at most $1 + \log\_2(|V| - 1)$. You also need to keep the potential adjacent vertex of $v$, next in the path.

All in all, a Turing Machine solving this problem would only need $O(\log |V|)$ additionnal space memory (the memory of the graph and of the starting vertex and the destination vertex of the path you are guessing are not considered in the memory used, because they are part of the input).

$\textsf{PATH}$ is $\textsf{NL}$-hard, because to solve any $\textsf{NL}$ problem, you have to determine if there exists a sequence of possible transitions from the initial configuration to an accepting configuration in the Turing Machine of the problem. If you consider a graph of the possible configurations (where there exists an edge from a configuration $\alpha$ to a configuration $\beta$ if and only if one can go from $\alpha$ to $\beta$ in one transition in the Turing Machine), then solving the $\textsf{NL}$ problem is the same as solving $\textsf{PATH}$ in the graph of possible configurations.

You then need to prove that the graph of configurations can be constructed in logarithmic additionnal space. This can be done, because if a non-deterministic Turing Machine works in space $s(n)$, then the number of possible configurations is $2^{O(s(n))}$. Considering the binary encoding of those configurations, one can determine if there exists an edge between two configurations in deterministic space $O(s(n))$.

Now, since $\textsf{PATH}$ is solvable in polynomial **time** (with a graph traversal algorithm, for example), that means that any $\textsf{NL}$ problem is solvable in polynomial time (via the $\textsf{NL}$-completude of $\textsf{PATH}$), so $\textsf{NL}\subseteq \textsf{P}$. This stands true, because if a Turing Machine uses $s(n)$ space memory, then it has at most $2^{O(s(n))}$ configurations, and exploring all of them takes time $2^{O(s(n))}$. Since $s(n) = \log n$ for problems in $\textsf{NL}$, the total time is indeed $n^{O(1)}$.

---
Tags: complexity-theory
---


# Question
Title: Can a runtime environment detect an infinite loop?
Would it be possible for a runtime environment to detect infinite loops and subsequently stop the associated process, or would implementing such logic be equivalent to solving the halting problem?

For the purpose of this question, I define an "infinite loop" to mean a series of instructions and associated starting stack/heap data that, when executed, return the process to exactly the same state (including the data) as it was in before initiating the infinite loop. (In other words, a program generating an indefinitely long decimal expansion of pi isn't "stuck" in an "infinite loop," because at every iteration, it has more digits of pi somewhere in its associated memory.)

(Ported from https://stackoverflow.com/q/16250472/1858225)

# Answer
> 13 votes
It might be **theoretically possible** for a runtime environment to check for such loops using the following procedure:

After ever instruction executed, the runtime environment would make a complete image of the state of a running process (i.e. all memory associated with it, including registers, P.C., stack, heap, and globals), save that image somewhere, and then check to see whether it matches any of its previously saved images for that process. If there is a match, then the process is stuck in an infinite loop. Otherwise, the next instruction is executed and the process is repeated.

In fact, rather than performing this check after every single instruction, the runtime environment could simply pause the process periodically and make a save-state. If the process is stuck in an infinite loop involving *n* states, then after at most *n* checks, a duplicate state will be observed.

Note, of course, that this is **not** a solution to the halting problem; the distinction is discussed here.

But such a feature would be an **enormous waste of resources**; continually pausing a process to save *all memory associated with it* would slow it down tremendously and consume an enormous amount of memory very quickly. (Although old images could be deleted after a while, it would be risky to limit the total number of images that could be saved because a large infinite loop--i.e., one with many states--might not get caught if there are too few states kept in memory.) Moreover, this feature wouldn't actually provide that much benefit, since its ability to catch errors would be extremely limited and because it's relatively simple to find infinite loops with other debugging methods (such as simply stepping through the code and recognizing the logic error).

Therefore, I doubt that such a runtime environment exists or that it will ever exist, unless someone programs it just for kicks. (Which I am somewhat tempted to do now.)

# Answer
> 6 votes
Let's assume that the program does not interact with the outside world, so that's it's really possible to encapsulate the entire state of the program. (This means it does not do any input, at least.) Furthermore, let's assume that the program is running in some deterministic environment so that each state has a unique successor, which means that the runtime is either not threaded, or that the threading can be deterministically reduced to a sequence.

Under these highly improbable but theoretically non-limiting assumptions, we can duplicate the program and run it in two separate runtimes; each will do exactly the same computation.

So let's do that. We'll run it once in the Tortoise runtime, and at the same time we'll run it in the Hare runtime. However, we'll arrange for the Hare runtime to operate exactly twice as fast; every time the Tortoise runtime makes one step, the Hare runtime makes two steps.

Now we can (theoretically) compare the states after every step of the Tortoise runtime. If the program reaches an endless loop of $n$ steps after some non-looping prefix of $p$ steps, then the Hare and Tortoise states will be identical at every Tortoise step $kn$ for any integer $k$ where $kn\ge p$.

The total cost of the test is one extra state and one state comparison per step, and it will terminate in no more than three times the number of steps it takes for the program to complete its first loop. (One time in the Tortoise and twice in the Hare, for a total of three times.)

As the terms I used imply, this is just Robert Floyd's famous Tortoise and Hare cycle-detection algorithm.

# Answer
> 3 votes
The AProVE termination tool performs static analysis on rewrite systems (including a subclass of Haskell programs) which can *prove* non-termination, giving an actual example of non-terminating program. The technique is quite powerful and works using a variant of a technique called narrowing.

As far as I know though, there has not been much work on detecting actual non-termination for general languages.

# Answer
> 3 votes
Just as I was going to suggest Floyd's cycle-detection algorithm, rici's post beat me to it. However, the whole thing can be made more practical by speeding up comparisons of full states.

The bottleneck of the proposed algorithm would be in comparing full state. These comparisons will usually not finish, but stop early --- at the first difference. One optimization is to remember where the past differences occurred, and check those parts of the state first. For example, maintain a list of locations, and go through this list before making a full comparison. When a location from this list exposes a difference, stop the comparison (with failure), and move the location to the front of the list.

A different (and potentially more scalable) approach is to use incremental hashing. Pick a function of the full state such that the hash values are easy to adjust in O(1) when some part of the state changes. For example, take a weighted sum of state words mod some large prime and concatenate with the unweighted sum mod some other large prime (can also throw in a modular weighted sum of squares of words, with different weight and modulus). This way, hash updates will take O(1) time on each execution step, and comparisons will take O(1) time until you get a hit. The probability of a false positive (i.e., the hashes match while the states differ) is very low, and even if this ever happens, it will amortize over a large number of true negatives (false negatives are impossible).

Of course, in practice, it seems more likely to get into situations like generating digits of the number pi --- things keep on changing, but never end. Another frequent possibility is that the infinite loop allocates memory, in which case it quickly exhausts all available memory.

In my course on algorithms and data structures, our autograder has to deal with student submissions that sometimes get into infinite loops. This is taken care of by a 30-second time-out and a certain memory limit. Both are much looser than runtime and memory budgets we impose as part of grading. I am not sure if implementing true infinite-loop detection would make a lot of sense in this context because such programs will run quite a bit slower (this is where hardware support for state hashing could help, but again you'd need additional uses to justify this). When students know that their program timed out, they can usually find the infinite loop.

# Answer
> 1 votes
There is an efficient way of detecting infinite loop, with no practical drawbacks (even if it is impossible in theory):

Let's says you have a cryptographic hash function like sha256, delivering a 256 bit's "imprint" of whatever input you give, with a probability of collision of 2^-128 (due to birthday problem).

Let's use an integer counter of 128 bits. here is the detection method:

let's says we have a pure function new\_state=f(state); (aka new\_state depends only of state). also we have a function bool stop(state);

one can detect that repeated f will end up as an infinite loop (halting problem) like this (C++ code):

```
uint128 counter=0;
auto current_hash = sha256(current_state);
auto sample = current_hash;
while(not stop(current_state)) {
  current_state = f(current_state);
  current_hash = sha256(current_state);
  if (current_hash == sample)
     break; // infinite loop detected and avoided
  if (0 == ++counter)
     break; // failed detection, after 3e+38 =2^128 iterations.. past end of our universe
  if (0 == (counter & (counter+1))) // counter is a power of 2 -1
    sample = current_hash;
}

```

Note that does not really solve the theoretic halting problem:

* hash is only stochastic
* integer may be too small for loop size
* some never ending programs may not become periodic as they may grow the state with no limit.

But it never occurs for regular programs.

# Answer
> 0 votes
You can use the same algorithm as for cycle detection in linear lists: Use two copies of your machine, one executing two steps per cycle, the other executing one step per cycle. If you enter two identical states, then you are in a loop. If you never enter two identical states, which could happen for an infinite Turing machine, then you don't know whether you are in a cycle. You might be able to add a clever AI that will be able to find a loop through some cleverness in some cases, but it won't work in all cases. And if the program halts, then you know that.

Summary: Very easy mechanical solution that works for some cases. High cleverness that works for other cases. Nothing that works for every possible program.

---
Tags: halting-problem
---


title: Constant-time adding an element?

text:
# Question
Title: Constant-time adding an element?
Is a computer with infinite memory and infinite word size a Turing machine equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) if we allow constant-time linked list element insertion (at the beginning of the list)?

I doubt this because element insertion requires memory allocation and allocation is usually not a constant-time operation.

# Answer
> 0 votes
Oh, I've found an $O(1)$ allocation strategy:

Because our memory is infinite, we may never deallocate: Just add memory at the end of the used space by incrementing a pointer.

---
Tags: complexity-theory, turing-machines, polynomial-time, memory-allocation
---


# Question
Title: Searching in sorted array with $O(\log n)$
Recently been practicing some recent exams, there was a problem I could not comprehend the given answer, the question is as follows:

> Suppose array $A\[1..n\]$ consist of $n$ distinct integers that is sorted in ascending order, then How many of below problems could be solved in $O(\log n)$?

and there were three statements;

> * Find an $i$ index so that $A\[i\]= i $
> * Find an $i$ index so that $A \left \lfloor{i}\right \rfloor = 3i +2$
> * Find an $i$ index so that $A\[i\]= 4i^{2} + 3i + 5$

The answer sheet stated as `one statement is true`, Also there was no clue on which statement is true.

---

What is my issue?

So I think the `first` and `second` statements could be true, since the array is sorted then we can use Binary search with $O(\log n)$ to find the element with index $i$, also the first two statements are linear, thus I think that's what the question wants, If it's not then I don't know what the question exactly wants, any explanation would be handful.

# Answer
You can answer the first question with `binary search`. Lets consider you're now discussing the interval $\[l, r\]$, and $m = \frac{(l + r)}{2}$. If $A\[m\] = m$, you have found an answer and you shall stop the search. If $A\[m\] \< m$, then the answer must be in the interval $\[m + 1, r\]$, because if $i \le m$, then $A\[i\] \le A\[m\] - (m - i) \< m - (m - i) = i$ (since the array is sorted in strictly ascending order and the elements are integers), thus no $i \in \[l, m\]$ can be the answer. Otherwise, if $A\[m\] \> m$, then the answer must be in the interval $\[l, m - 1\]$, because if $i \ge m$, then $A\[i\] \ge A\[m\] + (i - m) \> m + (i - m) = i$.

And I don't think you can solve the other tasks in $O(lg(n))$ using `binary search`. Consider these two examples :

$A = \[5, 6, 12, 14, 15\]$
$B = \[4, 9, 12, 14, 17\]$

As we know, `binary search` initially examines the middle element, in these cases, $12$. $12 \ne 3 \times 3 + 2$, thus the search has to continue. In both cases, decision must be the same, since the middle element is the same, therefore, if the algorithm decides to check the interval $\[4, 5\]$, the algorithm will respond `NO` to the array $A$, although $5 = 3 \times 1 + 2$, and if the algorithm decides to search the interval $\[1, 2\]$, it yields `NO` to the array $B$, while $17 = 3 \times 5 + 2$.

It is also true about the third task, with examples :
$A = \[13, 49, 51, 52, 180\]$
$B = \[12, 48, 51, 52, 193\]$

I hope my answer was helpful.
> 1 votes

---
Tags: asymptotics, search-algorithms, arrays
---


# Question
Title: CFG for $L=\{a^m b^n c^k | m,n,k > 0, k\neq m+n\}$
I started learning CFG and I'm trying to find CFG for this language, but I have no idea where to start and I can't seem to find this one online anywhere. It would be great help, if someone could show me how to do it. Thank you!

# Answer
You can verify that the following CFG recognizes the language $\\{a^nb^mc^k|n,m,k\>0, n+m=k\\}$:

> $S \rightarrow aXc | aSc$
>
> $X \rightarrow bXc | bc$

Now your language $L$ can be written as $L = L\_1 \cup L\_2$ where $L\_1 = \\{a^nb^mc^k|n,m,k\>0, n+m\>k\\}$ and $L\_2 = \\{a^nb^mc^k|n,m,k\>0, n+m\<k\\}$.

You can then find a CFG for $L\_1$ and $L\_2$, based on the grammar I gave you above.
> 0 votes

---
Tags: context-free, formal-grammars
---


title: $P=PP$ or $P=PSPACE$ vs $VP=VNP$

text:
# Question
Title: $P=PP$ or $P=PSPACE$ vs $VP=VNP$
We do not know if $P=NP$ has an impact on $VP=VNP$ however how about $P=PP$?

1. Is $PP$ and $VNP$ related and would $P=PP$ or $P=PSPACE$ imply $VP=VNP$?
2. Is there a way to show $\\#P$ is in $FP^{PP}$?

# Answer
> 1 votes
Note that $\\#P\in FP^{PP}$ follows from a simple binary search. Given some non-deterministic machine $M$, the language $\\{(x,k) |\\#M(x)\ge k\\}$, where $\\#M(x)$ is the number of accepting paths on input $x$, is in PP (you can change the constant in the definition of PP to any FP function). Thus, using a PP oracle we can count the number of accepting paths via binary search.

This implies that $\mathsf{P=PP}$ puts permanent in $VP$, as the problem of counting the number of perfect matchings in a bipartite graph (or equivalently, computing the permanent of the adjacency matrix) is in $\\#P$.

---
Tags: complexity-theory, np, complexity-classes, polynomial-time, counting
---


# Question
Title: Upper and lower tangent line to convex hull from a point
Is it possible to find an upper and lower tangent line to a convex hull in $log(n)$ time where $n$ is number of points on a convex hull? I have just done it in linear time where I checked for upper tangent line if orientation of $S,i,i+1$ is greater than zero (anti-clockwise) and if orientation of $S,i,i-1$ is greater than zero as well. Same for lower tangent line where I checked if its clockwise orientation. $S$ is a point from where I want my tangent line to go, $i$ is a point on a convex hull and $i-1$,$i+1$ are its neighbours. This is the only source I've found so far\[Link\]$\_1$ and I really can't understand the algorithm for now.

# Answer
Let's assume that the convex polygon $P$ is defined as an ordered list $(p\_0,p\_1,...,p\_{n-1})$ of points, and for each such point $p \in P$ we are able in $O(1)$ time to find a previous point $Prev(p)$ and a next point $Next(p)$ according to this order, taking into account that:

$$Prev(p\_0)=p\_{n-1}$$ $$Next(p\_{n-1})=p\_0$$

The binary search over this list is very similar to a binary search over a regular array - on each step you have a $p\_{left}$ point, a $p\_{right}$ point and a $p\_{mid}$ point. You check some condition on the $p\_{mid}$ point and then choose a $\[p\_{left},p\_{mid}\]$ interval or a $\[p\_{mid},p\_{right}\]$ interval for the next step.

The condition you want to check is the following one. In order for the $p\_{mid}$ point to be the tangential point for all lines going through the query point $S$, **both neighbors of the $p\_{mid}$ point must be on the same side of the line, connecting the point $S$ and the $p\_{mid}$**. You'll have to choose, which side of this line is *right* and which side is *wrong* \- this will define, which tangent line you'll get (upper or lower). So, if the previous point $Prev(p\_{mid})$ is on the wrong side, then you choose the left interval. Similarly, if the next point $Next(p\_{mid})$ is on the wrong side of this line, then you choose the right interval for the next step. This algorithm will stop on one of two tangential points if and only if the point $S$ is located outside of the polygon $P$.

The algorithm doesn't need any preprocessing of the convex polygon $P$ and nevertheless finds tangential points for any query point, located outside of the polygon, in $O(\log n)$ time.
> 2 votes

---
Tags: computational-geometry, binary-search, convex-hull
---


title: Pruning: Outlier Candidate Selection

text:
# Question
Title: Pruning: Outlier Candidate Selection
I am using method 3.3 described in Outlier Detection using Isolation Forest and Local Outlier Factor .

It states:

Specify a dataset: $={\_1, \_2, ..., \_}$. Here, is the sample number of . $\_$ is an attribute in $$, and $\_={\_1, \_2, ..., \_}.$ $\_$ is a certain data value of the attribute $\_$ . The outlier coefficient of the attribute is defined as:

Here, $\bar{}$ is the mean of the attribute $\_$ and $\_$ is used to measure the degree of dispersion of the attribute $\_$ . Calculate the outlier coefficient of each attribute in the dataset, and get the outlier coefficient vector $\_$ of the dataset, which is recorded as: $\_ = \_1, \_2, ..., \_n$

However, I do not understand what value to select for $x\_j$. What does a 'certain data value' mean in this case?

# Answer
I suspect this paper has typos (see e.g., line 2 of Algorithm 1). If so, you're going to have to guess from context what they might have meant.

It's possible that they might have meant to write

$$fd\_i = \frac{\sqrt{\frac{\sum\_j (x\_j - \bar{x})^2}{n}}}{\bar{x}}$$

In other words: the ratio between the standard deviation and the mean of that attribute.

Who knows; this is just a guess. You might try contacting the authors.
> 0 votes

---
Tags: algorithms, machine-learning
---


# Question
Title: Complexity of pattern matching for modus ponens logical conclusions
Is a Turing machine with added the following contant-time operation equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) to a (usual) Turing machine:

By predicates I will mean predicates in first-order predicate calculus. (Note that predicates may have free variables.)

* constant-time modus-ponens resolution (yes or no) and then adding $y$ to the end of this array if yes, for given predicates $x$ and $y$ and an array (or a linked list) of predicates. By definition of modus ponens, it's yes, if and only if some element of the arrays is $X\Rightarrow y$ where $X$ is a pattern matching $x$.

Remark: The above operation is a part of the standard procedure of proof-checking is first-order predicate logic.

If the above hypothesis is false, then what is the running time upped bounds of the above operation in different kinds of Turning machine equivalents (such as Turing machine, Markov algorithms, von Neumann architecture with infinitely many infinitely big words of memory, etc.)?

BTW, is von Neumann architecture with infinitely many infinitely big words of memory a Turning machine equivalent? (I think yes, but not 100% sure.)

# Answer
> 1 votes
This boils down to the question of whether there exists a polynomial-time algorithm for your matching operation.

If there exists such an algorithm, call it $A$, then the answer to your question is yes: given an augmented Turing machine that uses these operations, you can convert it to an ordinary Turing machine by simulating those operations using $A$. This blows up the running time by at most a polynomial. (Invoking a polynomial-time subroutine at most polynomially many times leaves with a running time that remains polynomial.)

If there is no such algorithm, then the answer to your question is no: the matching problem can be solved in polynomial time (indeed, constant time) on an augmented Turing machine, but cannot be solved in polynomial time on an ordinary Turing machine.

I'm not clear on the definition of your matching operation, and I'm not an expert in computational logic, so I don't know what is the computational complexity of the matching operation you have in mind.

---
Tags: complexity-theory, logic, polynomial-time, pattern-recognition, predicate-logic
---


# Question
Title: Is it OK to change any polynomial time to another polynomial time without breaking equivalency of Turing machines?
Is it true that adding to a Turing-machine-equivalent an "oracle" calculating any polynomially calculable (in this machine) function using some *other* nonzero polynomial time than this machine itself could do, leaves the new Turing machine equivalent (in the sense that polynomial algorithms remain polynomial and exponential ones remain exponential)?

# Answer
> 3 votes
Yes. You can replace the oracle with subroutine calls to the polynomial-time implementation of the oracle. Or, to put it another way: $P$ is closed under composition.

The running time remains polynomial: if the original Turing machine used $p(n)$ steps, and the subroutine takes $q(n)$ steps, then the resulting machine will use at most $p(n) + q(p(n))$ steps, which is upper-bounded by a polynomial.

---
Tags: complexity-theory, turing-machines, polynomial-time
---


# Question
Title: |L(M)| <= 330 is not computably enumerable
M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.

Why is {M : |L(M)| \<= 330} not CE?

I can't seem to understand the logic why it is not CE, wouldn't it be CE since if it goes over 330, then we just halt?

Here they mention that its complement is CE, then by Rice Theorem, |L(M)| \<= 330} is not CE, but I still don't understand why the same logic that was used to prove its complement is CE, can't be applied to "Is |L(M)| \<= 330} is CE?".

# Answer
> 0 votes
> I can't seem to understand the logic why it is not CE, wouldn't it be CE since if it goes over 330, then we just halt?

The issue is what we do *next*: does halting correspond to "IN" or "OUT"?

A c.e. language is one for which we have an algorithm halting on exactly those inputs **in** the language. However, the "wait until you see 331, then halt" algorithm here halts on exactly those inputs **not in** the language. Like c.e.-ness this is a kind of "half-computability" property, but it's *the other half*: this is an example of a **co-c.e. language**.

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


# Question
Title: Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?
My understanding of non-deterministic algorithms is that they're "as lucky as you want".

> ...you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.

For example, if you choose two vertices `v` and `w`, if there's a `vw` path, then you can non-deterministically walk a `vw` path, luckily correctly guessing the vertices to walk in a `vw` path. Given this is true of paths in general, I wonder if the same can be done for Hamiltonian paths. I would think so, but I'm not sure.

Therefore, my first question is: if you can non-deterministically walk a `vw` *path*, can you non-deterministically walk a *Hamiltonian path* from `v` to `w`, if a Hamiltonian path exists? If you can non-deterministically walk a Hamiltonian path, I wonder if the same can be done for an additional constraint, what I'm calling a "least Hamiltonian path." I would think so, but I'm not sure.

Define the **least Hamiltonian path** from `v` to `w` to be the Hamiltonian path such that the second vertex is the smallest it can be, then the third vertex is the smallest it can be, the fourth is the smallest, etc. Assume vertices are integers. For example, if we consider `K5` the graph with vertices `{1,2,3,4,5}` and all possible edges, then the least Hamiltonian path for `(v,w)` = `(2,3)` is `21453`. If you were at vertex 2, the **next least vertex** would be 1. Then, the next least vertex would 4. etc.

Therefore, my actual question is: **Given graph `G` and vertices `v` and `w` can you non-deterministically walk the least Hamiltonian path from `v` to `w`, if it exists?**

Motivation: If so, then perhaps there's a space-efficient algorithm for non-deterministically walking a Hamiltonian path: You can keep a counter for vertices `v` and `w`, and go through each pair of vertices such that `v<w`, checking for the existence of a least Hamiltonian path. To ensure all vertices in `G` are reached, keep a counter for the number of vertices walked (this should equal `N` if there are `N` vertices). Also, ensure that each vertex in the path is unique. The least Hamiltonian path from `v` to `w` will be unique, therefore it can be walked multiple times (each time you walk through it, starting at `v`, you'll non-deterministically guess the next least vertex in the least Hamiltonian path). You could use two counters to ensure no vertices are repeated - one for the vertex you're checking to see if it's unique (loop through the vertices in the least Hamiltonian path), and another counter for a second pass through the least Hamiltonian path. Ensure the second counter encounters the value of the first counter exactly once (use a boolean flag to keep track of this).

# Answer
> 2 votes
No. There has to be a way to verify that your choices led to a correct choice, in polynomial time (with an ordinary deterministic computer). Given a particular Hamiltonian path, there's no way to verify it is the least Hamiltonian path (in polynomial time).

The "space alien" stuff is just intuition, but if you want to know what it means in a precise way, you need to go to the formal mathematical definition. My favorite definition of NP is the verifier-based definition. With that definition, there is no obvious way to pick a short certificate that a polynomial-time (deterministic) algorithm can use to verify that a proposed solution to the problem is correct.

---
Tags: graphs, graph-traversal, hamiltonian-path
---


# Question
Title: Is there a relationship between visitor pattern and DeMorgan's Law?
Visitor Pattern enables mimicking sum types with product types. Where does the "sum"-iness come from?

For example, in OCaml one could define `type my_bool = True | False`

Or encode with visitor pattern:

```
type 'a bool_visitor = {
  case_true: unit -> 'a;
  case_false: unit -> 'a;
}

let t visitor = visitor.case_true ()
let f visitor = visitor.case_false ()

let visitor = {
  case_true = (fun () -> "true");
  case_false = (fun () -> "true");
}

let () = print_endline (t visitor) (* prints "true" *)

```

What's the best way of explaining the sum-type-to-visitor-pattern transformation? Is it:

* Of course + and * are interdefinable, what did I expect?
* Or is it that the left side of `->` is the "negative" position and that this leads to a DeMorgan-law-like flip of sum and product?

I also wonder if this question is related to how one can use universally-quantified types to mimic existential types.

# Answer
The best way to explain it is $$\mathsf{Bool} \to C \cong C \times C,$$ which is a special case of $$(A + B) \to C \cong (A \to C) \times (B \to C).$$ Read the above as follows: as sum is equivalent to a pair of visitors.

(By the way, this is not the de Morgan law. It does not have a name, as far as I know. It's a general consequence of the definition of the concepts involved.)
> 2 votes

---
Tags: data-structures, type-theory
---


# Question
Title: Does this algorithm for permuting rows and columns of a matrix converge?
Given a binary matrix, define the magnitude of a row by reading off the numbers in it left to right and similarly for columns, reading the numbers going down. For instance, the row magnitude of the 1-st row of this matrix is 1001101, and for the 2-nd column it is 11.

1 0 0 1 1 0 1
0 0 0 1 1 0 1
0 1 1 0 0 1 0
0 1 1 0 0 1 0

I would like to sort a matrix by doing the following:

1. reorder rows so that rows are ordered in descending order according to their row magnitude
2. reorder columns so that columns are ordered in descending order according to their column magnitude
3. repeat 1 and 2 until rows and columns are in a correct order

For the matrix above this would go as follows:

sort by rows (step 1)
1 0 0 1 1 0 1
0 1 1 0 0 1 0
0 1 1 0 0 1 0
0 0 0 1 1 0 1

sort by columns (step 2)
1 1 1 1 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1
1 1 1 0 0 0 0

sort by rows (step 1)
1 1 1 1 0 0 0
1 1 1 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1

both columns and rows are in order, terminate procedure.

For the majority of matrices, performing steps 1 and 2 once won't be sufficient, since reordering columns will ruin the ordering of the rows. However, strangely enough it seems like 3 reorderings are sufficient to order matrices I've tried it on.

Despite not being able to find a counterexample, I struggle to see why this would be the case, and even more generally, what guarantees the algorithm won't get stuck in a cycle. Is there an existing name or more formal way to describe this algorithm and are there any proofs on its convergence?

# Answer
> 5 votes
For an $n \times m$ matrix $M$, define the potential function $$ \Phi(M) = \sum\_{i=1}^n \sum\_{j=1}^m 2^{n-1-i} 2^{m-1-j} M(i,j). $$ If we write it as $$ \Phi(M) = \sum\_{i=1}^n 2^{n-1-i} \sum\_{j=1}^m 2^{m-1-j} M(i,j) $$ then it immediately follows that reordering rows either fixes $M$, or strictly increases $\Phi$. Similarly, reordering columns either fixes $M$ or strictly increases $\Phi$. Since there are only finitely many $n \times m$ matrices, it follows that your algorithm eventually converges.

It is definitely not the case that the process terminates after three steps. For example, here is a matrix which requires five steps: $$ \begin{pmatrix} 0&0&1&0 \\ 0&1&0&0 \\ 1&0&0&1 \\ 0&0&1&1 \end{pmatrix} $$ This is a matrix in which the $(i,j)$'th entry depends only on $i+j$. Specifically, $M(i,j) = 1$ iff $i+j \in \\{4,7,8\\}$.

More generally, the $n \times n$ matrix $M$ in which $M(i,j)=1$ iff $i+j \in \\{4,2n-1,2n\\}$ requires $2n-3$ rounds, which is optimal for small values of $n$ (over *all* $n \times n$ matrices). Moreover, this is the unique choice over matrices of this form.

(To complete the picture, for $n = 3$ the unique optimal choice is $i + j \in \\{4,6\\}$ rather than $i+j \in \\{4,5,6\\}$, and for $n = 2$ the only choices are $i+j \in \\{4\\}$ and $i+j \in \\{3,4\\}$, which both correspond to two rounds.)

---
Tags: sorting, matrices, permutations
---


# Question
Title: Is $\Pi’\propto_{poly}\Pi$ for any two NP-complete problems $\Pi,\Pi'$?
I am facing the following question:

> Let $\Pi$ and $\Pi$’ be two NP-complete problems, prove or refute $\Pi’\propto\_{poly}\Pi$.

I do not understand the meaning of this question and how to answer it.

The definition of $\Pi’\propto\_{poly}\Pi$" as follows:

> Let $\Pi$ and $\Pi'$ be two decision problems. We say that $\Pi$ reduces to $\Pi'$ in polynomial time, symbolized as $\Pi’\propto\_{poly}\Pi$, if there exists a deterministic algorithm $A$ that behaves as follows. When $A$ is presented with an instance $I$ of problem $\Pi$, it transforms it into an instance $I’$ of problem $\Pi'$ such that the answer to $I$ is yes iff the answer to $I’$ is yes. Moreover, this transformation must be achieved in polynomial time.

# Answer
> 1 votes
Try to combine the following two definitions:

1. A problem $\Pi$ is NP-hard if $\Pi' \propto\_{\mathit{poly}} \Pi$ for every $\Pi'$ in NP.
2. A problem $\Pi$ is NP-complete if $\Pi$ is NP-hard and $\Pi$ is in NP.

---
Tags: np-complete
---


# Question
Title: Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?
Given a self-balancing binary search tree of size $n$, I want to perform the following operations:

1. `InsertInOrderSequentialBatch` an ordered sequence of $k$ values (specialized $k \in \\{2, 3, 4\\}$ or generalized $k \in N $) which are guaranteed to be sequential in an in-order tree traversal immediately after insertion.

* For example, insert $\[310, 320, 330, 340\]$ into a balanced tree containing $\[100, 200, 500\]$.
    * Future insertions might still be between the inserted nodes' values.
2. `DeleteRange` all of $k$ nodes (likewise specialized or generalized) between 2 values in the BST.

For both operations, I want the tree to remain balanced.

With a Red-Black or AVL tree, I can achieve both operations through a sequence of $k$ insertions/deletions in $\mathcal{O}(k \log n)$, but wonder if a data structure (e.g. AVL/RB tree variant) could achieve $\mathcal{O}(\log n + k \log k)$ time for a real-world performance gain (e.g. traverse tree for insertion point, insert balanced tree into insertion point, perform one auto-balance pass)?

My needs are less theoretical and more in terms of wall-time & memory pressure for an implementation of Fortune's Algorithm - an algorithm with high constant-time multipliers is unfortunately not useful. My insertion sequence is biased & frequently multimodal (modes not known prior) with long streaks of insertions/deletions within modes. My tree size is anywhere from 100 to 3000 nodes.

# Answer
> 2 votes
This can be solved with `split` and `join` operations, both achievable in $\mathcal{O}(\log n)$ for Red-Black and AVL trees.

For Red-Black Trees this is doable either leveraging finger trees or via extending a regular Red-Black Tree as in Ron Wein's "Efficient Implementation of Red-Black Trees with Split and Catenate Operations" implemented in CGAL with criticisms mentioned in https://stackoverflow.com/questions/29029894/red-black-tree-split-concatenate-in-logn-time (Tarjan might have a better paper).

For AVL trees this is doable according to Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory".

`InsertInOrderSequentialBatch` is expressable as a split followed by 2 joins. `DeleteRange` is 2 splits followed by 1 join.

# Answer
> 0 votes
Red-Black tree insertion requires an amortized O(1) recolorings and rotations; if you know where to insert, doing so and rebalancing is O(1). Therefore multi-insertion can be achieved via a single O(logN) search followed by k amortized O(1) insert-successor-and-rebalance operations, since it is possible to implement insert-successor-and-rebalance such that the new node's Black Height is always \<= 2, which bounds the next search to a constant time.

Alternatively, but more complex, if blackHeight(treeN) \> blackHeight(treeK), insertion can be done in log(n/k)+k time: treeify k values, then insert the tree k into tree n at a leaf and "pull" it upward to maintain black height invariants. This is very similar to implementing a split-join.

For my personal code, I'm doing the O(logN + k) approach first described if k's tree is smaller in black height than N's. Otherwise, I suspect that past some threshold the split-join approach is going to be faster.

---
Tags: algorithms, data-structures, balanced-search-trees, avl-trees, red-black-trees
---


title: Turing machine for $0^{3^k} 1^{p}$

text:
# Question
Title: Turing machine for $0^{3^k} 1^{p}$
Hey guys so I picked up Introduction to the Theory of Computation and started studying finite automata and Turing machines. I was given the following language as an exercise in class, in which I need to build a Turing machine with only one tape and no extra tape space that accepts the following language:

$$\\{0^{3^k} 1^p, \text{ where $k \> 0$ and $p$ is a multiple of $k$}\\}$$

How can one build a single tape Turing machine that accepts this kind of language without using any extra tape space?

I found an example for $\\{0^n 1^n\\}$ in Introduction to the Theory of Computation but I cannot figure out how to build a machine for the language mentioned above.

# Answer
> 4 votes
This problem can be solved in two steps. First, you need to work out the $k$ by repeatedly "dividing" the string by $3$, and storing how many times this was repeated. For example, each "division" will process the zeros in triplets. Each triplet will replaced by one zero, and in the first triplet processed you store a "1", as an indicator that you performed one division (since after erasing the first triplet you will have the space to store this "1"). Then you have to bring all the new zeros together and repeat the procedure. The number of ones you have written will be equal to $k$ (and if at some point you cannot perform the division, that is you don't have a power of three - you reject the language).

Next, you begin erasing the ones that come after zeros. Each turn will consist of wiping out exactly $k$ ones - for example the $k$ ones that you have on the left can be replaced by zeros in order to indicate that a one on the right has been erased. At the end of the turn, you replace all the zeros by ones again. Again, if you cannot perform the whole round, you must reject the language.

# Answer
> 4 votes
Just for fun, I've constructed the TM sketched by Rodion, you can simulate its behaviour here. Observe that I assume $p$ (or $m$, which is the same) strictly positive; moreover one actually has to use two cells outside the input, namely the cell immediately to the left of the first symbol of the input and the one immediately to the right of the last symbol of the input.

---
Tags: algorithms, turing-machines
---


# Question
Title: Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n)
Two sorted arrays of positive integers, X\[\] and Y\[\] are given.But, the array sizes are unknown to us. We may assume that accessing any index beyond the last element of the array returns -1. The elements in each array are distinct but the two arrays may have common elements. An intersection point between the two arrays is an element common to both the arrays, i.e., p ( p\>0 ) be an intersection point if there exists i,j such that X\[i\]=Y\[j\]=p

Given a positive integer q, how can we design an algorithm ( in pseudocode ) to check if q is an intersection point between X and Y **in strictly less than O(n) time complexity**.

> I proceeded by thinking of applying binary search on both the arrays X and Y, since they are sorted and trying to find if q exists in both of them. But not knowing the lengths leads me astray.

Could anyone please help me with this ?

# Answer
We need to first find the length of array in long time as it is not given.

1. Start with length as 1 and increase it as multiple of 2.
2. Check whether element at length-1 position is positive or not.
3. If so repeat steps 1 and 2.
4. If not return the index position it will be the maximum size of the array. As it is mentioned beyond the maximum position element value is negative.
5. Once the length of array is known simple binary search alto will be applied to search element and it will be searched in both the array and intersection point will be determined.
> 1 votes

---
Tags: algorithms, complexity-theory, arrays, pseudocode
---


# Question
Title: Understanding N process Peterson's algorithm
The intuitive informal description of two process Peterson's algorithm for process 0 can be given as follows:

```
flag[0]=true;                   //I am ready to enter my critical region
turn=1;                         //but you may take your turn to enter your critical section

while(flag[1]==true && turn==1) //if you are ready to enter your critical section
                                //and if its your turn,
{ }                             //I will wait

//Critical Section

flag[0]=false;                  //I am no more ready to enter my critical section

```

Peterson's algorithm for n processes is given as follows:

Each process runs the following pseudo code:

```
lock(pid);
<critical section>;
unlock(pid);

```

where `lock()` and `unlock()` functions are defined as below..

```
lock(for Process i):

/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
    flags[i] = count;
    turn[count] = i;
    "wait until (for all k != i, flags[k]<count) or (turn[count] != i)"
}

Unlock (for Process i):

/* tell everyone we are finished */
flags[i] = -1;

```

Now I want to understand the n process Peterson's algorithm in same intuitive way, but I am unable to bring such informal explanation for it. To be precise I want to know the following:

1. In 2 process Peterson's algorithm, `flag[i]=true` means "process i is ready to enter its critical section". What does it mean in n process algorithm when `flag[i]=true`
2. In 2 process Peterson's algorithm, `turn=1` means "its process 1's turn to enter its critical section". What does it mean in n process algorithm when `turn[i]=x`
3. How can we intuitively / informally describe the line:

```
 "wait until (for all k != i, flags[k]<count) or (turn[count] != i)"

```

# Answer
> 2 votes
The way the N-process Peterson's algorithm works is slightly different than how the 2-process version is presented above. We can reason about the N-process version a little more like this:

When a process wants to start running (i.e.: executes lock()), it imagines that it's joining an imaginary queue of processes. It doesn't know exactly how many processes are in the queue nor exactly what position in the queue it is in (because of the vagaries of concurrency). It does know that the queue can only have N possible positions because there are N total processes. The goal is for to only allow a process to exit the lock() procedure once it is sure that it is at the head of the queue.

To keep the notation consistent with the pseudocode listed above, we'll say that position 0 is the tail (back) of the queue, position N-1 is the head (front) of the queue, position N-2 is second from the front, etc... , and position -1 means you're not in the queue at all (i.e.: has not executed lock()).

What each process does is it makes an estimate of what its potential position is in this queue and declares that it is the most recent process to estimate that it is in that position (if that position is not -1). Initially, when a process first starts the lock() procedure, it will of course estimate that it is at the back of the queue (i.e.: position 0). These estimates of where each process thinks it is in the queue and who is the most recent process to think they are in each position is shared information. In the pseudocode the position estimates per process are stored in the `flags` array and the list of most recent process per position is in the `turn` array.

Then, each process looks around at this shared information to see if it can update its estimate of where it is in the queue. These updates can only move a process's estimate one position forward in the queue (i.e.: closer to the head). You can update your position in two situations: 1) if another process comes later than you and thinks it is in the same position as you, 2) if everyone else thinks they're strictly behind you. Whenever you see one of these situations happen, you can update your estimate of your position to move one step toward the head.

```
lock(for Process i):

/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
    flags[i] = count;                 // I think I'm in position "count" in the queue
    turn[count] = i;                  // and I'm the most recent process to think I'm in position "count"

    "wait until                       // wait until
     (for all k != i, flags[k]<count) // everyone thinks they're behind me
     or (turn[count] != i)"           // or someone later than me thinks they're in position "count"

                                      // now I can update my estimated position to "count"+1

 }                                    // now I'm at the head of the queue so I can start my critical section

Unlock (for Process i):

/* tell everyone we are finished */
flags[i] = -1;                        // I'm not in the queue anymore

```

As noted before, this is slightly different than the presentation of the 2-process version as given above. However, we can reframe that presentation in this framework easily with only some slight modification. Note that in the 2-process case, the queue only has two potential positions, the head (position 1) and the tail (position 0) of which only position 0 is explicitly claimed.

```
flag[0]=0;                   // I am at the tail of the queue
turn=0;                      // and I am the most recent process to join the queue

while (flag[1]==0            // while you are in the queue
    && turn==0)              // and I joined the queue later than you did
  { }                        // I will wait

//Critical Section

flag[0]=-1;                  // I am no longer in the queue

```

# Answer
> 1 votes
I'm late to the party but I suppose I can offer my intuition on this. I think of it as a race between threads. The race consists the number of laps = #threads-1. The idea is after each lap, 1 thread is left behind, so at the end of the race, only 1 thread is guaranteed to come out on top.

From the perspective of each thread, it looks like below (the comments).

For lock:

```
lock(for Process i):
    for (count = 0; count < (NUMPROCS-1); count++):    // For each lap/iteration:
        flags[i] = count;                              // Update where I'm at right now.
        turn[count] = i;                               // Ring the bell to get my turn.
        wait until (for all k != i, flags[k] < count)  // If I'm the furthest in the race (highest iteration),
                or (turn[count] != i);                 // or I'm not the last to ring the bell in my current lap,
                                                       // then I can proceed to the next lap, else I'll just wait

```

For unlock:

```
unlock(for Process i):
    // I'm done with the race. Let the next guy be on top.
    flags[i] = -1;
    // Imma do sth else now, but I might come back later tho.

```

---
Tags: operating-systems, concurrency, synchronization, critical-section
---


# Question
Title: Comparisons of functions, their big-oh and their implications
I don't understand why the $1^{st}$ is false but I think I see why the $2^{nd}$ is true.

1. If $f(n) = O(n^2)$ and $g(n) = O(n^2)$, then $f(n) = O(g(n))$.
2. If $f(n) = O(g(n))$ and $g(n) = O(n^2)$, then $f(n) = O(n^2)$.

I understand why the second is true but not the $1^{st}$. For case 1, if

* $f(n) \< c\_1n^2$ for some $n \> n\_1$ and
* $g(n) \< c\_2n^2$ for some $n \> n\_2$

by using constants instead of big-O notation , can't we find $c\_3$ such that $f(n) \< c\_3g(n)$ for some $n \> n\_3$ ?

# Answer
As a counterexample you can take $f(n)=n$ and $g(n)=\sqrt{n}$. You can think that $f(n)=O(n^2)$ means that an upper bound for $f(n)$ is $n^2$ (of course, without considering multiplicative constant), so the fact that both $f$ and $g$ are bounded by $n^2$ does not implies nothing about the relative behavior of $f$ and $g$.
> 1 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round?
Found this in solutions of a test as being true

> If you can square an n-bit integer in time $O(n \\,log \\,n)$, then you can multiply two n-bit integers in time $O(n \\, log \\,n)$.

How does the above scenario apply for multiplying different numbers? Isn't it possible that squaring is a special operation since it is just 1 number? . I would see this making sense.

> If you can multiply two n-bit integers in time $O(n \\, log \\,n)$, then you can square an n-bit integer in time $O(n \\,log \\,n)$.

# Answer
Of course, we can suppose we are able to do sum and difference in linear time. Now, if we want to calculate $h\cdot k$, we can find in linear time $a$ and $b$ such that $h=a-b$ and $k=a+b$: take $a=\frac{k+h}{2}$ and $b=\frac{k-h}{2}$. Then $h\cdot k=(a-b)(a+b)=a^2-b^2$, so we only need to square two numbers of at most $n$ digits (if $h$ and $k$ have $n$ digits, then also $\frac{k+h}{2}$ has at most $n$ digits) in $O(n\log(n))$ and take their difference in $O(n)$.

Actually, this works if $h$ and $k$ have the same parity, else $a$ and $b$ are not integers; if it is not the case, then you can write $h\cdot k=h\cdot(k-1)+h$ and proceed as above.
> 1 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: How can I do a subtraction with a two tape Turing machine
I have already made a Turing machine with just one tape that solves a subtraction between two numbers, but I trying to do the same but with TWO tapes.

As an example, how can I solve 4-2?

Taking account that 4 can be represented as 0000, 2 as 00 and the - as 1.

So, in this case the input will be 0000100.

# Answer
> 2 votes
Copy the second number (from the second tape) to the first tape, and then use the already existing TM that subtracts the numbers

---
Tags: turing-machines, arithmetic, turing-test
---


# Question
Title: Why do we need hashed page tables for Paging in Operating Systems?
I understand that we might need hierarchical paging to handle page tables with sizes greater than the size of one frame, but what is the use of Hashed Page tables then? I would understand if we were storing page-numbers and mapped frame numbers as $key-value$ pairs, because then hashing would make the process of accessing a particular $key-value$ pair much faster but can't we just store the base of the page table and add the virtual page number, go to that index of Page Table, and get the frame number anyway?

# Answer
There are several advantages of hashed page tables over the standard flat/hierarchal page tables. One of these being size, a hashed page table will use less space in memory than using a flat or hierarchal page table. It will at most have one entry for every physical frame (worst case scenario; unlikely as many page numbers will end up having same hash value) instead of having an entry for every page (many of which will be left unused; although this problem is alleviated with the use of hierarchal page tables). Inverted page tables also have this advantage, however hashed page tables have a performance advantage over inverted tables, as the lookup is much faster in hashed page table. So a hashed page table combines the space advantage of an inverted table with the lookup advantage of a standard page table.
> 2 votes

---
Tags: operating-systems, hash-tables, paging
---


title: BNF syntax for a recursive function?

text:
# Question
Title: BNF syntax for a recursive function?
I'm to write a syntax that will allow for a recursive function, i.e.

```
f(x) = if x == 0 then x else f(x+1)

```

Here's one attempt at creating the grammar:

But I don't think this is right since there's no such thing as parameterized syntax.

# Answer
> 1 votes
Are you aiming to simply allow recursive functions or specify only recursive functions. The following grammar allows recursive functions:

```
function      := id '(' parameter ')' '=' function_body ;
function_body := conditional
               | expression
               ;
expression    := function_call
               | <other expression types>
               ;
function_call := id '(' parameter ')' ;

```

Specifying only recursive functions would require a context-aware grammar (BNF is context-free). You can approach the problem outside of the grammar specification though and check for recursive functions later in your parser / compiler pipeline.

Checking for recursion outside of the grammar allows you to more easily identify cyclic recursion (not just `f` calling `f` but something like `f -> a -> b -> c -> f`).

---
Tags: formal-grammars, programming-languages, compilers, parsers, syntax
---


# Question
Title: Python versus Matlab on the quantity 1/0
Python and Matlab seem to disagree on the division by 0.

Python:

```
>>> 1 / 0
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: division by zero

```

Matlab:

```
>>> 1 / 0
Inf

```

with the usual properties of $\infty$ for Inf.

Which one is correct when it comes to the IEEE double-precision format?

# Answer
> 3 votes
In the copy that I have of IEEE 754 (2008) it says

> 7.3 Division by zero 7.3.0
>
> The divideByZero exception shall be signaled if and only if an exact infinite result is defined for an operation on finite operands. The default result of divideByZero shall be an ∞ correctly signed according to the operation:
>
> ― For division, when the divisor is zero and the dividend is a finite non-zero number, the sign of the infinity is the exclusive OR of the operands’ signs (see 6.3).
>
> ― For logB(0) when logBFormat is a floating-point format, the sign of the infinity is minus (−∞).

Python is choosing that the exception that the standard requires is a Python exception. My own interpretation is that this agrees with section 7.3. We don't get the value `float('inf')` because the exception interrupts the execution. I personally find it a bit inconvenient. I don't know the reasons they had for this choice.

One can get the behavior of obtaining a value by using `numpy`. With

```
x = numpy.float64(1.0)/numpy.float64(0.0)

```

we get

```
x = numpy.float64('inf')

```

and a `RuntimeWarning`. Alternatively, one can capture the exception `ZeroDivisionError` and produce the result `float('inf')` ourselves.

In Matlab we get `inf` as the result. It agrees with the standard because I think there is a warning (a flag) that can be seen by setting `warning on MATLAB:divideByZero`.

# Answer
> 2 votes
Matlab gives infinity because it's working directly with floats. IEEE754 floats attempt to let errors propagate through a computation instead of immediately crashing a program when something such as division by zero is encountered.

Python division, whether integer or float (`1/0`, `1.0/0.0`, `1//0`), all have special checks for integer division at the software level (e.g.).

There's a fundamental problem with integer division by zero: the hardware generates a hardware arithmetic fault that's difficult to recover from. As to why Python doesn't allow float division by zero either, I can only speculate about the design decision. It may be to help the user catch mistakes in computations closer to the sources. To avoid this, you can use a numpy float or alternative which doesn't add this extra check.

---
Tags: floating-point, python
---


# Question
Title: Definition of Closed Under Left Polynomial Composition
I am studying Computation complexity using Papadimitrious's book: "Computational Complexity". While doing Problem 7.4.4, I came across the definition of what it means for a class of functions $C$ to be closed under left polynomial composition.

Here is Problem 7.4.4:

> "Let $C$ be a class of functions from nonnegative integers to nonnegative integers. We say that $C$ is **closed under left polynomial composition** if $f(n) \in C$ implies $p(f(n)) = O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$. We say that $C$ is closed under right polynomial composition if $f(n) \in C$ implies $f(p(n)) = O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$.
>
> Intuitively, the first closure property implies that the corresponding complexity class is "computational model-independent", that is, it is robust under reasonable changes in the underlying model of computation (from RAM's to Turing machines, to multistring Turing machines, etc.) while closure under right polynomial composition suggests closure under reductions (see the next chapter).

My doubt is what is the correct way of interpreting this definition and proving that a given class of functions $C$ is closed under left polynomial composition. The definition got me confused since the part "for all polynomials $p(n)$" appeared after the part "for some $g(n) \in C$". I thought about two interpretations.

1. Given arbitrary $f(n) \in C$ and $p(n)$, exhibit some $g(n) \in C$ such that $p(f(n)) = O(g(n))$. Then, you have proved that $C$ is closed under left polynomial composition. I think this makes more sense, since by this definition I was able to prove that the class $C = \\{n^k: k \> 0 \\}$ is "computational model independent", which makes sense to me.
2. Given an arbitrary $f(n) \in C$, exhibit some $g(n) \in C$ such that for all polynomials $p(n)$ we have that $p(f(n)) = O(g(n))$. While assuming this definition, I gave a counterexample and proved that the class $C = \\{n^k: k \> 0 \\}$ is NOT "computational model independent", which sounds awkward to me.

Which interpretation is the correct one?

Thanks in advance.

# Answer
The correct interpretation is as follows. A class $\mathcal{C}$ is closed under left polynomial composition if the following holds:

> For any $f(n) \in \mathcal{C}$ and any polynomial $p(n)$ there exists $g(n) \in \mathcal{C}$ such that $p(f(n)) = O(g(n))$.

In particular, the class $O(n)$ isn't closed under left polynomial composition.

Why are we interested in this definition? Here is an example. We can convert a $k$-tape Turing machine running in time $T(n)$ into a single-tape Turing machine running in time $5kT(n)$, see this question. If we start with a multi-tape Turing machine running in linear time, we don't necessarily end up with a single-tape Turing machine running in linear time. But if we start with a multi-tape Turing machine running in polynomial time, then we do end up with a single-tape Turing machine running in linear time. It thus makes sense that $O(n)$ isn't closed under left polynomial composition, but $n^{O(1)}$ is.
> 1 votes

---
Tags: complexity-theory, closure-properties
---


# Question
Title: Reverse An Array whats wrong with this type of code?
```
import java.io.*;
import java.util.*;
public class reverseAnArray2
{
    public static void main(String args[])throws IOException
    {
        Scanner sc  = new Scanner(System.in);
        System.out.println("Enter size");
        int  n = sc.nextInt();
        int a [] = new int [n] ;
        int b [] = new int [n] ;
        System.out.println("Enter elements");
        for(int i=0;i<n;i++)
        {

            a[i]=sc.nextInt() ;
        }
        int size = n;
        System.out.println("Reverse array is : ");
        int p=0;
        while(n>=0 && p<n)
        {

            a[--n] = a[p] ;
            ++p;
        }
        for(int i =0;i<size;i++)
        {
             System.out.println(+ a[i]);
        }

}
}

```

The output comes correct but only up to the last $n/2$ terms, rest of it gets repeated. The output was correct when I used another fresh array to store data. But that's not an optimal code. I want to reverse it without using another array.

# Answer
> 0 votes
Notice that you increment $p$, whilst also decrementing $n$. Since your condition in the `while` loop is that `p < n`, then the while loop will only work for half the elements.

Also, note that you delete the last $n/2$ values, since you modify them without first reading them.

---
Tags: data-structures, arrays
---


# Question
Title: dynamic programming: longest palindromic subsequence, recurrence relation question
Moving from top left down the column then over to the right column, taking ideas from here: https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/ I want to restate the question at the top of the Excel table. Why do I need to max from T(i,j-1) and T(i+1,j)? Can't you just take what's in T(i,j-1)?
I changed the input slightly and I still get the right answer just taking T(i,j-1) when T(i,0) != T(0,j)

Edited:

A counterexample would be nice to see.

# Answer
> 1 votes
### Let `T(i,j) = T(i,j-1)` when `L(i) != L(j)`

You could be wrong if you take `T[0, n-1]` as the final answer as in the article on GeeksforGeeks. For example, let `X = "abb"`. Then `T[0, n-1] = 1` while the longest palindromic subsequence is `bb` with length 2.

You are right if you take the maximum of `T[i,n-1]` as the final answer, where `i` goes through all valid indices, i.e., from `0` to `n-1` and `n` is the length of the given string `X`.

What is happening?

We need to understand/specify the meaning of `T(i,j)`. We can let `T(i,j)` denote the length of the longest one among all subsequences that **start at index `i` and end no later than index `j`**, where `i <= j`. Then it is correct that `T(i,j) = T(i,j-1)` when `X(i) != X(j)`, since any palindromic subsequence that start at index `i` cannot end at index `j`, i.e., it must end no later than index `j-1`.

### Exercise

1. Describe the meaning of `L(i,j)` in that GeeksforGeeks article.
2. Suppose we let `T(i,j)` denote the length of the longest one among all subsequences that **start at index `i` and end at index `j`**, where `i <= j`.

* What will be the recurrence relations?
    * Suppose we have computed all `T(i,j)`. What would be the final answer, i.e., the length of the longest palindromic subsequence overall?

---
Tags: dynamic-programming
---


# Question
Title: Proof of $f(n) + ο(f(n)) = \Theta(f(n))$
Can you please help me prove this? I am trying to set $o(f(n))= g(n)$ and then try to solve the equation $f(n) + g(n) = \Theta(f(n))$ but I don't know if it is the correct way, and if it is I don't know how to continue my solution. Thank you

# Answer
Obviously, $f(n)+o(f(n))=\Omega(f(n))$ (clearly, I'm assuming all functions being positive), so you need only to prove that $f(n)+o(f(n))=O(f(n))$. But a function in $o(f(n))$ is definitevely smaller than $f(n)$, so for sufficient large $n$ you have $f(n)+o(f(n))\leq 2f(n)=O(f(n))$.

Actually, in the same way you can easily prove also this stronger claim: $f(n)+O(f(n))=\Theta(f(n))$.

---

If $h(n)=o(f(n))$, then $\lim\_{n\to+\infty} \frac{h(n)}{f(n)}=0$, so there exists $n\_0$ such that for all $n\geq n\_0$ you have $h(n)\leq f(n)$ (actually, we can prove a stronger statemen, namely that for all $\varepsilon\>0$, we have $h(n)\< f(n)$, but here we not need it). This means that for all $n\geq n\_0$ you also have $f(n)+h(n)\leq 2f(n)$, and then $f(n)+h(n)=O(f(n))$.

---

---

If you don't want to explicitely assume positiveness of the functions involved; I suggest to use limits (I like limits).

Remember that $f(n)=O(g(n))$ means $$ \limsup\_{n\to+\infty} \frac{|f(n)|}{g(n)}\<+\infty $$ while $f(n)=\Omega(g(n))$ means $$ \liminf\_{n\to+\infty} \frac{|f(n)|}{g(n)}\>0 $$ (use $|g(n)|$ instead of $g(n)$ if you want to take into account also negative functions). Notice that I'm not assuming that $\lim\_{n\to+\infty} \frac{f(n)}{g(n)}$ exists, indeed $\liminf$ and $\limsup$ are used to deal with this case. Now, as above, let $h(n)$ be an $o(f(n))$, e.g. $\lim\_{n\to+\infty} \frac{h(n)}{f(n)}=0$.

Finally $$ \limsup\_{n\to+\infty} \frac{|f(n)+h(n)|}{|f(n)|}\<\limsup\_{n\to+\infty} \frac{|f(n)|+|h(n)|}{|f(n)|}=\limsup\_{n\to+\infty}\left( 1+\frac{|h(n)|}{|f(n)|}\right)=1\<\infty $$ while $$ \liminf\_{n\to+\infty} \frac{|f(n)+h(n)|}{|f(n)|}=\liminf\_{n\to+\infty} |f(n)|\cdot\frac{\left|1+\frac{|h(n)|}{|f(n)|}\right|}{|f(n)|}\geq 1\>0. $$ Also observe that in the first limit, we only need $\limsup\_{n\to+\infty} \frac{|h(n)|}{|f(n)|}$ to be finite, so $h(n)$ can be also a $O(f(n))$.
> 3 votes

# Answer
It's widely known, that $f=\Theta(g)$ we understand as "one direction" equality i.e. $f \in \Theta(g)$. But when we write something like $\Theta(f) = \Theta(g)$, then situation becomes slightly different: now it is equality between sets, so need proof in "two directions".

Equality $f+o(f)=\Theta(f)$ formally considered as equality between sets requires to be proved two facts $f+o(f) \subset \Theta(f)$ and $\Theta(f) \subset f+o(f) $. As first is shown in another answer, then let's concentrate on later:

Obviously $2f \in \Theta(f)$, but $2f \notin f+o(f)$, because $f \notin o(f)$.

So, we can write only $f+o(f) \subset \Theta(f)$ and as elaboration $f+o(f) \neq \Theta(f)$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Time complexity of finding median in data stream
I was reading a solution to the problem in the title on leetcode and the article says that the time complexity of the following solution is O(n)

1. setup a data structure to hold stream value and insert new element in the right place using linear search or binary search
2. return median

my solution is as follows:

```
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.arr = []

    def addNum(self, num: int) -> None:
        idx = bisect.bisect_left(self.arr, num)
        self.arr.insert(idx, num)

    def findMedian(self) -> float:
        # self.arr.sort()
        if len(self.arr) % 2 != 0:
            return self.arr[len(self.arr)//2]
        else:
            return (self.arr[len(self.arr)//2 -1] + self.arr[len(self.arr)//2 ])/2

```

My question is about the time complexity of the push method. the binary search will take O(log n) to find the index. the insert will take O(n). but since the method will be called on the stream, will the complexity be O(n^2) or O(n) ?

# Answer
> 1 votes
From a brief look at Leetcode streaming problem solutions, the complexity solutions provided for streaming problems refer to the time complexity of a single iteration for the stream i.e. after $n$ elements in the stream, what is the complexity of updating the data structure and answering a query with a new element?

---
Tags: algorithms, time-complexity
---


# Question
Title: Why does the Java grammar have a StatementExpression that resolves to just Expression? Why have this and other redundant rules in the grammar?
I'm looking at the following grammar rules for the Java language described on the Oracle docs:

```
Statement:
    ...
    if ParExpression Statement [else Statement]
    StatementExpression ;
    ...

StatementExpression:
    Expression

ParExpression:
    ( Expression )

```

I don't understand why the StatementExpression rule is present at all. I also don't understand why ParExpression had to be written as a separate rule.

Why couldn't the grammar just look like the following?

```
Statement:
    ...
    if ( Expression ) Statement [else Statement]
    Expression ;
    ...

```

# Answer
> 7 votes
**StatementExpression** is described in the same specification document as Expression Statements. I would like to quote this passage specifically:

> Certain kinds of expressions may be used as statements by following them with semicolons.
>
> ```
> ExpressionStatement:
>     StatementExpression ;
>
> StatementExpression:
>     Assignment
>     PreIncrementExpression
>     PreDecrementExpression
>     PostIncrementExpression
>     PostDecrementExpression
>     MethodInvocation
>     ClassInstanceCreationExpression
>
> ```

and this:

> Unlike C and C++, the Java programming language allows only certain forms of expressions to be used as expression statements.

**ParExpression** is described as **Parenthesized Expressions** and Primary Expressions.

> A parenthesized expression is a primary expression whose type is the type of the contained expression and whose value at run time is the value of the contained expression. If the contained expression denotes a variable then the parenthesized expression also denotes that variable.
>
> The use of parentheses affects only the order of evaluation, except for a corner case whereby (-2147483648) and (-9223372036854775808L) are legal but -(2147483648) and -(9223372036854775808L) are illegal.

About your question:

> Why have this and other redundant rules in the grammar?

They are not redundant, that is a mistake in the document, **they are different** types of expressions. See the grammar for the next version:

```
StatementExpression:
  Assignment
  PreIncrementExpression
  PreDecrementExpression
  PostIncrementExpression
  PostDecrementExpression
  MethodInvocation
  ClassInstanceCreationExpression

```

# Answer
> 6 votes
Edit: previously incorrect.

Chapter 18 does not have the correct definition of `StatementExpression`. The correct definition can be found in 14.8. StatementExpression is a subset of the expression grammar.

Justification for statement expression: In java, the statement `1 + 1;` is invalid grammatically (unlike most other languages).

---
Tags: formal-grammars, compilers
---


# Question
Title: FA for when length of $w$ is $4$ or $w$ contains the substring $01$
I have been trying to create an FA for the language.

$\\{w \in \\{0, 1\\}^∗ , |w|= 4 \vee w \text{ contains the substring }01\\}$

I created one that accepts words that contain the substring $01$, but I have a hard time finding a solution for the length part.

This is my attempt so far:

Any help is greatly appreciated.

# Answer
> 0 votes
The easiest way to construct a deterministic automaton for such a language is to use the product construction:

1. Construct an automaton for all words of length $4$.
2. Construct an automaton for all words containing the substring $01$.
3. Use the product construction to construct an automaton for the union.

If you are allowed to use a nondeterministic automaton, then you can replace the product automaton with a "union automaton", that is, add a new initial state and connect to the the initial states of the two automata with $\epsilon$ transitions.

---
Tags: finite-automata
---