# Question
Title: Memory addresses requested by CPU vs Memory Address Provided to DRAM
So, i just got through studying DRAM architecture. I learned that a row address, column address, bank number etc are provided to the DRAM during a read operation. Based on the address provided, 64 bits will be transferred back to the memory controller (assuming the data bus is 64 bits wide). So if we have 8 DRAM chips, each will contribute 8 bits to the data bus. Basically a single memory address (consisting of a row address, column address etc.) corresponds to 64 bits in the DRAM.

But then i came across the fact that most modern computer memory is byte addressable? So the CPU can request a single byte of data rather than a 64 bit chunk as is output by DRAM.

I'm not sure how to reconcile the two pieces of info. Can someone please clarify how addressing works? So if the CPU requests the byte at a certain address, how is that translated into a row address and column address to get the requested byte from DRAM, since a row and column address in DRAM returns 64 bits and not a single byte?

# Answer
Simple. If the software requests a single byte the processors memory subsystem will request the 8 bytes contains this byte.
> 1 votes

---
Tags: computer-architecture, memory-management, cpu
---


# Question
Title: Difference between product automaton vs. NFA with epsilon transitions
Let $L\_1, L\_2$ be regular languages. You can proof with a product automaton that $L\_1\cup L\_2$ is also regular. But you can also construct a NFA. Since $L\_1, L\_2$ are regular, they also have an NFA representation $M\_1, M\_2$. You can create a NFA with a start state $q\_0$ with one edge each to the start states of $M\_1,M\_2$ with an epsilon transition.

So I wonder what is the difference, advantages and disadvantages?

Thx!

# Answer
> 4 votes
Both constructions work. The advantages of using NFAs is that they allow easier constructions, especially for languages that can be naturally specified using existential quantifiers. So if we only care about proving whether some language is regular, then easy design wins. As you've wrote, putting two automata next to each other and guessing which automaton to run on the input word is a straight-forward construction compared to the product construction, and indeed, in this case we want to check whether there **exists** an automaton (one of the two automata that we started with) that accepts the input word: the construction simply **guesses** which automaton to run on the input.

Another classical example is closure of regular languages under concatenation, where we want to check whether there **exists** a partition of the input word into two words such that the first word is accepted by one automaton, and the second word is accepted by the other automaton. Here, we guess while reading the input word when we branch and run the second automaton on the suffix to be read. Also, many more examples exist where NFAs allow for conceptually easier constructions. Its just that existential properties and NFAs work well with each other due to the existential semantics of nondeterminism: a nondeterministic automaton accepts an input if there **exists** a run of it on the input.

The disadvantages of such constructions is that while they are conceptually simple, they do not necessarily preserve determinism. So while nondeterminism allows more elegant designs, we prefer constructions that end up with deterministic automata (preferable small ones) since decision procedures about deterministic automata are considebraly easier than decision procedures about nondeterministic automata: language containment, minimization, etc, are all in PTIME for deterministic automata, yet PSPACE-complete for nondeterministic ones. In this sense, the product construction is better as it preserves determinism (the product of deterministic automata is deterministic) and results in an automaton of quadratic size (which is at most polynomial in the two automata that we started with -- good!).

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


title: Quick sort with $K-1$ pivots

text:
# Question
Title: Quick sort with $K-1$ pivots
I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of unique numbers into $k$ classes? My goal is to demonstrate that this multiary partitioning can be achieved in $O(n \log k)$ time, ensuring that all classes are approximately of the same size (to within 1).

I found this paper https://cs.stanford.edu/~rishig/courses/ref/l11a.pdf

but it doesn't seem to talk about how to go about partitioning the array into nearly equal. Note: I am just interested in selecting the pivots not the partition algorithm

I did try finding the $n/k^{\text{th}}, 2n/k^{\text{th}} \ldots$ smallest element in the array and using them as pivots but the complexity isn't coming right (as each element can be found using BFPRT algorithm in $O(n)$ therefore total complexity would be $O(nk))$
Any Insights will be appreciated.

# Answer
> 1 votes
Hint: Suppose $k$ is a power of two at first, for simplicity. Find the $n/2$th element in the array. Then.... (you fill in the next part)

---
Tags: algorithms, algorithm-analysis, quicksort, divide-and-conquer, selection-problem
---


# Question
Title: $F(n, L) = 2F(n / 2, L) + nL + n^2 log(n)$ and Master Theorem
I have the following recurrence: $F(n, L) = 2F(n / 2, L) + nL + n^2 log(n)$. Am I correct in saying that $F(n, L) \in O(n \log(n) L + n^2 log(n))$? I got to this result by bounding the $nL$ and $n^2 \log(n)$ parts separately. Thank you!

# Answer
> -1 votes
You don’t really need the master theorem. If n = 2^k then the result is \<= 2 n^2 k + n k L.

---
Tags: runtime-analysis, master-theorem
---


# Question
Title: Solving recurrence by iteration, choosing base case
A question I am to answer wants me to find the big O of a recurrence, I am doing it with the iteration method. For the base case, which we get after applying the recurrence $i$ times, can we make this any number as long as we assume it will be in constant time? Such as $T(5)$, $T(100)$ etc. I can't give anymore info to the question as it's an assignment. Thanks

# Answer
Well, obviously $T(1),T(2),\dots,T(100)$ are all integers. So, let $c=\max(T(1),T(2),\dots,T(100))$. $c$ is obviously some integer, so it is a constant. So yes, all of those base cases are at most a constant.

In practice, we often assume that $T(1)=1$, as usually multiplying it by a small constant doesn't change anything about the asymptotics (though of course there are strange cases where this might not hold).
> 2 votes

# Answer
If you have a recurrence that doesn’t apply to the case n = 1, then it would be correct to assume T(1) = c, for some unknown c, and resolve the recurrence based on that; this would be useful if you are interested in actual and not just asymptotic values.

Or you can say that T(1) is O(1) and go from there. If the recurrence is problematic for small n, then you can also assume for example max (T(1), T(2), …, T(100)) = O(1).
> 1 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Batch rounding with preservation of a sum
I have a sequence of floating point numbers. I want to map each of them to one of their closest integers. There is one rule:

Sum of integers must be as close to the sum of original numbers as possible (ideally sum of integers is a rounded sum of originals).

You can think about it as of snapping to grid some bar plot with preserving its total area.

# Answer
There are many rounding methods that round an integer to the nearest integer, all of which are the same except on the half-integers. The sum of integers returned will be close to the sum of the original numbers on average when the distribution of the fraction parts of the numbers are roughly symmetric to $0.5$. One of those methods might be good enough for you in practice.

However, none of them will ensure the rule for sum, "the sum of output integers must be as close to the sum of original numbers as possible". For example, the nearest integer to $0.6$ and $0.7$ is $1$ but the nearest integer to their sum $0.6+0.7=1.3$ is $1$ instead of $1+1 =2$. Hence to satisfy the rule of sum, we cannot guarantee that each integer is mapped to its nearest integer.

Let us pick one of the rounding methods as $\mathcal R$, which will specify the exact meaning of "as close as possible". For methods below, we will ensure that $$\mathcal R(\text{sum of input numbers})=\text{sum of output integers}$$ while trying to round integers to their respective nearest integers fairly.

### Offline Method

Suppose numbers $a\_1, a\_2, \cdots, a\_n$ are given.
Let $\\{a\_i\\}=a\_i-\lfloor a\_i\rfloor$ be the fractional part of $a\_i$ and $s = \\{a\_1\\} + \\{a\_2\\} + \cdots + \\{a\_n\\}$.

* Round down $a\_i$ to $\lfloor a\_i\rfloor$ for $i\le n-\mathcal R(s)$,
* Round up $a\_i$ to $\lfloor a\_i\rfloor + 1$ otherwise.

To be fair, sort $a\_i$ by $\\{a\_i\\}$ before rounding so that, for example, $4.8$ will be rounded up instead of $7.6$ if one of them should be rounded up.

### Online Method

Input: a source that produces numbers
Output: numbers rounded to integers
Procedure:

1. Let number $gap$ be $0$
2. For each number $num$ in the source:
    1. Let $num{\\\_}rounded=\mathcal R(gap + num)$. Output $num{\\\_}rounded$.
    2. Add $num - num{\\\_}rounded$ to $gap$.

### Buffered Method

We can mix the offline method and the online method by repeating the following procedure after initializing $gap=0$.

1. Apply the offline method to the next block of numbers, including $gap$ as a summand for $s$ as well.
2. Add the difference between the sum of the numbers returned in step 1 and the sum of the original numbers to $gap$.

The size of each block of numbers is up to your choice.
> 8 votes

# Answer
A "stateless" approach (i.e. the same value always rounding the same way) *cannot work*. To see why, consider a sum of always the same number. After n terms, the error will equal n times the error between the original and rounded value, and this grows unboundedly.

A simple solution is to use "error propagation", as done in the image dithering algorithms. You just keep the fractional part of the sum, and update it with the fractional part of the next number. If the new fractional part exceeds 1, transfer this unit to the rounded value.

E.g.

```
2.3 + 4.4 + 6.4 + 3.1 ->

2, error = 0.3;

4, error = 0.7;

6, error = 1.1, which becomes 7, error 0.1

3, error = 0.2

```

---

Note that this gives the same output as the simple method of effectively computing the partial sums, rounding to integer and taking the difference with the previous sum (but for accumulation of floating-point errors in the long run).

```
2.3 + 4.4 + 6.4 + 3.1 -> 0, 2.3, 6.7, 13.1, 16.2 -> 0, 2, 6, 13, 16 -> 2 + 4 + 7 + 3

```

---

Note that I used truncation, but rounding also works.

---

**Update:**

If the distribution of the fractional parts is uniform, rounding to the nearest integer will work on average. In practice, this is rarely the case, because of Benford's law, so a bias can be expected. You can determine it experimentally, hoping that your data sets are homogeneous. In the long run, drifts are to be feared anyway.
> 6 votes

# Answer
Yves's answer will give you exactly the answer you are looking for.

An alternative is to use stochastic rounding which will give you the rounded sum *in expectation*, and may have nicer properties for the individual numbers, although you say that is not important.

The idea is to round the number up to the next integer with probability equal to the fractional part of the number, otherwise round down.
> 5 votes

# Answer
I had this problem in several projects and generalized a solution: https://github.com/cgdeboer/iteround
> 0 votes

---
Tags: algorithms, integers, rounding
---


# Question
Title: Can you short-cut the substitution method for recurrence solving? (Wrong Guess but End Result Works)
So I asked this question already once but didn't formulate it well. I ask it again but this time I want to be clear. The way how I understood it, the substitution method wants you to come up with a guess function $g(n)$ which has the property $g(n) \in O(f(n))$. The goal is, to show that your recurrence $T(n) \in O(f(n))$. In order to do that, you claim: $T(n) \leq g(n)$ and substitute accordingly until you have that exact term.

Example: $$T(n) = 2T(n/2) + n$$ $$T(n) \leq cn^2 - dn$$

Substitution: $$T(n/2) \leq c(n/2)^2 - (d/2)n = (c/4)n^2 - (d/2)n$$

So: $$T(n) = 2T(n/2) + n$$ $$T(n) \leq 2\[(c/4)n^2 - (d/2)n\]+n$$ $$T(n) \leq (c/2)n^2 - dn+n$$

Multiply with 2, property is not violated. $$T(n) \leq cn^2 - 2dn + 2n$$

If we assume $d \geq 2$ $$T(n) \leq cn^2 - dn$$

Our function $g(n) = cn^2 - dn$ and we tried to show that $T(n) = O(n^2)$ because $g(n) \in O(n^2)$.

Assume we failed to do the proof this well and we got something like: $$T(n) \leq (ac + b)n^2 - (xd+y)n$$

Observe that $a, b, c, d, x, y$ are all constants.

Would it be possible to claim: $(ac + b) = c\_2$ and $(xd+y) = d\_2$? And this new expression $c\_2n^2 - d\_2n$ is another function $g\_2(n) \in O(n^2)$ Would this indirectly still prove that $T(n)\in O(n^2)$?

# Answer
> 1 votes
No, you can't.

As an example, consider the recurrence $T(n) = 4T\left(\frac{n}2\right) + n^2$.

If you assume $T(n) \leqslant cn^2 - dn$, using substitution method, you will get to:

$$T(n) \leqslant 4\times c\frac{n^2}4 - 4\times d\frac{n}2 + n^2 = (c+1)n^2-2dn$$

Even if $(c+1)n^2-2dn\in \mathcal{O}(n^2)$, you cannot conclude that $T(n) \in \mathcal{O}(n^2)$.

Indeed, you can prove by induction that for all $k$: $$T(n) = 4^kT\left(\frac{n}{2^k}\right)+\sum\limits\_{i=0}^{k-1}n^2$$ If $n$ is a power of $2$, then for $k = \log\_2 n$, $T(n) = 4^kT(1) + n^2\log\_2 n = \Omega(n^2\log n)$.

---
Tags: recurrence-relation
---


# Question
Title: Longest path of directed graph with cycle and now weights
If you have a unweighted directed graph with possible cycles, what algorithm would you use to find the longest path without visiting the same node twice? Also, there are multiple starting nodes...

The real problem I am trying to solve is the following:

All values are positive integers:

A1 = \[a1, a2, ..., an\]

B2 = \[b1, b2, ..., bn\]

A person starts at ai. In order to live another day, the person must find an aj (i != j) that is greater than or equal to bi (you do not 'keep' the difference of the two). Once the person selects aj, the must do the same with bj and ak. The goal is to live as long as possible, and each time you land on an ai, counts as a new day.

How would you solve a problem like this?

# Answer
> 0 votes
The longest path problem is $\mathsf{NP}$-complete, so there is no known polynomial algorithm.

It can be solved in exponential time using dynamic programming.

---
Tags: shortest-path
---


# Question
Title: Turning stacked overlapping intervals (with associated data) into non-overlapping intervals
I'm looking for an efficient algorithm to merge a list of overlapping intervals (each of which has data associated) into non-overlapping intervals. In case two or more intervals overlap, the *latter* one wins (e.g. the later intervals shadow the earlier ones).

In my case, the intervals actually come pre-sorted (by starting point) but of course I can't do any further sorts because the intervals that come later in the input list dominate the previous ones.

Other facts:

* the intervals may overlap but don't have to
* there may be gaps not covered by any intervals

This feels like a common problem but I haven't found a common algorithm quite yet.

## Algorithm ideas

The naive algorithm (*O(n2)*) is just to intersect each interval with every interval that follows, keeping only the 'non-occluded' pieces. But that's inefficient.

I've also thought about using a variation of the regular overlapping intervals algorithm: Basically, building a stack and always intersecting the next element with the top of the stack followed by pushing the non-overlapping part of the old element and the overlapping part of the new element. But of course that potentially leaves a left-over piece from the old element. (Essentially `((1, 10), "1")` and `((2, 5), "2")` becomes `((1, 2), "1"), ((2, 5), "2")` with a left-over of `((5, 10), "1")`. But that left over is now unsorted with respect to the elements that follow and I can't sort it into the input list either because other intervals need to dominate this one.

Or maybe I should use an interval intersection algorithm to find each of the segments and then use a scan line algorithm to find the original interval that dominates each of the segments?

## Examples:

### Example 1

* input: `[((1, 10), "green"), ((5, 8), "red")]`
* output: `[((1, 5), "green"), ((5, 8), "red"), ((8, 10), "green")]`

### Example 2:

* input: `[((1,10), "1"), ((2, 4), "2"), ((3, 8), "3"), ((4, 7), "4"), ((5, 6), "5"), ((6, 9), "6")]`
* output: `[((1, 2), "1"), ((2, 3), "2"), ((3, 4), "3"), ((4, 5), "4"), ((5, 6), "5"), ((6, 9), "6")]`
* visualised:

((1,10), "1") 1111111111
((2, 4), "2") |222     |
((3, 8), "3") ||333333 |
((4, 7), "4") |||4444  |
((5, 6), "5") ||||55   |
((6, 9), "6") |||||6666|
              ||||||||||
              vvvvvvvvvv
========================
merged        1234566661

```

# Answer
> 1 votes
I found an answer that works well. The basic concept is to iterate a sorted list of all 'points of interest' (start and end location of intervals). Iterating that (scan line) allows us to maintain a stack of 'active intervals' (push when interval starts; pop when interval ends) where the top one is the dominating interval. That will essentially give us a list of non-overlapping segments associated with the dominating interval. That is exactly the goal.

In slightly more detail (hope I got the text description about right):

1. Create an array of all intervals which are already sorted by start point in $O(n)$.
2. Initialize:
    1. An empty hash set of 'dead intervals' in $O(1)$.
    2. An empty stack of 'active intervals' in $O(1)$.
    3. An empty array of 'output intervals' in $O(1)$.
3. Create a 'points of interest' array of all start and end points of all the intervals alongside the kind (start/end) and index (into the array of all intervals) in $O(n)$.
4. Sort the 'points of interest' array by position/index/kind in $O(n \log n)$.
5. Run a scan line from front to back: Iterate through the 'points of interest' from front to back in $O(n)$. For each 'point of interest' do:
    1. If it's a start point:
        1. Add the interval (looked up by index) to the stack of 'active intervals' in $O(1)$.
        2. If we have previously remembered an 'open interval', close it and append it to the array of 'output intervals'. Also clear the remembered 'open interval' in $O(1)$.
        3. Remember the current position as 'open interval' in $O(1)$.
    2. If it's an end point:
        1. Add the interval (looked up by index) to the set of 'dead intervals' in $O(1)$.
        2. While the interval at the top of the 'active intervals' is contained in the set of 'dead intervals' in amortized $O(1)$ (this can be $O(n)$ but each interval can only be in the dead intervals once):
            1. Remove from 'dead intervals' in $O(1)$.
            2. Pop the stack in $O(1)$.
        3. If we have previously remembered an 'open interval', close it and append it to the array of 'output intervals'. Also clear the remembered 'open interval' in $O(1)$.
        4. If the stack of 'active intervals' is non-empty, remember the current position as an 'open interval' in $O(1)$.

Overall, the algorithm runs in $O(n \log n)$.

# Answer
> 0 votes
One conceptually simple approach is to sort the intervals by which is latest. Then create an empty binary tree for the intervals you keep. Iterate through the intervals, from latest on to earliest, and for each interval, check if it overlaps any interval in the tree; if not, add it to the tree. If you use a self-balancing tree, each tree operation takes $O(\log n)$ time, so the total running time is $O(n \log n)$.

---
Tags: algorithms, intervals
---


# Question
Title: Undecidability of minimal PDAs and TM machines
Consider $$L=\\{\<TM\>:TM \text{ is a Turing machine and has minimal states}\\}$$ $$L'=\\{\<PDA\>:PDA\text{ is a PDA and has minimal states}\\}$$

Which one is recursive?

I think neither $L$ nor $L'$ are recursive but I can't reduce from a famous problem.

# Answer
> 4 votes
For all CFL, there is a one-state PDA that recognizes this language. So $L'$ is recursive: you just have to check if the PDA has exactly one state.

For $L$, note that Turing machines with exactly one state can recognize only the empty language or the universal language. That may help to find a reduction (especially knowing that there are two-states universal Turing machines).

# Answer
> 3 votes
This proof is very similar to a proof in Sipser. They consider the length of the description $\langle TM \rangle$ instead of the number of states, but the idea is the same.

Assume that $L \in \texttt{RE}$, then there must be an enumerator $E$ enumerating the words of $L$. Define the TM $A$ such that on word $w$:

* $A$ obtains its own description $\langle A \rangle$ using the recursion theorem,
* runs $E$ until it finds a machine $\langle B \rangle$ with more states than itself, and
* simulates $B$ on $w$.

Thus, $A$ is a machine with less states than $B$ and $L(A) = L(B)$ ↯. So $L$ can't have been enumerable.

---
Tags: formal-languages
---


title: Seeking help in designing an algorithm

text:
# Question
Title: Seeking help in designing an algorithm
I am not a computer science nor a math person, but if given a pseudo-code or a English outline of steps. I can probably fumble my way through and write some code. I Apologize for the wall of text/numbers and my formatting.

Seeking an algorithm that takes a number to start with. This number will be either in column A or column B

The algorithm will traverse down the list alternating the two columns A and B, if the first selected number is in column B then the next number must be in column A and vice versa

The length of movement must be one of the 20 values or as close as possible with a difference no greater than 0.1409

The algorithm ideally would collect all paths from the starting number to last number in the list or past the end of the list according to the above rules.

---

Column A, Column B

78.509, 78.087

79.996, 79.063

80.826, 80.112

81.307, 81.569

82.939, 82.123

83.274, 83.973

84.003, 84.979

85.081, 85.999

86.043, 86.742

87.441, 87.063

88.491, 88.986

89.991, 89.307

90.341, 90.589

91.157, 91.536

92.017, 92.541

93.051, 93.853

94.100, 94.785

95.426, 95.091

96.213, 96.563

97.933, 97.044

98.778, 98.064

99.827, 99.200

100.993, 100.337

101.619, 101.007

102.727, 102.960

103.892, 103.339

104.009, 104.606

105.072, 105.699

106.311, 106.952

107.681, 107.448

108.759, 108.234

109.196, 109.983

110.333, 110.916

111.629, 111.353

112.926, 112.023

113.276, 113.946

114.005, 114.923

115.943, 115.127

---

The 20 only possible length of movements

1.1275

2.2550

3.3825

4.5100

5.6375

6.7650

7.8925

9.0200

10.1475

11.2750

12.4025

13.5300

14.6575

15.7850

16.9125

18.0400

19.1675

20.2950

21.4225

22.5470

---

1 Possible combination For Example Starting Number:81.307 Column A next target is on Column B 81.307 + 13.52 = 94.827 - Column B Num:94.785 (94.827-94.785) = .042 which is less than 0.1409, so this is an acceptable movement.

Now Column B num:94.785 + Num:6.765 = 101.55 which is within acceptable tolerance of the Column A Number of 101.619

Now Column A num:101.619 + Num:13.52 = 115.139 which is in acceptable tolerance of Column B num:115.127

Thank you for your Time and Effort Scott

# Answer
> 1 votes
We can view this problem as depth first search on a directed unweighted bipartite graph.

A graph is a set of vertices connected by a set of edges between the vertices.

We can construct such graph by viewing each number as a vertex, then ask each pair of vertices whether they match one of the possible length of movements (check the possible length of movements one by one) and form an edge between them if they do.

The graph is directed since otherwise we could go between 81.307 and 94.827 without ever ending, which I assume is not intended.

The graph is unweighted since we only want to know whether we can go between 81.307 and 94.827, for example.

The graph is bipartite since we can only go to the other column and never the same column, we can color the columns blue and red without the vertices of the same color ever being adjacent.

We can perform depth first search using recursion on the graph to find all possible paths from a source point in lexicographical order.

The total time taken by this algorithm is proportional to the number of elements of column A times the number of elements of column B times the number of possible length of movements.

---
Tags: algorithms, algorithm-design
---


# Question
Title: What is meant by "uneven spacing" on number line when dealing with floating point numbers in computers?
I read some examples online on this subject, but none of them really gave an explanation. When I visualize the number line all I can see is evenly spaced numbers, I'm not grasping the notation of "uneven spacing" when It comes to plotting the floating point values from a machine's perspective. Perhaps I am thinking about this too literally.

# Answer
Let's look at a single-precision floating point number (as specified by IEEE 754). It is made up of 32 bits. Therefore, there are exactly $2^{32}$ floating point numbers that dots the number line.

What does it mean when we say that the floating point numbers are "unevenly" distributed on the number line? It means that they are not uniformly distributed. But why?

Well, let's consider the case where these numbers are distributed uniformly on the number line. Then there's some constant finite gap between successive numbers, $\Delta$. Since there are $2^{32}$ points on this line, then these uniformly distributed numbers span an interval of $\Delta \times 2^{32}$ width.

How big is $2^{32}$? Well, it's about 4 billion. Do you see the problem with uniformly distributed representations of numbers? If you want to even be able to represent the number $\pm 2$ billion in your uniform system, then you need to make sure that both $-2 \times 10^9$ and $2 \times 10^9$ are within your representable interval. Therefore, we need $\Delta \times 2^{32} \ge 4 \times 10^9$, so that we must space our numbers around $\Delta \approx 1$ apart. But if $\Delta \approx 1$, how are you going to represent both $1$ and $0.5$ precisely? Their difference is smaller than the gap!

Herein lies the rationale for having non-uniformly distributed representations such as floating point numbers. Uniformly distributed representations (or fixed-point numbers) cannot represent both big numbers and small numbers in a "good-enough" manner.
> 3 votes

# Answer
let consider a simple decimal system in which precession = 3, lower exponent = -3 & upper exponent = 3. so in order to call it uniform, number line should have a equal gaps between consecutive numbers.

case 1: $x\_1 = 1.31\*10^2, x\_2= 1.32\*10^2 $ $\therefore \Delta x =0.01\*10^2 $

case 2: $x\_1 = 1.31\*10^{-2}, x\_2 = 1.32\*10^{-2} $ $\therefore \Delta x = 0.01\*10^{-2}$

since $\Delta x$ in case 1 is not equal to case 2, we can say that floating point numbers are not uniformly distributed.
> 2 votes

# Answer
Positive floating point numbers are encoded as something like

$Mantissa * 2^{Exponent-Constant}.$

Where $Mantissa$ and $Exponent$ are naturals, for example respectively 24bits and 7bits scalars (32bits single precision).

The 'spacing' between consecutive values depend on the exponent, it is not constant.

(Actual floating point numbers are a bit more complex with encoding for infinites, tricks around zero...)
> 1 votes

# Answer
Take a C++ compiler. Start with double x = 1.0 and double y = 1e100.

Now try out various values z, and find for which z you find that x+z != x or y+z != y. What is the smallest z where 1.0 + z != 1.0 and the smallest z where 1e100 + z != 1e100?
> 1 votes

---
Tags: floating-point
---


# Question
Title: What type of clustering would occur if one of the functions in double hashing is constant?
If the hash is calculated as h(k, i) = (h1(k) + i\*h2(k)) mod |T|

What would happen if h1(k) or h2(k) is constant? Would that produce primary or secondary clustering? I think both would produce secondary clustering and I don't see how it would cause primary clustering because I feel the i multiplying h2(k) prevents the formation of a big cluster, but I get different opinions

# Answer
> 3 votes
When $h\_2$ is constant we have open adressing with linear probing. Usually the step size equals $1$, but here it is another constant. It has both primary and secundary clustering. For the primary cluster, not all keys are next to one another, but rather a constant $h\_2$ places apart.

When $h\_1$ is constant, I would not call this hashing at all, as the keys are not distributed over the address space at all. Whether it has clustering seems then irrelevant in my opinion.

---
Tags: hashing, clustering
---


# Question
Title: Why does Hopcroft-Karp only work on bipartite graphs?
I have a simple question which I cannot answer, and it relates to this question.

What I cannot answer is this:

1. Why does a graph with bidirectional edges destroy the "bipartiteness" of the graph?
2. Depending on the answer to question 1, why wouldn't Hopcroft-Karp work on bidirectional graphs?

Specifically, for question 1, it seems we can do the following:

1. Assume that a graph with bidirectional edges with node set $A$ with cardinality $|A|$ is actually two sets of nodes $B, C$, each with cardinality equivalent to $|A|$ such that $|B \cup C| = 2 |A|$ and there is guaranteed to be an edge from $B \rightarrow C$ if there is an edge from $C \rightarrow B$.
2. This would be analogous to the stable marriage problem, where every time a marriage is desired in one direction, it is reciprocated. It seems like an unlikely but valid setup.

Is there a problem with viewing a bipartite graph in this way? It seems like a valid setup to me.

# Answer
I don't see why bi-directional edges are relevant here (or what problem your construction tries to solve), the question you reference is only about undirected graphs. But I can understand your confusion with that Q&A pair. My understanding is that:

1. The questioner wants to match the entries of an array $A$ to other entries of this array, where the edges are given due to some condition, and try to do so by making a copy $B$ of $A$, and create a bipartite graph on them. However, they note that then they need the additional requirement that if $(A\[i\],B\[j\])$, are matched then $(A\[j\],B\[i\])$ must also be matched
2. The answer notes that they should not try to make a bipartite graph. What they mean is that the additional constraint on the bipartite graph corresponds to the original edge-relation on the array $A$. As the original edges were arbitrary, we need to perform matching on a general undirected graph.

The standard formulation of the Hopcroft-Karp algorithm uses the fact that the graph is bipartite to ensure finding augmenting paths is not too difficult. It is apparently possible to extend this procedure efficiently for general undirected graphs, but this is rather complicated, so using another algorithm such as Edmonds algorithm seems a better choice.
> 4 votes

---
Tags: algorithms, graphs, bipartite-matching
---


# Question
Title: Is there a one-state PDA that recognizes every context free language?
Here, I read this:

> For all CFL, there is a one-state PDA that recognizes this language.

What is the proof/idea behind this claim?

CFL: Context Free Languages PDA: Push Down Automaton

# Answer
We have to be precise.

Each context-free language can be accepted by *empty stack* using a push-down automaton with a single state, or by *final state* and two states. (In the latter case we obviously need one accepting and one non-accepting state.)

The proof uses the equivalence between context-free grammars and push-down automata. Every CFG is equivalent to a PDA with a single state (and empty stack acceptance). Wikipedia mentions the expand-match construction which directly simulates the context-free derivation on the stack.
> 6 votes

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


# Question
Title: Given two sets of integers find an integer in the first set furthest away from all members of the second set
If given two sets of integers how can I find an integer in the first set furthest away from all members of the second set. The distance of two integers is the absolute value of difference of the two integers. To clarify the question: if $a\_i$ and $b\_j$ are elements of the first and the second sets, I am trying to find $i$ such as $$\operatorname\*{argmax}\_{i} (\min\_{j} |a\_i - b\_j|)$$

Thanks!

# Answer
> 5 votes
Since you now clarified your request, I give a new answer:

Assume your sets are $A$ and $B$, with $|A|=n$ and $|B|=m$. Let $k=\max(n,m)$. This is the procedure:

1. Join the two sets $X=A\cup B$ in $\Theta(k)$ time.
2. Sort $X$ in $\Theta((n+m)\log(n+m))=\Theta(k\log k)$ time.
3. Scan the sorted set and, each time you encounter an element of $A$, it is sufficient to compute its distance from the previous element of $B$ and the next element of $B$ and take the minimum of the two distances. In this process, keep track of the maximum of these minimum distances. This can be easily done in $\Theta(k)$.

So, the overall time complexity is $\Theta(k\log k)$.

---
Tags: algorithms, sets
---


# Question
Title: Creating an executable after code generation - compiler design
I am learning about and building a very basic compiler. My question is about code generation. I have read on a lot of materials about code generation when building a compiler and I get the concept.

Suppose I am targeting only a single architecture and OS, for a very basic language, and I have completed all the necessary steps and generated the assembly code for that specific architecture and OS. How would I do such that this assembly code gets compiled to an executable file from my compiler alone such that invoking it like:  `my_compiler codefile.mylangugage` produces an executable file, instead of first compiling to assembly then having the user to call an assembler such as `nasm` themselves?

As an addition, if you can also tell how interpreted languages and virtual machines convert to machine code (just the overview)?

# Answer
> 2 votes
Assembly language is basically meant to be a 1:1 representation of the underlying CPU machine code. (Yes I'm aware there are a few exceptions, especially with modern assemblers) The difference is you are representing actual machine opcodes with short "mnemonic codes" that make it slightly easier to understand what is happening. So Opcode FF in hex might become JMP in assembler, which refers to an instruction to jump to a particular memory address.

Honestly, if you can write a compiler that generates assembly language, how are you not aware of this and how can you not simply write a compiler that generates the machine code directly?

---
Tags: programming-languages, compilers, code-generation
---


# Question
Title: Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?
This question is kind of a follow-up to a question asked a few days ago. Both of the non-linear complements of linear languages found were also not context free. So the question is this: Is there some linear $L$ such that $\overline{L}$ is non-linear but still context free?

One attempt I've made was to look at the linear language $L = \\{a^nb^ma^ib^j \in (a^+b^+)^2 : n = m \lor i = j\\}$ with $$\overline{L} = \overline{(a^+b^+)^2} \cup \\{a^nb^m \in a^+b^+: n \neq m\\}^2.$$ $\overline{L}$ must be context free since its components are, and the context free languages are closed under $\cup$ and $\circ$. Intuitively $\overline{L}$ doesn't seem linear to me, especially since it contains the contcatenation of linear languages. Maybe the pumping lemma can be used?

Thanks in advance for all help :)

# Answer
> 3 votes
It seems you almost solved the problem in your question statement. Note that the $n\neq m$ condition makes pumping hard: one needs a trick using factorials to succeed, see Prove if $L=\\{0^m1^n∣m≠n\\}$ is regular or not. We use your idea, but start at the other side.

As a shorthand, let $D = a^+b^+a^+b^+ $ be the underlying regular "domain".

Your linked paper by Horváth and Nagy states a pumping lemma for linear-languages, referring to the classic book by Hopcroft and Ullman (page 143, Exercises 6.11 and 6.12). It is interesting to see that this pumping lemma looks exactly like the pumping for context-free languages, but one of its conditions looks more like that for regular languages: we can pump somewhere near the top of the derivation tree.

The example of a non-linear language given there is $L = \\{ a^m b^m a^n b^n \mid m,n\ge 1\\}$, or
$\\{ a^m b^n a^i b^j \mid m=n \text{ and } i=j\\}$.

Its complement, $L^c = D^c \cup \\{ a^m b^n a^i b^j \mid m\neq n \text{ or } i\neq j\\}$ is linear. It can be split into simpler languages, like for example $\\{ a^m b^n \mid m\> n \\}\cdot a^+b^+$.

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


title: Python Scikit-Learn transformation

text:
# Question
Title: Python Scikit-Learn transformation
I am trying to learn Scikit\_Learn and build an ML model. I am learning from "Hands-On Machine Learning with SciKit-Learn, Keras & TensorFlow".

In Chapter 2, there is a review of an entire ML project from the beginning until completion. One of the steps is to transform or prepare the data for the model. There are numerous transformation steps and each output is stored in a new object (mostly Dataframe).

Why is the model built with the original dataset? Wouldn't these transformations be ineffective?

I haven't cited the example from the book as it is too lengthy. If you have the book, please review and respond to my question.

Another similar instance would be from https://machinelearningmastery.com/python-machine-learning-mini-course/

In Lesson 7, the standardized data is stored in "rescaledX" and the model is built from X which is the original dataset. How is the standardized data used in the model that comes afterwards?

# Answer
You can build a model from either untransformed data or from transformed data. The only requirement is that, at test time, you must apply the model to the same sort of data.

Which will perform better? It depends on the algorithm, the data, and perhaps other factors. Some algorithms work better with data that has been standardized (e.g., k-nearest neighbors, deep learning). Others don't care. The most reliable way to know which will perform best is to try both.

It's hard to say why a particular exercise does it one way without knowing the specifics of that exercise. Perhaps they tried both ways and one way works better. Perhaps they only tried one way and that worked well enough so they went with it. Perhaps there is a bug. Perhaps it was chosen for pedagogical reasons. "Why?" questions are often hard to answer in modern machine learning. If you want to try to gain more insight yurself, you can try training a model both ways and see if one way performs better or not.
> 0 votes

---
Tags: machine-learning, python
---


# Question
Title: Is the fact true that GPT-3 wasn't trained on any explicitly gathered code dataset?
The paper mentions a line about GPT-3's training dataset -

`Motivated by the ability of GPT-3 (Brown et al., 2020) to generate plausible code completions despite its training data not containing any explicitly gathered code datasets`

My question - I need clarification on the following:

1. If it was not trained on any "explicitly gathered code datasets", did the actual dataset on which it was trained on, contained some amount of code or exactly no code?
2. If not, then how did it develop an ability to generate any code without learning what code really is?

# Answer
> 2 votes
Presumably "explicitly gathered" means that they didn't go out of their way to collect datasets specifically focused on code.

Undoubtedly the datasets they did use contained some code in it. The GPT3 paper says it was trained on a filtered version of CommonCrawl. This includes data from many sources that likely contain some code. For instance, Wikipedia contains code. So do some arXiv articles, some blog posts, some Stack Exchange answers, and many other sources.

---
Tags: natural-language-processing
---


# Question
Title: How to find a "short" walk that visits all vertices of a strongly connected directed graph
I am interested in the following algorithmic problem: Given a strongly connected directed graph $G$, I want a "short" (see below for what I mean by short) walk that starts with an arbitrary vertex $s$ and contains all vertices of $G$.

Deciding if such a walk can be a path (i.e. no repeated vertices) is a well known NP-complete problem.

So I am interested in a walk that might repeat vertices.

I can perform the following: Start with the walk $X=(s)$ and, until there are unvisited vertices, let $v$ be unvisited, take the last vertex $x$ from $X$ and append a $x$-$v$ path (it must exist because $G$ is strongly connected) to $X$. This procedure will eventually terminate, but will produce a walk of possibly quadratic length.

My question is, can we do better and guarantee a linear-sized walk? Is there an efficient (say linear or maybe $n\log n$) algorithm to compute the walk?

What I know: if G was undirected (and connected), there is always a walk visiting each vertex and it can be easily found by computing the spanning tree and doing DFS traversal of it, but this is not applicable since we assume $G$ to be directed.

# Answer
The answer is **no**. For any $n\geq 3$ consider an oriented cycle $C\_n$ and let $u\to v$ be adjacent in the $C\_n$. Create $n$ vertices $x\_1...x\_n$ and add edges $u\to x\_i$ and $x\_i \to v$. Now any walk containing all vertices has length $\Omega(n^2)$.
> 14 votes

---
Tags: algorithms, directed-graphs, path
---


# Question
Title: Potential of Artificial Intelligence to improve algorithm for PI
Recently AI (alphazero) was used to improve practical matrix multiplications by around 10 to 20 percent. Alphageometry and ramanujan machines all came into existence in the recent years as well. Seems like it might time AI gets used to further improve algorithms for pi like this one? If so, is there a sketch of a solution?

# Answer
> 4 votes
All of the improved algorithms that Alphazero found are basically the same idea: there is a combinatorial search space of solutions which is hard to navigate through, but it's possible to prove that you've found a solution when you propose one.

There are definitely algorithms for computing $\pi$ that live in spaces like this. Machin-like formulas are an example that are relatively easy to understand: there are an infinite number of possible algorithms, it's straightforward to prove that one is correct or not, and the goal is to find the most efficient of them.

The Chodnovsky and Borwein algorithms are both examples of Ramanujan-Sato series. Again, these form a large search space that is feasible to search and prove correctness. So it's certainly possible that alphazero could indeed produce new algorithms of that type.

---
Tags: algorithms, optimization, artificial-intelligence, mathematical-programming
---


# Question
Title: Process Synchronization: Dekker's algorithm
This Screenshot is taken from William Stalling's Operating Systems book. My doubt is that Bounded wait is not satisfied by this solution.

For example: P0 and P1 both want to enter critical section and set their flags to true.

flag\[0\] = true

flag\[ 1\] = true

Both p0 and p1 enter while loop, p0 wins the race process P1 sets its flag to false

now flag\[ 1\]= false

Process P0 goes into Critical Section, comes out, sets turn = 1 and flag\[0\]=false.

Now actual problem starts from here:

Process P1 comes out of infinite while loop and before i could set flag\[ 1\] to True from False, it gets preempted.

Now Process P0 can go any number of times in Critical section because Flag\[ 1\] is False.

Conclusion: Process P1 tried to get access to critical section but because of bad solution it did set its flag to False to give path to Po and now stuck for infinite time.

hence B.W is not satisfied!

# Answer
> 4 votes
When P1 runs again, it set its flag to True. Your scenario assumes P0 is executed continuously, while P1 never gets a chance to execute its code. This also happens in the simple case where there is only one process running, but obviously this does not contradict bounded waiting.

An implicit assumption when talking about protocols for mutual exclusion is that all of the processes involved will eventually run and execute their current command (otherwise it is meaningless to talk about properties such as bounded waiting or starvation freedom).

# Answer
> 1 votes
Yes, it ensures bounded waiting. In the example you have given even if p0 enters twice in a row, p1 will be able to enter in it the after p0's second entry.

Normally you will see only 1 entry to the other process is allowed for binary critical solution problem. But here 2 entries are allowed.

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Regex for string does not contain the substring "110"
Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)? Write a regular expression for the language L = {w | w does not contain 110}

So, the answer I get is: $(0 \cup 10)^\* (1 \cup 111^\* \cup \epsilon)$

And the answer given is: $(0 \cup (10)^\*)^\*1^\*$

# Answer
Note that $\mathcal{L}(1\cup 111^\*\cup \varepsilon) = \mathcal{L}(1^\*)$.

And in the general case, $\mathcal{L}((e\cup f)^\*) = \mathcal{L}((e\cup f^\*)^\*)$.

So your regular expression is correct.
> 1 votes

# Answer
To elaborate on Nathaniel's answer:

$1 \cup 111\* \cup\space \epsilon \\ = 1(\epsilon \cup 11^\*)\cup \epsilon \\ = 1(\epsilon + 1^+) \cup \epsilon \\ = 1(1^\*) \cup \epsilon\\ = 1^+ \cup \epsilon \\ = 1^\*$
> 1 votes

# Answer
Your strings can start with any number of 0's or 10's. These don't contain any 110. So we start with $(0 | 10)^\*$.

The remainder of the input mustn't contain any zeroes: If the remainder starts with no 1 or one 1, then that cannot be followed by a zero, because 0 or 10 would be part of $(0 | 10)^\*$. If there are $n \ge 2$ 1's, that cannot be followed by a 0 because then we would have $1^{n-2} 110$ which is by definition not part of the language. So the rest of the input is $1^\*$, and the regular expression is $(0 | 10)^\* 1^\*$.

OP's answer is also correct, but this grammar is simpler, and any string can be parsed in one way only.
> 0 votes

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


# Question
Title: Possible Mistake in Skiena's Algorithm Design Manual
In Skiena's book *Algorithm Design Manual, 3rd Edition*, it is claimed on page 45 that

$$ mn - m^2 + m \in \Omega(mn) $$

where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the following proof. Toward a contradiction, suppose otherwise. Then $$mn-m^2 + m \geq cmn$$ where $m,n \> N\_{0}$ for some sufficiently large interger $N\_{0}$ and some constant $c \> 0$. Without loss of generality, we may assume that $c \< 1$ since the RHS above is a lower bound. Then after some rearrangement and canceling terms, we obtain

$$ 1-c \geq \frac{m-1}{n}. $$

Now recall we can take $m = n$, so we obtain

$$ 1-c \geq \frac{n-1}{n}, $$

where the RHS is not greater than $1$. However it is easy to see that $\frac{n-1}{n} \to 1$ as $n \to \infty$. Therefore, given any fixed constant $0 \< c \< 1$, we will be unable to choose a sufficiently large bound $N\_{0}$ such that when $m,n \> N\_{0}$ the above inequality is satisfied. Thus the original claim is false.

In fact, the claim is apparently still false even under the stronger assumption that $m - a \leq n$ for some constant $a \> 0$. In this case we arrive at the final inequality

$$ 1-c \geq \frac{n-a+1}{n}, $$

where the RHS still converges to $1$ as $n \to \infty$.

**Question:** Where did I go wrong above? Did I go wrong above? I would appreciate any feedback addressing any issue with the argument above.

**P.S.** There exists at least one question on here that also references this equation in the text but the discussion there does not address this particular issue with the claim.

# Answer
> 6 votes
You are totally right, though I think there is an easier proof: if $m = n$, then $mn-m^2 +m= m\notin \Omega(m^2)$.

However, since the analysis is done when searching for a worst case, you could just add a condition $2m\leqslant n$ for the analysis to be correct.

But there is indeed a mistake in the analysis by Skiena, that could be clarified.

---
Tags: algorithms, algorithm-analysis, asymptotics, big-o-notation
---


# Question
Title: Bankers Algorithm - maximum number of processes
I recently got the following question in my exam.

**Q1) In the banker's algorithm, if the total number of resources in the system is 20 and the maximum resource allocation for a process is 5, what is the maximum number of processes that can be running simultaneously?**

Options

1. 1
2. 4
3. 5
4. 20

The answer is given as **5**.

I believe it should be **4** because with 5 processes there is still a situation where deadlock could still happen - when all the resouces are equally distributed among all the processes i.e. 20/5 = 4 resources/process.

# Answer
Yes. It should be 4 only.

$4\times n+1 \leqslant 20 $

Maximum possible value of n is 4
> 0 votes

---
Tags: operating-systems, concurrency, synchronization, deadlocks
---


# Question
Title: How to test progress and bounded waiting in Peterson's algorithm?
This is Petersons's solution for critical section problem. I want to test mutual exclusion, progress and bounded waiting for it. Of course, it satisfied all three.

```
Process0

while(true)
{
intendToEnter0=true;
turn=1;
while(intendToEnter1==T && turn==1);
critical section
intendToEnter0=false;
non-critical section
}

Process1

while(true)
{
intendToEnter1=true;
turn=0;
while(intendToEnter0==T && turn==0);
critical section
intendToEnter1=false;
non-critical section
}

```
1. Mutual Exclusion

Definition:

No two cooperating processes can enter into their critical section at the same time. For example, if a process P1 is executing in its critical section, no other cooperating process can enter in the critical section until P1 finishes with it.

Test:

Say P1 is in its critical section. That means turn=0 & intendToEnter1=true.

Now, P0 attempts to enter its critical section. That means it sets intendToEnter0=true & turn=1.

In AND condition if any condition is false, the output is false. Both condition are true here, so it waits.

So, mutual exclusion is achieved.

2. Progress

Definition:

If no process is in its CS and there are one or more processes that wish to enter their CS, this selection cannot be postponed indefinitely.

No process in remainder section can participate in this decision.

How to test?

3. Bounded Waiting

Definition:

After a prcess P has made a request to enter its CS, there is a limit on the number of times that the other processes are allowed to enter their CS, before P's request is granted. How to test?

How to test?

# Answer
> 0 votes
We note that a process P i can be prevented from entering the critical section only if it is stuck in the while loop with the condition flag\[j\] == true and turn == j ; this loop is the only one possible. If P j is not ready to enter the critical section, then flag\[j\] == false , and P i can enter its critical section. If P j has set flag\[j\] to true and is also executing in its while statement, then either turn == i or turn == j . If turn == i , then P i will enter the critical section. If turn == j , then P j will enter the critical section. However, once P j exits its critical section, it will reset flag\[j\] to false , allowing P i to enter its critical section. If P j resets flag\[j\] to true , it must also set turn to i . Thus, since P i does not change the value of the variable turn while executing the while statement, P i will enter the critical section (progress) after at most one entry by P j (bounded waiting).

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


# Question
Title: Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$
The thing that confuses me here is that i've seen a similar example where $L=\\{a^nb^m : 2m\leq n\leq 4m\\}$ where the CFG was straight forward: $$ S\rightarrow aSbb\\ S\rightarrow aSbbb\\S\rightarrow aSbbbb\\S\rightarrow \epsilon $$ however, in this example I cant get my mind out of the "just go for the simple approach" which is $$ S\rightarrow aSbbb\\S\rightarrow\epsilon $$ however this feels somewhat incomplete to me.

EDIT: I see my errors, i propose this solution: $$ S\rightarrow aaaAb\\A\rightarrow aaaAb\\A\rightarrow \epsilon $$ this seems more correct due to the fact that now I am 'forcing' 3 $a$'s each time a $b$ shows up, also $\epsilon$ is no longer included.

# Answer
> 2 votes
The problem with your (new) solution is that you force $n$ to be equal to $3m$. That means that your grammar generates words that are in $L = \\{a^nb^m\mid 2m \< n \< 4m\\}$, but words in $L$ like $aaaaabb$ cannot be generated by your grammar.

You can use the example grammar to construct the wanted grammar by noting these facts:

* for each $b$, one must add $2$, $3$ or $4$ $a$'s;
* one must neither always add $2$ $a$'s, nor always add $4$ $a$'s.

# Answer
> 1 votes
No. The grammar you propose is not correct. For example it generates $\varepsilon$, which is not in the language. In fact, no word generated by your grammar is in the language. To see this notice that the generated words have at least as many $b$s than $a$s, yet all words in the language have more $a$s than $b$s.

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


# Question
Title: Confusion in the solution to first readers-writers synchronization
I am studying the solution to “First Readers-Writers Problem” from the book Operating System Concepts (9th edition) and it describes:

> First readers–writers problem, requires that no reader be kept waiting unless a writer has already obtained permission to use the shared object. In other words, no reader should wait for other readers to finish simply because a writer is waiting.

And what I have understood from this is that if there is any reader running and a writer comes, then that writer would be blocked until reader has completed. But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer.

First of all please correct me if I am wrong here. But if am right, then what I have understood is that, the code for the reader below does not guarantee this.

Code for reader-writer is given below:

```
//data structures
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

//Code for writer
do {
   wait(rw_mutex);
   . . .
   /* writing is performed */
   . . .
   signal(rw_mutex);
} while (true);

//Code for reader
do {
   wait(mutex);            //Line 01
   read_count++;

   if (read_count == 1)
      wait(rw_mutex);      //Line 02

   signal(mutex);
   . . .
   /* reading is performed */
   . . .

   wait(mutex);            //Line 03
   read_count--;

   if (read_count == 0)
      signal(rw_mutex);    //Line 04

   signal(mutex);
} while (true);

```

Now suppose following sequence of events occurs:

* Suppose a first reader comes and it blocks the writer on the line mentioned as `Line 02` in comments.
* Then a writer comes which is waiting for `rw_mutex`.
* Then the first reader is executing the code line mentioned as `Line 03` in comments and it has locked the `mutex` semaphore.
* At the same time a second reader comes and it starts waiting on the line mentioned as `Line 01` in comments.
* Now when the first reader executes `Line 04`, it releases the lock on `rw_mutex` and the writer which was waiting in its while loop is unlocked now and starts executing.
* The second reader will be unlocked when the first reader executes the line after `Line 04` that signals the `mutex` semaphore.

Now if we see the overall flow, then *the writer runs before the second reader*. So does the code logic work the same as described above?

Please correct me if I am wrong.

# Answer
> But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer.

It's a bit more subtle. The second reader is not given priority. Rather, the reader *is not blocked* by the first reader. This means that if the first reader takes sufficiently long, then the second reader will eventually start reading, even if there is also a writer waiting to take the lock. It is possible however to have a sequence of events where:

* A first reader is reading.
* The first reader has finished its task and starts releasing the reader-writer lock. This is not an atomic operation: the first reader needs to perform several operations (decrement `read_count`, test it for zero, and call `signal` on `rw_mutex`), and these operations must look atomic from other processes' point of view so they are performed in a critical section, protected by `mutex`. Thus “starts releasing the reader-writer lock” means “takes `mutex`”.
* A second reader enters the system and starts working on acquiring the reader-writer lock, but it has not yet finished acquiring the reader-writer lock. The second reader waits on `mutex`, which is currently held by the first reader.
* A writer enters the system and starts working on acquiring the reader-writer lock: it waits on `rw_mutex`.
* The first reader is releasing the reader-writer lock, and it signals `rw_mutex`, allowing the writer to take it.

This sequence of events is what is going on in the scenario you describe: the second reader is waiting at line 01, and the first reader goes through line 03 then line 04.

In typical operation, this scenario will not occur often, because it depends on the second reader starting to wait on `mutex` while the first reader holds it. Given that the first reader only keeps that semaphore for a very short time, this scheduling is unlikely: most of the time, `mutex` is not held.

If the second reader arrives (i.e. calls `wait(mutex)`) before the first reader enters the critical section to release the reader-writer lock, then the second reader can start reading while the first reader is still reading, and the writer only gets the reader-writer lock once the second reader has finished. If the second reader arrives after the first reader exits that critical section, then it is clear that the already-waiting writer will grab the lock first. It's only if the second reader arrives during the first reader's critical section that there is this possibility of inversion where the writer arrives after the second reader, while the first reader is still in the critical section, and then the writer wins the race.

This kind of rarely-occurring scenario is an illustration of why concurrency is difficult. It's rare, but you still need to make sure your algorithm works in this case, because when it does occur, if your algorithm is buggy, it can bring your system down in a way that's hard to identify and fix. Here, this scenario specifically illustrates the need for `mutex`: without it, the second reader and the writer could both take the reader-writer lock.

In situations with low contention (i.e. it's rare that multiple processes want the same lock at the same time), as long as your algorithm is correct, the fact that the writer sneaks past the second reader is irrelevant. In situations with high contention, this kind of inversion can lead to starvation, and sometimes more sophisticated algorithm ensuring some kind of fairness property are needed.
> 3 votes

# Answer
Essentially in your example: The correct sequence of description would be -

1. Reader 1 arrives
2. Reader 1 starts reading
3. Writer 1 arrives and starts waiting
4. Reader 1 completes
5. Writer 1 starts writing
6. Reader 2 arrives and starts waiting

So, here is no contradiction.
> 0 votes

---
Tags: operating-systems, concurrency, synchronization, mutual-exclusion
---


title: Naive Read-Write Lock

text:
# Question
Title: Naive Read-Write Lock
Consider the simply read-write lock algorithm that allows many readers and a single writer. Why is this algorithm flawed?

I was thinking about the implementation of a well-known read-write lock library and wondering why it didn't do this simpler approach.

**To read:**

1. atomically add 1.
2. if the old value was less than N, proceed. When you're done, subtract 1.
3. otherwise, subtract 1, wait, and try again.

**To write:**

Pick a fixed large number N, greater than the number of readers will every be (it can be in the billions).

1. atomically add a N.
2. if the old value was zero, proceed. When you're done, subtract N.
3. otherwise, subtract N, wait, and try again.

# Answer
It will work but generally we cant take the assumption that N is known beforehand.
> 0 votes

---
Tags: concurrency, deadlocks
---


# Question
Title: Tigers and elephants can't drink water from a pond simultaneously, while more than one tiger or more than one elephants can drink water simultaneously
Below is a question on synchronization mechanism which was asked in an interview in *Indian Statistical Institute, M.Tech CS*. I got hold of it from here.

> There is a forest where there are tigers and elephants. There are two processes named tiger and elephant. Design a concurrency processing using semaphore, such that tigers and elephants cannot drink water from a pond simultaneously, whereas more than one tiger or more than one elephants can drink water simultaneously.
>
> $\tag {ISI, M. Tech CS}$

Though some of my peers have tried to answer it, but I felt like trying it on my own, but after trying out on my own, I do not know whether is it flawed of not. It seems correct to me apparently, but since I am a self learner, I do not know anyone who could possibly look into my solution and give me hints to rectify the flaw in the solution (if it exists). So I thought of asking it here.

Below is my approach: \[This is my second approach, my previous version can be found in the edited section\]

---

Let `Tiger` and `Elephant` be integer variables initialized to `0` which stores the number of tigers and elephants drinking water respectively.

Also, `T` and `E` be two semaphores each initialized to `0`, to block a tiger process or elephant process respectively on these semaphores.

Let `blockedTiger` and `blockedElephant` be integer variables to store the number of $\text{Tiger}$ and $\text{Elephant}$ processes blocked on `T` and `E` respectively.

Also let us have a binary semaphore `mutex` initialized to `1` which is used for mutual exclusion and to implement the synchronization.

So in terms of code we have:

```
//shared variables
int Tiger,Elephant;
Tiger=Elephant=0;
Semaphore T,E;
T=E=0;
int blockedTiger,blockedElephant;
blockedTiger=blockedElephant=0;
BinSemaphore mutex ;
mutex=1;

```

---

Next let me show the code for the $i$th $\text{Tiger}$ process.

```
/*i th Tiger Process*/

/**********************ENTRY SECTION***************/
P(mutex);
while(Elephant!=0)
{
    V(mutex);
    blockedTiger++;
    P(T);   //to block this Tiger process on semaphore T
    P(mutex);
}

while(--blockedTiger)
    V(T);
Tiger++;
V(mutex);

/*******************END OF ENTRY SECTION***************/

DrinkWater();

/*******************EXIT SECTION**************/
P(mutex);
Tiger--;
if(Tiger==0)
   V(E);
V(mutex);

/********************END OF EXIT SECTION****************/

```

---

Next let me show the code for the $j$th $\text{Elephant}$ process.

```
/*j th Elephant Process*/

/**********************ENTRY SECTION***************/
P(mutex);
while(Tiger!=0)
{
    V(mutex);
    blockedElephant++;
    P(E);   //to block this Elephant process on semaphore E
    P(mutex);
}

while(--blockedElephant)
    V(E);
Elephant++;
V(mutex);

/*******************END OF ENTRY SECTION***************/

DrinkWater();

/*******************EXIT SECTION**************/
P(mutex);
Elephant--;
if(Elephant==0)
   V(T);
V(mutex);

/********************END OF EXIT SECTION****************/

```

---

Please can anyone give me feedback as to whether it is correct or not. And if not correct, please give me hints so that I can rectify it.

# Answer
> 0 votes
Your approach is allowing the tiger and elephant to simultaneously enter the pond. Consider the case when there are no tigers or elephants and both of them approach the pond. The control of your program is reaching `Drinkwater()` for both the processes which shouldn't be allowed as per the problem statement.

Hint: Try doing the same with fewer mutexes/semaphores. Right now the way you have approached it doesn't really take advantage of the nature of a mutex as both processes are operating on different copies of it. And while constructing your solution for such problems, try pre-empting the process and switch back and forth between them to find if the violate mutual exclusion or end up in a deadlock.

# Answer
> 0 votes
Starvation Free Solution assuming FIFO Waiting Queue

```
wait(mutex);
wait(Tiger_Mutex);
tiger_count++;
if(tiger_count==1);
    wait(pond)
signal(mutex);
signal(Tiger_Mutex);
drink_water();
wait(Tiger_Mutex);
tiger_count--;
if(tiger_count==0)
    signal(pond)
signal(Tiger_Mutex);

```

All mutex initialized to 1

Similar code for Elephant

---
Tags: operating-systems, concurrency, synchronization, check-my-answer, semaphore
---


title: Mutual exclusion for n processes

text:
# Question
Title: Mutual exclusion for n processes
I want to implement mutual exclusion for $n$ processes. Critical section code:

```
int turn = 0;        /* shared control variable */

Pi:                  /* i is 0 or 1 */
while (turn != i)
   ;                 /* busy wait */
CSi;
turn = 1 - i;

```

This solution from this page but it is only made for two processes.

I tried to adapt it for $n$ processes like this:

```
turn = 0 // shared control variable

i = turn;

while (turn != i);

// CS

turn = (turn + 1) % n;

```

Does this work?

# Answer
From my understanding of the 2-processor, if you want to do the same thing you would delete the statement (I truly dont know why you had it. There could be something interesting behind this statement of yours).

```
 i = turn

```

and instead, let each of the $n$ processors have an id from $\\{1, \dots, n\\}$. Then, you would let the processors go *in sequence* to the critical code. That is, assume a processor $i$ takes the token and left it. Then, it has to wait the other $n- 1$ to take the token if it want to take it again. The problem in this solution is the sequential method of taking the token.

If you want to have something more efficient, then have a look at the Lamport's bakery algorithm. The pseudocode of the algorithm is available in the site you provided, and it is explained in wikipedia. The idea of this algorithm is very simple in fact. There is a *queue* of processors that want to get the token. These processors enter the queue, and the first come is first served.

In regard to the link you included in your question, this is done by these lines:

```
number[i] = max(number) + 1;   // enter the queue !
...
...
while (number[j] != 0 && (number[j] < number[i] ||
                         number[j] == number[i] && j < i) )
// wait until your turn comes.
...
Do your critical section ! ...
...
 number[i] = 0;     // go out of the queue ..

```

Obviously, you can play around with this. But it is a neat way of implementing FIFO requests.
> 5 votes

# Answer
Take a look at Allen B. Downey's "The Little Book of Semaphores, it discusses synchronization in great depth. In any case, schemes based on just the atomicity of writing to memory are unwieldly and of no practical use (real CPUs have special instructions that simplify implementing this stuff enormously).
> 1 votes

# Answer
The progress condition of critical section problem is not satisfied here.
> 0 votes

---
Tags: concurrency, mutual-exclusion
---


# Question
Title: Is Starvation possible in First Come first serve CPU scheduling algorithm
Let's say if we have an infinite process that never yields such that other process dosent get to run. Since FCFS is a non preemptive scheduler does it leads to starvation

# Answer
OS would generally trap these type of process and core would be dumped.
> -1 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Understanding how lazy functional languages achieve IO (...sometimes?)
> An Alternative view of I/O programs, popular in earlier **lazy** functional programming languages, was to see the input and output as Strings, that is as lists of characters. Under that model an I/O program is a function
>
> listIOprog :: Str-\>Str
>
> This obviously makes sense in a 'batch' program, where al, the input is read before any output is produced but in fact it also works for interactive programs where input and output are interleaved, if the language is lazy. **This is because in a lazy language we can began to print the result of a computation - the output of the interactive program here - before the arguement - the interactive input - is fully evaluated.** As an example, repeadtely to rever lines of input under this model one can write
>
> listIOprogram = unlines. map reverse . lines

I don't understand the bolded line. How can we evaluate the output before the actual inputs are given? For eg, take the function Sum x y = x+y, what would it mean to evaluate this without any numbers are given.

# Answer
> 1 votes
Addition is not a good example for this because it does need both of its inputs. Laziness comes into play for functions whose output may not depend on all of the input.

An example of laziness that can be found in virtually all mainstream programming languages is the boolean operator `&&` (and its sibling `||`). Conventionally, `X && Y` first evaluates the expression `X`, then if `X` is true, it evaluates `Y`. But if `X` is false, it skips evaluating `Y`, ignoring any of its side effects.

Lazy evaluation of the following program will interleave input (`read_bool`) and output (`write_bool`):

```
let x = read_bool() in
let y = read_bool() in
write_bool(x && y);
write_bool(y)

```

Lazy evaluation follows demand: we do not evaluate `read_bool()` immediately when we encounter the binding `x = read_bool()`, because `x` might not be needed in the end. Instead, `write_bool` is the operation that drives evaluation, because the value must be known before `write_bool` can print it.

The evaluation of that expression can be broken down as follows, with **IO operations written in bold**.

1. `write_bool(x && y)` demands `x && y`
2. `x && y` demands `x`
3. `x = read_bool()` **reads a boolean**. For example, `x = false`. Now we can go back to the previous expression that demanded `x`.
4. `false && y = false` (by definition of `&&`).
5. `write_bool(false)` **writes `false`**.
6. `write_bool(y)` demands `y`
7. `y = read_bool()` **reads a boolean**. For example, `y = true`.
8. `write_bool(true)` **writes `true`**.

That is how lazy evaluation lets us interleave IO operations even though in the source expression, all input operations appeared before all output operations.

---
Tags: functional-programming
---


# Question
Title: what is the complexity of this sorting algorithm?
```
public class SortAlgorithm {
public static void sort(int[] A) {
    quickLevel(A, 0, A.length - 1);
}

private static void mergeLevel(int[] A, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        quickLevel(A, l, m);
        quickLevel(A, m + 1, r);
        merge(A, l, m, r);
    }
}

private static void quickLevel(int[] A, int l, int r) {
    if (l < r) {
        int m = partition(A, l, r);
        mergeLevel(A, l, m - 1);
        mergeLevel(A, m + 1, r);
    }
}

```

I want to find the complexity of this function, but it isn't very clear because mergelevel and quick\_level are calling each other recursively. I hope someone can give me some tips

The "merge" function is used in merge sort to merge two sorted arrays, working in O(n) time complexity. The "partition" function, used in quicksort, selects the first element as the pivot and finds its correct location in the array, placing it there. Its complexity is also O(n).

# Answer
> 1 votes
Let $M(n)$ be the runtime of mergeLevel on an input of size $n$, and let $Q$ be the runtime of quickLevel on an input of size $n$.

By inspecting the code, we see that $M(n) = 2Q(\frac{n}{2}) + n$ and $Q(n) \leq n + \max\_{1 \leq i \< n} M(n - i) + M(i)$. We can then just substitute, and henceforth ignore $M$:

$$Q(n) \leq 2n + 2\max\_{1 \leq i \< n} Q(\frac{n - i}{2}) + Q(\frac{i}{2})$$

The worst case for the maximum is going to be $i = 1$, which leads us to $Q(n) = O(n^2)$.

---
Tags: algorithms, recurrence-relation, recursion, big-o-notation
---


# Question
Title: Name of class of errors where the real state differs from the recorded state?
Is there a name for the class of software errors that arise from the fact that the software believes something wrong about the state of the world?

(Allow me a bit of anthropomorphization of software, for the sake of explanation.)

One example:

> A temperature sensor correctly reads 19°C, but the software accesses its memory location in the wrong way and ends up reading 24°C.
>
> This mismatch between the real value (19) and the believed value (24) would then kick-off some actions that are reasonable for 24°C, but not for 19°C.

The bug here is not that the wrong actions have been performed, because they are consistent with the state that that software believes to exist. The bug here is in the fact that the software formed a belief that does not match the reality. From there on other reasonable but wrong things happened (a classic case of *ex falso quodlibet*).

Another example:

> A network interface is up, but configured in a way that makes the operating system believe that it actually down.
>
> Programs asking the OS "is the network working?" will get the wrong answer but will trust it and act accordingly (for example showing stale Web pages from the offline cache).

TOCTOU errors would be a subclass of this more generic class of errors (TOCTOU errors are due to timing, the errors in the class I'm talking about can be caused by any issue.)

# Answer
Maybe ***hypnosis***, as used by Raymond Chen to describe a closely related set of bugs?

> It’s like saying, “I am a bad guy from a 1960’s spy movie. I have successfully hypnotized the victim into obeying all of my commands, while nevertheless behaving perfectly normally. I tell the victim to go to the bank, withdraw all their money, and bring it to me. This is a security flaw in the bank. It should not allow hypnotized people to withdraw money!”
>
> The bank did its job, which is to confirm the identity of the person withdrawing the money. The person at the counter did nothing to draw suspicion, and all the paperwork checked out, so they got their money.
>
> The system sees that there is a process running as the user, and that process is asking for the password that the user had saved earlier. Now, certainly, users are permitted to access the passwords that they had saved \[...\] and the Credential Manager is correct in returning those saved passwords to that user.

https://devblogs.microsoft.com/oldnewthing/20230206-00/?p=107797

The system ("the bank") did nothing wrong except trusting its reading of the state. All subsequent actions were compatible with that perceived state. Not real bugs there. The perceived bug is due to the fact that the system did not know that the state was a wrong reading of the reality (in this case because it has been manipulated, but it could happen also due to a mistake).
> 2 votes

# Answer
GIGO - Garbage In, Garbage Out.
> 1 votes

---
Tags: terminology, software-engineering
---


# Question
Title: Is $\{\langle \langle M\rangle, q\rangle\mid M(\varepsilon)$ enters state $q$ infinite times$\}$ not in RE?
I'm trying to use reduction $\overline{HP} \leq L$, but I just can't think of a way to do so.
Any help would be appreciated!

# Answer
The machine would go in an infinite loop if there is at least one state that it visits an infinite number of times (By pigeon-hole principle).

**Hint:** Dovetailing
> 1 votes

# Answer
**Hint**: given a Turing machine $M$ and a word $w$ over $M$'s alphabet, consider a machine $T$, that on the empty word simulates the run of $M$ on $w$. Can you force $T$ to visit a state infinitly often if the simulation does not halt? Note that ofcourse there is such a state but we do not know it in advacnce to output it in the reduction, but there is a simple way around this: you can modify the simulation anyway you see fit.
> 0 votes

# Answer
I got it.
Using reduction $\overline{HP} \leq L$ with $f\left ( \left ( \left \langle M \right \rangle ,x \right ) \right ) = \left ( \left \langle M\_x \right \rangle ,q\right )$ where $M\_x$ is a TM which simulates M on input x, but between every two steps, it goes into state q. If $M\_x$ halts, reject.
This means that if $\left ( \left \langle M \right \rangle ,x \right ) \in \overline{HP}$ then M does not halt on x, which means $M$ will be in an infinite loop which means $M\_x$ will visit state q infinite times.
If $\left ( \left \langle M \right \rangle ,x \right ) \notin \overline{HP}$ then $M$ will halt which means $M\_x$ visits q $n \in \mathbb{N}$ times.
> 0 votes

---
Tags: turing-machines, reductions, halting-problem
---


# Question
Title: What is the precise difference between state and environment and memory?
I was just reading this question regarding the difference between **environment** and **memory**. However, the textbook in question, *Essentials of Programming Languages*, third edition, by Friedman and Wand, also has chapter **4 State**, which, as it says, discussed the concept of **state**. But, as far as I can tell, it doesn't seem to explicitly differentiate between **environment**, **memory**, and **state**, and it is unclear to me what the difference is. What is the precise difference between **state** and **environment** and **memory**?

# Answer
> 2 votes
Very informally:

An **environment** is a set of pairs (variable+value) that are accessible to a particular object/process during its execution.

A **memory** is a set of "locations" in which an object/process can read/store information. Usually a location is associated with a variable and the value of the variable is stored in that location (or in several locations).

The **state** of an object/system is the set of values of the properties (variables) of the object/system in a particular point in time (during an execution or process).

The big picture:

* variables are logical "names" for values that can change in time (modified during the execution). They are called *constants* (from the viewpoint of a particular object/process) if the object/process cannot modify them.
* environment refers to a set of variables from the viewpoint of an object/process; the object/process can read or (if allowed) modify them. Note that the emphasis, when talking about "environment", is usually on the "variables", not their (current) values.
* memory is the place where variables are stored. Note that memory is a concept that is at a lower (implementation) level. To define a high-level programming language there is no need to "talk about memory" unless you need to implement it on a real architecture; but it can be useful to understand other concepts such as variables or arrays.
* state is a "dump" ("snapshot") of the variables+current values (hence implicitly also a dump of the memory where they are stored) in a particular point in time of the execution/process

# Answer
> -1 votes
I believe you can consider state and environment to be the same thing. The difference is mostly when writing logical deductions. The environment is the context that makes a given proposition true and may be a just a part of the global state. What memory introduces is **aliasing**; $A\[i\] = x$ may be falsified by a preceding $A\[j\] \leftarrow y$ if $i = j$. Without memory you don't have aliasing and the value of a variable is always the last value assigned to it.

---
Tags: programming-languages, static-analysis
---


title: Hardwiring input in DFAs and PDAs

text:
# Question
Title: Hardwiring input in DFAs and PDAs
A Turing Machine can be converted into a Turing Machine that has a specific input coded into it's description. This Turing Machine can then be run on empty input. Can we do the same for PDAs or DFAs?

I am familiar with models of computation such as Conway's Game of Life where the rules are fixed and the entire computation solely depends on the initial state. It is also easy to imagine this in a Turing Machine where **the input is encoded on the tape.**

I would imagine it might be possible for a model like Push-Down Automata where the input is encoded in the stack, but I am unaware if there is a formal construction of this sort. How would one do this for a DFA?

# Answer
> 0 votes
Yes. You can easily build a PDA or DFA that immediately halts and rejects (regardless of its input); and you can easily build one that immediately halts and accepts (regardless of its input). Those are the only two cases you need, so the answer to your question is yes.

---
Tags: finite-automata, pushdown-automata, computation-models
---


# Question
Title: Is a language *engine* the same as a language *implementation*?
(This may just be a terminology clarification question.)

Wikipedia says

> A language usually has at least one implementation in the form of a compiler or interpreter, allowing programs written in the language to be executed.

And reading the page on programming language implementations:

> In computer programming, a programming language implementation is a system for executing computer programs.

This page also gives CPython and PyPy as examples. So I think we can safely conclude that those are implementations.

Searching for "CPython engine" or "PyPy engine" gives me very few results. So are CPython and PyPy "engines"?

But if we then look at V8, both their docs and the Wikipedia page for V8 use the term "engine" but the docs also state V8 *implements* the ECMAScript standard. Is this because V8 is more than just an implementation of ECMAScript? Would it be more precise to say that V8 *contains* an implementation of ECMAScript?

Or could it be that these projects have chosen to use one term over another and the communities around them have followed suit? It kinda feels like "implementation" is the more computer science-y term for it and "engine" was chosen by V8 to sound less daunting?

Thanks!

# Answer
> 2 votes
I've never heard of the phrase "language engine" before, so I don't think you need to worry about knowing that phrase. Perhaps it is used in certain communities, such as browsers. From context, it sounds like a Javascript engine is a subsystem of a browser that provides a Javascript interpreter/JIT plus interfaces to all of the browser APIs. I wouldn't worry about it.

---
Tags: compilers, interpreters
---


# Question
Title: Knapsack Problem for Fixed weight and Fixed price
Is the knapsack problem for a target weight, let's say 1000 for example, and a target price, let's say 10000, still an NPC problem?

# Answer
Probably not. If you have $n$ items, and a capacity of $W$, there is a pseudo-polynomial time algorithm using dynamic programming that runs in $O(Wn)$ time. Thus, for any constant weight, we can solve the Knapsack problem in linear time.
> 1 votes

---
Tags: algorithms, np-complete
---


title: Ω(f(x)) and worst case analysis

text:
# Question
Title: Ω(f(x)) and worst case analysis
I'm currently reading *The Algorithm Design Manual* by Steven S. Skiena as my first book to algorithms.

Something in the asymptotic part is kind of confusing to me.

> **Proving the Theta**
>
> The analysis above gives a quadratic-time upper bound on the running time of this simple pattern matching algorithm. To prove the theta, we must show an example where it actually does take $Ω(mn)$ time.
>
> Consider what happens when the text $t = “aaaa \ldots aaaa”$ is a string of $n$ $a$’s, and the pattern $p = “aaaa \ldots aaab”$ is a string of $m − 1\ a$’s followed by a $b$.
> Wherever the pattern is positioned on the text, the **while** loop will successfully match the first $m − 1$ characters before failing on the last one. There are $n − m + 1$ possible positions where $p$ can sit on $t$ without overhanging the end, so the running time is:
>
> $$(n − m + 1)(m) = mn − m^2 + m = Ω(mn)$$

This example is clearly meant to be the worst possible running time of the algorithm, however, instead of $O(mn)$, $Ω(mn)$ has been used.

Isn't $Ω$ the lower bound of the algorithm, meaning for big enough $n$(s) the algorithm cannot perform better than this?

If it is then why is $Ω$ used to show the worst performance, shouldn't Big Oh be used instead?

Any help would be much appreciated.

# Answer
I think this is a common misconception among undergraduates about $\mathcal{O}$, $\Omega$, and $\Theta$. It is not like these symbols represent worst, best, and average case running time, respectively. They are just upper and lower bounds on running times and you can have lower and upper bounds on all of those cases.

In some sense, $\Omega$ is just the *pessimistic view* of the worst case running time. This shows that in the worst case (e.g. the word+pattern of your problem) you cannot expect a running time that is faster than $c \cdot mn$ for some constant $c$. However, the first paragraph of *Proving the Theta* suggests that they also show that the algorithm is guaranteed to run in time $\mathcal{O}(mn)$, this is the *optimistic view*, stating that you will never find and example where the running time is worse than $c' \cdot mn$ for some constant $c'$. Both parts combined give you that the running time is in $\Theta(mn)$.
> 5 votes

# Answer
By showing a worst-case example, it doesn't show $O(mn)$ ... big-O is an upper bound, so when asserting a big-O runtime, it says that that algorithm takes $O(mn)$ time or better (remember that an $O(n)$ algorithm is also an $O(n^2)$ algorithm). But showing that there is an example that actually requires $kmn$ time means that the big-O runtime of $O(mn)$ cannot be any smaller function ... That is, showing an example of where an algorithm requires $kmn$ time is a way to show the algorithm cannot be any better than $kmn$, meaning it is $\Omega(km)$. And once you have both $O(mn)$ and $\Omega(km)$ then you have $\Theta(mn)$.
> 1 votes

# Answer
One thing I would like to add is that $O$, $\Omega$, $o$, $\omega$, and $\Theta$ are all about relating functions to one another. In particular for functions $f$ and $g$, $f(x)\in O(g(x))$ says that (in some sense) $g(x)$ is an upper bound for the function $f(x)$, and $f(x) \in\Omega(g(x))$ says that (in some sense) $g(x)$ is a lower bound for $f(x)$.

In the context of computer science and runtime analysis, the function $f$ that we care about is (usually) the function that takes in a natural number $n$ and returns the maximum running time of an algorithm on any instance of size $n$. When we say that an algorithms running time is $O(g(n))$ or $\Omega(g(n))$ what we actually mean is that this "worst-case running time" function is $O(g(n))$ or $\Omega(g(n))$. So, for an algorithm to be $\Omega(g(n))$, we don't need to show that the running time is lower bounded by $g(n)$ for every instance of size $n$, just for at least one instance.
> 1 votes

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


# Question
Title: How to show L is non-regular without pumping lemma?
$L=\\{(ab)^n : n\text{ is a natural number apart from }6\\}$, I want to show L is non-regular by finding an infinite set of L-distinguishable words. Could you help me?

# Answer
> 8 votes
Well, you can't show that it is not regular, because it is regular.

Indeed, $L = (ab)^\*\setminus \\{(ab)^6\\}$, and $(ab)^\*$ is regular (concatenation + kleene star), and $\\{(ab)^6\\}$ is regular (because it is finite), and regular languages are closed under difference.

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


title: Parallel prefix sum/scan on trees

text:
# Question
Title: Parallel prefix sum/scan on trees
Let $T$ be a rooted, finitely branching tree, with values from $A$ in its nodes; $T(j)$ is the value of a node called $j$. $A$ is a commutative monoid. The "bottom-up scan tree" of $T$ is a rooted tree $T^\ast$ isomorphic to $T$, such that if $j$ is a leaf of $T$, $T(j)=T^\ast(j)$, and otherwise $T^\ast(j) = \sum\_{i\leq j}T(i)$, where $i\leq j$ indicates that $i$ is a descendant of $j$.

1. What algorithms exist to compute $T^\ast$ quickly on a parallel random access machine?
2. Is there an algorithm which performs in time strictly less than $O(N)$, even in the pathological case where $T$ is a linked list?
3. In the real world, how should $T^\ast$ and $T$ be implemented in order to get good performance on a GPU?

My motivation comes from studying the description of the network simplex algorithm in the book "Network flows" by Ahuja and Magnanti, where this problem appears as "compute-flows" in section 11.4. I am trying to solve optimal transport problems.

I think that it should be relatively straightforward to solve this problem in a loop indexed by the height of tree, where the time of each loop iteration is at most $\log(N)$. If the tree is balanced, then this algorithm suffices, and there is no need for sophisticated algorithms. However, I can see no reason why the trees in the network simplex algorithm for minimum flow cost should be reasonably balanced. (If there are adaptations of the network simplex algorithm where the tree is always balanced, I would be interested in hearing about this.)

# Answer
Here is one approach that ought to run fast on real hardware. Store the structure of your tree in an array $P$ so that the parent of node $i$ is found at $P\[i\]$. For example, with $$ P = \[-1, 0, 0, 2, 3\], $$ $P\[3\] = 2$ so the parent of node 3 is node 2. -1 is a dummy value for the parent-less root node. Store all the intermediate sum of the nodes in an equally long array called $V$. Create another array $C$ with all elements set to 0 where you compute how many children each node has:

```
N = len(P)
C = [0] * N
for i in range(N):
    C[P[i]] += 1

```

Now process the tree in bottom-up order. Leaf nodes are childless, so we begin with those:

```
changed = False
parfor i in range(N):
    if C[i] == 0:
        C[i] -= 1
        atomic C[P[i]] -= 1
        atomic V[P[i]] += V[i]
        changed = True

```

So for every leaf node, we set its child count to -1 to indicate that it has been processed. Then we decrement the parent's child count.Effectively, this generates new leaf nodes and we can iterate the process until no work remain:

```
while True:
    changed = False
    parfor i in range(N):
        if C[i] == 0:
            C[i] -= 1
            atomic C[P[i]] -= 1
            atomic V[P[i]] += V[i]
            changed = True
    if not changed:
        break

```

I've invented the keyword "parfor" to denote loops whose iterations can run in parallel and the keyword "atomic" for operations that must run atomically as multiple threads may write to the same memory. There are many standard approaches for handling this effectively. I've also glossed over handling of the parent-less root note. But it's easy to add checks for. If memory is the bottleneck you could rearrange the tree so that nodes and their children are close. I.e, the $|i - P\[i\]|$ should preferably be small.
> 1 votes

---
Tags: trees, parallel-computing
---


# Question
Title: Express a language containing the words with an odd amount of 0's using the languages $\{0\}$ and $\{1\}$
This is a homework question and after struggling with it for a while, I have decided to ask for help here.

The task is to construct a language over the alphabet $\\{0,1\\}$ consisting of precisely those words $w$ with the property that $\\#\_0(w)$ is an odd number, i.e. the count of 0's in those words is odd (eg. $010,10011,00$ would all be words in this language). This language must be constructed using the languages $\\{0\\}$ and $\\{1\\}$ and a finite number of the following operations: union, intersection, set difference, complement, Kleene star, Kleene plus, concatenation and reverse. It's clear to me that I can equivalently construct a language with words whose count of 0 is even and then consider the complement. However, I cannot seem to come up with a way that can capture the parity of the amount a certain symbol appears in a word.

# Answer
The following language is the language of even number of 0's: $$ \\{1\\}^\*\cdot (\\{0\\}\cdot \\{1\\}^\*\cdot\\{0\\}\cdot \\{1\\}^\*)^\*$$

I leave correctness to you. Then, you can complement by taking its difference from the set of all words:

$$ (\\{0\\} \cup \\{1\\})^\*\setminus (\\{1\\}^\*\cdot (\\{0\\}\cdot \\{1\\}^\*\cdot\\{0\\}\cdot \\{1\\}^\*)^\*)$$

Also, it is not hard to obtain a representation of the language without using complementation.

**Hint:** think regular expressions that do not have $\epsilon$ in their syntax.
> 1 votes

---
Tags: formal-languages
---


# Question
Title: Create NFA where |w|_a is divisible by 2 or |w|_b is divisible by 3
I have to create an NFA $\mathcal{A}$ that accepts the language $L = \\{w \in \Sigma^\* \ | \ |w|\_a \ \text{is divisible by 2 or} \ |w|\_b \ \text{is divisible by 3} \\}$

So the NFA only accepts words with $|w|\_a \ mod \ 2 = 0$ or $|w|\_b \ mod \ 3 = 0$.

This is the NFA that I constructed but it is not enough. What is the full correct NFA?

# Answer
**Hint:**

1- The language $L$ can be written as the union of two simple regular languages.

2- $\epsilon$ is in the language.

3- When you design an automaton for all words $w$ with $\\#\_a(w) \mod 2 \equiv 0$, then you should allow for an arbitrary number of $b$'s to appear anywhere in the input $w$.
> 1 votes

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


title: Decide whether this Problem NPC or P?

text:
# Question
Title: Decide whether this Problem NPC or P?
Input: A finite set A, subsets S1, . . . , Sn ⊆ A, and a number k ∈ N. Question: Does there exist a set R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n? I read somewhere (without mentioning why) that it's an NP-complete problem, but I think it can be solved simply by taking the union of all subsets and comparing it to k. If it isn't equal to k, then we can't form a subset R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n. is it an NPC problem or P problem ?

# Answer
> 2 votes
Right, it is in $\text{PTIME}$. The condition $|R\cap S\_i| = |S\_i|$ is equivalent to $S\_i\subseteq R$. So the problem is to find a subset $R$ whose size is $k$ and contains all sets in $\\{S\_i\\}\_{i\in \[n\]}$. In other words, $ \bigcup\limits\_{i\in \[n\]} S\_i \subseteq R$. So you can simply find the smallest such set $\bigcup\limits\_{i\in \[n\]} S\_i$ and then compare $|\bigcup\limits\_{i\in \[n\]} S\_i|$ to $k$. If $|\bigcup\limits\_{i\in \[n\]} S\_i| \> k$ or $k \> |A|$, then there is no such set $R$. Otherwise, there is such a set.

As a conclusion, the problem is not known to be $\text{NP-complete}$, since we do not know yet whether $\text{PTIME} = \text{NP}$.

---
Tags: np-complete, sets
---


# Question
Title: turing recognisable = complement of co-recognisable
Define: RE = {L : L is recognizable by a TM}, R = {L : L is decidable by a TM}, and coRE = {L : L-complement is recognizable by a TM}.
The question is: Does the complement of coRE equal RE?
I know that the answer is false, but I'm not sure why my proof is wrong:

# Answer
> 1 votes
Let $A=\\{ \overline{L'} \in \Sigma^\* \mid L' \in \mathsf{RE} \\}$ (notice that I renamed the variable used in the definition of the set to avoid confusion). It is false that $L \in A \iff L \in \mathsf{RE}$.

To see this consider the language $H$ of the halting problem, which is well-known not to be decidable. $H \in \mathsf{RE}$ since you can simply simulate a Turing Machine until it halts (possibly never) and then accept. However $H \not\in A$. Indeed, $H \in A \iff \overline{H} \in \mathsf{RE}$ but $\overline{H}$ is not recognizable (otherwise both $H$ and $\overline{H}$ would be recognizable, which would imply that $H$ is decidable).

# Answer
> 1 votes
I'm assuming you mean $L \in P(\Sigma^\*)$ instead of $L \in \Sigma^\*$. Remember that by $\\{x \in D | \varphi(x)\\}$ we simply denote $\\{x | x \in D \land \psi(x)\\}$ and $\overline{\\{x | \varphi(x)\\}} = \\{x | \neg \varphi(x)\\}$.

The mistake is in the second equivalence of your proof, you assert that $$L \in \overline{\\{L \in P(\Sigma^\*) | \overline{L} \in \texttt{RE}\\}} \iff L \in \\{\overline{L} \in P(\Sigma^\*) | L \in \texttt{RE}\\}$$ which is equivalent to $$\neg(L \in P(\Sigma^\*) \land \overline{L} \in \texttt{RE}) \iff \overline{L} \in P(\Sigma^\*) \land L \in \texttt{RE}$$ but this is invalid (try applying DeMorgan's laws to the lhs).

The third equivalence isn't valid either, it's not the case that $$L \in \\{\overline{L} \in P(\Sigma^\*) | L \in \texttt{RE}\\} \iff L \in \texttt{RE} = \\{L \in P(\Sigma^\*) | L \in \texttt{RE}\\}.$$

# Answer
> 1 votes
Note that a language $L$ is a subset of $\Sigma^\*$ and not an element in $\Sigma^\*$, and here we're considering classes of languages. So I assumed that you meant $L$ is a language over $\Sigma$.

It looks like you have complemented the set $\\{ L \subseteq \Sigma^\*: \overline{L}\in \text{RE} \\}$ incorrectly. Specifically, you assumed that: $$\overline{\\{ L \subseteq \Sigma^\*: \overline{L}\in \text{RE} \\}} = \\{ \overline{L}\subseteq \Sigma^\*: L\in \text{RE}\\}$$

but this is incorrect as you should complement the set $\\{ L \subseteq \Sigma^\*: \overline{L}\in \text{RE} \\}$ as follows: $$\overline{\\{ L \subseteq \Sigma^\*: \overline{L}\in \text{RE} \\}} = \\{ L \subseteq \Sigma^\*: \overline{L}\notin \text{RE} \\}$$

In general, if we have a condition $c$ and a set $A$ given by $A = \\{ x: \text{$x$ satisfies $c$}\\}$, then $\overline{A} = \\{ x: \text{$x$ does not satisfy $c$}\\}$.

Note that:

* $\\{ \overline{L}\subseteq \Sigma^\*: L\in \text{RE}\\}$ is the class of languages whose complement is in $\text{RE}$, and thus it is actually $\text{coRE}$. So you also have another mistake in the last equivalence, not only in the middle one.
* $\\{ L \subseteq \Sigma^\*: \overline{L}\notin \text{RE} \\}$ is the class of languages whose complement is not in $\text{RE}$, and thus it is actually $\overline{\text{coRE}}$, which is the class you've started with, and that makes sense...

---
Tags: turing-recognizable
---