# Question
Title: How to devise an algorithm to generate a random but valid train track layout?
I am wondering if I have quantity C of curved tracks and quantity S of straight tracks, how I could devise an algorithm, (computer assisted or not), to design a "random" layout using all of those tracks, such that the following rules are satisfied:

1) The tracks, when all connected, form a closed (continuous) loop for the train to go around.

2) Ramps, bending of tracks, bumping of tracks, crossing of tracks are all not allowed.

3) C and S will both be even numbers. An example would be C=20 and S=10. Note that it takes 12 curves in the same orientation to make a complete circle of 360 degrees so at least 12 of those curves need to be oriented the same way to complete the 360 degrees. The others can "zigzag" as long as the net result is 360 degrees so the train has a complete loop.

Straight tracks are about 10 inches (25.4 cm) long and curved tracks are about 12.4 inches (31.6 cm) long (down the center, following the curve) and curve 30 degrees. The "ties" on the tracks have a maximum width of 3 5/8 inches (9.2 cm). I placed a straight and curved track on top of each other and measured that the 12.4" (31.6 cm) curve has 12" (30.5 cm) of linear length (in the same direction as the straight), and 3" (7.6 cm) of bend (in the perpendicular direction of the straight). A 12C circle has diameter of 47.5" (120.6 cm) from center to center of the tracks on opposite sides.

All measurements are approximate.

**UPDATE**

I re-measured the tracks using many more of them to help eliminate errors and somewhat to my surprise, the length of the straights are NOT 10 inches, they appear to be about 9.78 inches. This has a significant impact on the matching of zigzag curves to straights. Originally I thought 4 zigzag curves = 5 straights but that is not quite correct. 4 curves has about 47" of linear distance so 5 straights at 9.78" each would be 48.9", almost 2 inches longer. So the trick it to find the LCM (Least Common Multiple) of 47 and 9.78. It turns out to be 235. 235 = 47\*5 and 235/9.78 = 24.028... (close enough). That means 20 zigzag curves is virtually the same as 24 straights in linear length. Luckily I have 26 straights so I just barely made it. The 2 leftover can easily be positioned elsewhere in the layout.

Another thing I discovered is that if I zigzag the curves 2 the same orientation at a time (OOCCCCOO), then 8 of those has a linear distance of only 83 inches, not 94 inches like if I alternate curves (OCCOOCCO). The LCM of 83 and 9.78 is about 166. So 16 of those curves has the same linear length as 17 straights. That is useful to know because I have 44 curves and only 26 straights but if I do this substitution, I can help make up for that.

If I zigzag the curves 3 at a time (OOOCCCCCCOOO) and bend it just slightly, I can get the exact linear length of 10 straights (about 97.8 inches).

**END OF UPDATE**

So would the computer program have to create a geometric model and remember the exact positions of each track or is there some simpler way to code this? I want to be able to "push a button" and the computer "spits out" a valid "new" layout for me.

I want to give this working algorithm to kids that use the trains, so they don't get frustrated attempting a layout that doesn't work and then they try to bend the tracks to make it work or have to leave out a few track pieces cuz they don't fit. A computer can create a valid layout using all of the tracks and if the algorithm is good, perhaps in a few seconds. This is to help prevent frustration for them.

I have some coding skills but I need to know an algorithm first before I can code something meaningful (other than just testing a few parts of a candidate algorithm)

What I am thinking is I could have the computer model the tracks using a smaller (scaled down) representation. I think it could then just "place" the tracks in the candidate layout and check for collisions with other tracks already there.

I am thinking there are probably better ways to do it though, so that is why I am asking here for some help/ideas. I really want to get this to work and I have the tracks here so I can use them to help verify if the algorithm is working.

We can use C=20 and S=10 as the parameters to try to solve this because it is a reasonably small number of tracks (30 total). I am assuming if the algorithm is robust enough, C and S values can be changed at will and it will still work. For example, eventually I want to try C=44 and S=26.

**Final word**

Thank you all for your comments and suggestions regarding this question. I learned a lot too. As a kid I never really thought much about train tracks and how they fit together but as an adult, I can see it is a fascinating geometric problem and a very difficult mathematical counting problem to generate / figure out how many different (unique) track layouts there are. I hope you enjoyed this exercise as much as I did. The kids appreciate it too.

**End Final word**

# Answer
> 1 votes
I thought I would offer the brute force solution.

The idea is to try every single track layout in turn. When constructing a layout, there are only three pieces that need to be taken into consideration: a left handed curve, a right handed curve and a straight.

You can encode the track layout as a base 3 number with a width corresponding to the number of pieces in the layout. To enumerate all track layouts just count in base 3, where the encoding goes 0=straight, 1=left and 2=right.

The next stage is to check that the layout joins up at both ends. The first check is to make sure there are enough curves to go one complete circuit. If we choose an anti-clockwise sense for one circuit, then 12 left curves are needed. For every extra right curve, we need to add on extra left curve. So to check the particular layout might work, just add the number of left curves and subtract the number of right curves - this must equal 12.

Lastly, we need to check the ends actually meet. We simply plot the track on a cartesian grid. We start the origin at \[0,0\] and if it ends at \[0,0\], then it joins.

The simplest way to plot the track is LOGO style. In other words we maintain a direction vector which points in the direction of the last layed track piece. If we encouter a left curve, then rotate the direction by 30 degrees and for a right curve rotate by -30 degrees - a straight does not affect the direction.

To actually plot the curves and straight, we scale up the direction vector by the size of the piece, i.e. 10 units for a straight, and 12.4 x 12 / 2 x pi (radius of complete circular track) units for a curve.

**CAVEATS**

Due to rounding errors in adding up floating point numbers, the plotting is not exact. And in real life we can leave some wiggle room for the ends to meet, so this needs to be catered for.

Many layouts will be the same, but shifted by one position. I can't see a way to exclude duplicate shifted layouts other than to keep previous ones and check against them.

The algorithm does not exclude layouts where pieces cross. In order to do that, you would have to check that each piece in a layout does not cross another piece in the layout (thats O(n^2)). And there would have to be checks for curve-curve, curve-straight and straight-straight crossings, and that starts to get very complex.

The running time of the algorithm is obviously O(3^N) which is exponential - and probably impractical for very large layouts.

Below is some VBA code you can paste into Excel to give you proof of concept. I've deliberately tried to keep the code as simple as possible to aid conversion to your favourite language. Any questions, please feel free to ask.

```
Option Explicit

Type Vector
    X As Double
    Y As Double
End Type

Sub GenerateTrackLayout()
    Dim lCounts(40) As Long
    Dim lColumn As Long
    Dim lTrackLength As Long
    Dim lCurveSum As Long
    Dim lIndex As Long
    Dim lIndex2 As Long
    Dim vDirection As Vector
    Dim vBase As Vector
    Dim vTrackPosition As Vector
    Dim fPI As Double
    Dim fCurveRadius As Double
    Dim fStraightLength As Double
    Dim sPath As String
    Dim lOutputRow As Long
    Const TOLERANCE = 0.5 'inch

    lOutputRow = 1

    vBase.X = Sqr(3) / 2 ' 30 degrees
    vBase.Y = 1 / 2 ' 30 degrees

    fPI = 4 * Atn(1)
    fCurveRadius = 12.4 * 12 / (2 * fPI)
    fStraightLength = 10

    lTrackLength = 12 ' initial track length

    Application.ScreenUpdating = False

    Do
        ' Check for closed track
        lCurveSum = 0

        For lIndex = 0 To lTrackLength - 1
            If lCounts(lIndex) = 1 Then
                lCurveSum = lCurveSum + 1
            ElseIf lCounts(lIndex) = 2 Then
                lCurveSum = lCurveSum - 1
            End If
        Next

        If lCurveSum = 12 Then ' one 360 degree rotation anti-clockwise
            vDirection.X = 0
            vDirection.Y = 1
            vTrackPosition.X = 0
            vTrackPosition.Y = 0

            ' Plot the track and ensure that ends meet
            For lIndex = 0 To lTrackLength - 1
                Select Case lCounts(lIndex)
                    Case 0 ' straight
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fStraightLength))
                    Case 1 ' left curve
                        vDirection = MultiplyVectors(vDirection, vBase, 1)
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fCurveRadius))
                    Case 2 ' right curve
                        vDirection = MultiplyVectors(vDirection, vBase, -1)
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fCurveRadius))
                End Select

                ' If ends meet within tolerance then output the track
                If Abs(vTrackPosition.X) < TOLERANCE Then
                    If Abs(vTrackPosition.Y) < TOLERANCE Then
                        If lIndex = (lTrackLength - 1) Then
                            sPath = ""
                            For lIndex2 = 0 To lIndex
                                Select Case lCounts(lIndex2)
                                    Case 0 ' straight
                                        sPath = sPath & "S"
                                    Case 1 ' left
                                        sPath = sPath & "L"
                                    Case 2 ' right
                                        sPath = sPath & "R"
                                End Select
                            Next
                            Application.ScreenUpdating = True
                            Cells(lOutputRow, 1).Value = sPath
                            Application.ScreenUpdating = False
                            lOutputRow = lOutputRow + 1
                        End If
                    End If
                End If
            Next
        End If

        ' Count in base 3 where number width is Track Length
        lColumn = 0
        Do
            lCounts(lColumn) = lCounts(lColumn) + 1
            If lCounts(lColumn) = 3 Then
                lCounts(lColumn) = 0
                lColumn = lColumn + 1
            Else
                Exit Do
            End If
        Loop Until lColumn = lTrackLength

        ' We've tried all tracks of this length, next one up...
        If lColumn = lTrackLength Then
            Erase lCounts ' reset all columns to zero
            lTrackLength = lTrackLength + 1
        End If
        DoEvents
    Loop
End Sub

' Vector maths

Function MultiplyVectors(vVectorA As Vector, vVectorB As Vector, ByVal fConjugate As Double) As Vector
    MultiplyVectors.X = vVectorA.X * vVectorB.X - fConjugate * vVectorA.Y * vVectorB.Y
    MultiplyVectors.Y = vVectorA.Y * vVectorB.X + fConjugate * vVectorA.X * vVectorB.Y
End Function

Function AddVectors(vVectorA As Vector, vVectorB As Vector) As Vector
    AddVectors.X = vVectorA.X + vVectorB.X
    AddVectors.Y = vVectorA.Y + vVectorB.Y
End Function

Function ScaleVector(vVector As Vector, ByVal fScale As Double) As Vector
    ScaleVector.X = vVector.X * fScale
    ScaleVector.Y = vVector.Y * fScale
End Function

```

# Answer
> 4 votes
**One possible solution** to make this as simple as possible to quickly get a working algorithm would be as follows. The simplest layout is of course 12C (12 curved tracks all with the same orientation (relative to each other), and forming a simple circle. This will be the basis upon which we can build on.

So the basic algorithm will be to maintain the 360 degree continuous loop layout at every step when adding tracks. We can do this by examining how many curved tracks we have remaining, and adding them to the layout in groups such that the 360 degree property is maintained. For example, start with our 12C layout (a simple circle). We know we have 20C total so we have 8C remaining. The simplest addition of some of those that would maintain the 360 degree property would be to add a reverse orientation curve and a same orientation curve (same as the main circle we started with). We would then to do the same to the opposite side of the layout. In this simple example, we would have added 4 more curves to the circle layout so 12C would become 16C (with 4C leftover). We would continue placing curves until all 20 (in this example) are properly placed. Note that this layout consisting of all curves is a valid closed loop layout. The train can use this layout, however, it consists of all curved tracks so we are not yet done.

The straight tracks would then be inserted the same way except those can be added in pairs (2 tracks) since they are not changing the 360 degree property. They can be inserted anywhere so I think it would be best to first place ALL of the curved tracks, then go back and make a 2nd pass to place the straights randomly (but symmetrically).

This is the simplest algorithm I can think of for now. It is guaranteed to produce a 360 degree closed loop, a symmetrical track, and assuming the # of curves is a multiple of 4, and the # of straights is a multiple of 2, it will use each and every track.

One thing to consider though (when using this algorithm either on a computer or just in your mind as you are building the layout), is, there may be space restrictions more so in one direction than the other. For example, on a patio that is long, but not so wide. When using the algorithm, it should be biased more towards the long dimension of where the layout will be assembled.

If someone can figure out an algorithm to form an asymmetric layout using all of the tracks, that would be even more impressive.

The difference in complexity between the simplest solution and the most complicated is staggering. Starting with a circle (12C) is about as simple as it gets for this problem and is reasonable for kids, however it is very interesting to analyze a generic solution that can produce ANY valid layout (including asymmetric ones).

In reality, a non computer algorithm would be to just add some "cool" shapes to the layout and get it close to connecting, then go back and fine tune it so that it does indeed connect (for a closed loop). With 70 track pieces total (44C and 26S), a huge layout is possible. I calculated a total of about 67 feet of track which is about 20 meters. The train should take about 1 minute to loop that entire layout once.

**Another candidate solution** would be to take the actual measurements of each track and remember the rightmost edge of the layout. When building the layout, you can start with a straight track or with a left curve (counterclockwise), accumulating how far away the last added track is from that rightmost edge, and then when adding other tracks, never allowing a combination of tracks that will bump or cross that rightmost edge or maybe not even get close. So for example, start with a straight track (no 12C initial circle on this candidate solution), then randomly pick another track piece. Notice from the start we would NOT allow a right (clockwise) turn, since that would break the rule of "crossing" the rightmost edge. After the first straight track, our only options are another straight or a left (counterclockwise) curve. Another rule to enforce would be after a straight, we are not allowed to add more than 9 same orientation curves in a row, otherwise it will be likely to bump/cross some other tracks already in place. That limit could even be reduced to 8 for more clearance, and if that occurs, the next track MUST be a reverse oriented curve (since a straight may cause problems).

This algorithm would need some help to get it to come back and connect to the other side of that first added track piece. We can do that by insisting that counterclockwise curves count as +1 and clockwise curves count as -1, and those must add up to 12 on the last added curve. We can help this out by biasing the CC (counterclockwise) curves at a 4:1 ratio with clockwise curves, so that chances are we get 16 CC and 4 clockwise, which will effectively net a 360 degree circle. If the algorithm attempts to add a CC curve but bumps existing tracks, we have 2 options at that point, try an opposite orientation curve, or abandon the layout and start over. I would think that on a fast computer, eventually it will get a good layout.

I am not yet sure if this method would yield the all the same layouts as the starting with 12C, but perhaps it might be easier to implement on a computer since there are only a few rules to enforce, and we are building the layout one track at a time.

Actually, I just thought of a **3rd possible candidate solution** that should work and is not too difficult to implement. It goes as follows.

Use the technique described above, but only make a half layout (using half of the tracks of each type, so 10 curves and 5 straights. We have the computer pick random tracks but only accept layouts that end up with a net of 180 degrees of left turn (because we are enforcing a right border that no track can touch or cross. Okay so assume the computer very quickly finds a valid "half layout". Then what we do is simply take an inventory of how many clockwise curves, and counterclockwise curves there are, and duplicate that in the other half of the track (but not necessarily symmetrically). For the straights, we have to record at what angle they were inserted at then match them in the other half of the track, but again, not necessarily symmetrically.

Lets try an example using S for Straight, O for cOunterclockwise curve, and C for Clockwise curve. Concentrating on the half layout first.

The first straight track will be going away from us and that defines our rightmost edge that we are not allowed to cross.

SOOSOCSOOSSOOOC - This is a valid half layout since it has 5 straights and 10 curves with a net of 6 counterclockwise curves (2 of the 8 were "cancelled out by 2 clockwise curves).

Now we need to "keep tabs" on what angle the straights were inserted at and match those with a same angle (but opposite direction) track to "cancel" them out.

1: 0 degree angle straights
0: 30 degree angle straights
2: 60 degree angle straights
0: 90 degree angle straights
2: 120 degree angle straights
0: 150 degree angle straights
0: 180 degree angle straights

So to "match" this on the other half of the layout and make it so it connects to the single starting straight track, we just need to match the same number of Os and Cs, but also match the same # of straights at the +180 degree "returning" angle. For example, a 60 degree straight better have a 240 degree straight on the other side of the layout somewhere, not necessarily exactly opposite. This is because the 60 degree straight will go mostly to the left and a little up (using this scheme) and the 240 degree straight will bring it back to the right and back down the same amount to effectively "cancel" those 2 tracks contributions to deviating from the starting track position.

So now all we need to do to create the "missing half" of the layout is take the known tracks we need (and knowing at what angles the straights have to be), and just "scramble" them in any order.

There may be a way to NOT have to match exactly the one half of the layout with "complementary" tracks on the other side, but that would involve some more complex math and there probably isn't enough time to solve that in the time the bounty is active for. There is also a chance that not all the tracks would be used that way and some slight bending of the track would be required. We can ignore this special property for this question.

I actually made an asymmetric track to see if it would work and it seems it did. Using S for straight, O for cOunterclockwise curve, and C for Clockwise curve, plus the angle (in degrees) relative to the starting straight track, I got the following for the upper half:

S0, O30, O60, S60, O90, C60, S60, O90, O120, S120, S120, O150, O180, O210, C180

For the bottom half of the track I got:

O210, O240, S240, C210, O240, S240, O270, O300, S300, S300, O330, O360, O390, C360, S360

Actually the picture was taken from the wrong side so the top and bottom are flipped. The first track layed was the straight near the blue trashcan and coming towards the viewer of the pic and the 2nd track is the counterclockwise curve.

It seems like this technique would work for many even number of curves and even number of straights, including 44C and 26S which is my ultimate goal. This is really encouraging since an electronic computer isn't really necessary to solve this, I can just have the kids build just about any half circle shape they want with half of the tracks (22C and 13S), then "correct" their design so that it is 180 degrees, then "match" the other side of the track, not necessarily symmetrically.

You would have to be careful if you were to create 180 degree half layout where the starting track and the ending track are very close together. For example, the shape of the upper part of a question mark "?" (without the dot) but continue that upper curve so it comes around more and a straight going down from that would be very close to the straight that is above where the dot was. Then for the bottom half, you would NOT be able to do more counterclockwise curves right away since there are other straights there from the "top half". The image of my closed loop layout worked because I had no "bottlenecks" in the "upper" half but of course those are possible as I just described.

The "problematic" train layout is when one half of the track makes somewhat of an hourglass shape with a narrow middle. In that case, you almost have to "mirror" the top part because certain curves cannot be made since the tracks are so close to each other. Here is an example...

Another interesting observation is that 4 zigzag curved tracks is almost an exact replacement (as far as linear distance spanned) for 5 straights. However too many of these will create a significant difference in length. As stated in the UPDATED section above, 20 zigzag curves is almost an exact match (for linear distance) as 24 straights.

Using this technique, a giant layout can be made with all 70 track pieces. It would start with a 12C circle, then on one side, I could insert 24 straights (240 inches long). On the opposite long side of the layout (to almost match the length of the straight side), I would use 20 zigzag curves (also about 240 inches long). Those should almost line up and a slight bend should make it work. The remaining tracks (2 straight and 12 curved) could easily be placed to keep the layout "balanced" (and connected).

# Answer
> 4 votes
Firstly, a frame challenge:

> A computer can create a valid layout using all of the tracks and if the algorithm is good, perhaps in a few seconds

You don't need the algorithm to run in a few seconds. You need output in a few seconds. I don't see that there's anything stopping you from setting a brute force layout cruncher running on a computer in the corner and storing solutions in a database from which the UI can then select random layouts.

---

In terms of generation, there are a number of semi-standard approaches. The state space is rather large, so an exhaustive search may not be feasible. But any of the following might be worth a try:

* Pure random shuffling of a list of straights and equal numbers of left and right curves, followed by "goodness" test.
* Hill-climbing: start with a random permutation, and then test simple swaps to see whether they improve the "goodness". If they do, make the swap and repeat.
* Simulated annealing: similar, but sometimes allows changes which decrease the "goodness" in the hope of getting to a better hill.
* Genetic algorithm: generate lots of random permutations, and repeatedly mix them up and keep the best results. It's not entirely clear how to mix them, though.
* The latter three could start with "known good" curves generated by insertions into a circle.
* Explore options for meet-in-the-middle. E.g. generate all curves with a total angle of +90 deg, index them by 2D vector between the endpoints, and if there are many fewer vectors than there are curves you might be able to exhaustively consider quadruplets of them to find those which form a closed quadrilateral.

For "goodness" testing, there obviously needs to be a big penalty if the curve isn't closed. There also needs to be a large penalty for self-overlaps. I would be inclined to test those using a quad-tree to find segments which aren't consecutive but are close to each other, and then arc-arc, arc-line and line-line intersection tests to see whether any edge bounding one segment overlaps an edge bounding another.

---

Another strategy which might be able to completely brute-force the smaller case but not the larger would be to take an algebraic approach to the total vector. Let the length of the straight piece be $2\ell$ and the radius of the curved piece be $2r$. Since the orientations are all multiples of 30 degrees, the vector between the ends of a straight piece is in $$(0, \pm 2\ell), (\pm 2\ell, 0), (\pm \ell, \pm \sqrt3 \ell), (\pm \sqrt3 \ell, \pm \ell)$$ and similarly the vector between the ends of a curved piece is in $$(\pm r, \pm \sqrt3 r), (\pm \sqrt3 r, \pm r), (\pm (\sqrt3 - 1)r, \pm (\sqrt3 - 1)r))$$

Unless one of $\frac \ell r$, $\frac {\sqrt 3 \ell} r$, or $\frac \ell {\sqrt 3 r}$ is a fraction with a small numerator and a small denominator, curves and straights are independent, so you can find working sets of curves (brute force is enough for 20 curves of which 16 are in one direction and 4 are in the other; for 44 curves split 28-16 you need a better approach; I haven't worked through the implications of requiring the $+\sqrt 3$s to have a matching number of $-\sqrt 3$s, but they might allow some heavy filtering) and then insert straights in pairs. Applying this with brute-force for small numbers of curves would allow you to assess how many layouts you're potentially losing with the symmetric approach.

# Answer
> -2 votes
Assume that you start at the point (0, 0) going straight to the right. You need to add tracks until you reach the point (0, 0) again, this time straight from the left. There are two problems here: One is to reach the point (0, 0) coming from the left *exactly*. The other is to have no overlaps.

To form a counter-clockwise circle you will need 12 curved pieces turning left. These form an exact circle. With 0 or 24 or 36 curved pieces you'd have a figure eight or two or three circles, none of which can be done without crossing.

And of course you can add additional tracks, and these have to follow certain rules: You can add left-curved, straight, and right-curved pieces in pairs starting at angles of x degrees and x+30 degrees, so you return back to 0,0. And the number of left-curved pieces beyond the first 12 must match the number of right-curved pieces so the pieces match at the right angle at 0,0.

So that's the pieces you can use. You need to check that there are no crossings obviously.

If the lengths are exactly right then it might be that for example a combination left/right/right/left covers the exact same distance as four or five straights, so some other combinations may be allowed.

And of course tracks *are* bendy, which may produce many more possibilities.

---
Tags: computational-geometry, artificial-intelligence, randomized-algorithms
---


# Question
Title: Selecting elements from two arrays to get a target sum
Let $A$ and $B$ be two arrays of size $n$ with positive integer values. Let $k$ be a given positive integer.

Design an algorithm to solve the following problem.

For each index $i$ ($1\leq i \leq n$) either select $A\[i\]$ or $B\[i\]$ but not both such that the total sum of the picked elements from each of the arrays is at least $k$?

For example $A=\[1,2,3,4,5,49\]$ and $B=\[1,10,10,10,22,12\]$, target $k=50$.

**Solution**

Pick the first and the last elements from A whose sum is 50.

Pick the rest (all but the first and the last elements) from B. That sums up to 52.

So in both Arrays we get a sum at least the target value 50.

Can someone help me to find the algorithm to solve this problem?

# Answer
> 3 votes
Here is an algorithm using dynamic programming. Let us define the function $C:V\times \mathbb{N} \rightarrow \mathbb{N}$ as $C(i, s) = r$, if using only the first $i$ indices we can achieve a sum of at least $r$ in B, when having a sum at list $s$ in $A$. This means $C(i, s) = r$ if there is an index set $I \subseteq \[i\]$, such that $\sum\_{j \in I} A\[j\] \geq s$ and $\sum\_{j \in \[i\] \setminus I} B\[j\] \geq r$. If $s$ is greater than the sum of the first $i$ elements in $A$, then set $C(i, s) = -\infty$ It is easy to build the transitions of the dynamic programming as follows. For each $i$ and $s$: $$C(i+1, s) = \max\\{C(i+1,s), C(i, s) + B\[i\]\\}$$ $$C(i+1, s+A\[i\]) = \max\\{C(i+1, s+A\[i\]), C(i, s) \\}$$ The output is yes, if there is $s \geq k$ such that $C(n+1, s)\geq k$.

The correctness is pretty straight forward. The running time can be bounded in $O(nk)$.

On the other hand, this problem is NP-hard. It is easy to reduce the set partitioning problem to this problem. In the set partitioning problem, given a set of integers, you are asked to partition the set into two subsets having equal sums. Let $S$ be an instance of the set partitioning problem and $s$ be the sum of elements in $S$. Set $A = B = S$ and $k = s/2$. The correctness of the reduction is quite straight forward. That is why a **pseudo polynomial** algorithm (polinomial in the value of the input instead of its size) is the best we can hope for.

---
Tags: algorithms, dynamic-programming, arrays, greedy-algorithms
---


# Question
Title: How to make single cycle processor pipelined?
I was asked that *how can one make a single cycle processor pipelined* on a CS course without any specifications regarding the design.

I suppose, that I should answer that what should be changed on architecture level.

I am familiar with the meaning of pipelining.

I came up with the following basic idea: registers should be added to hold the intermediate values between pipelining input and output, which should be controlled by a common clock (including i/o).

Is my idea a plausible answer to the question?

At my level, I do not think that I am supposed to give a working example for it, but I am happy so any.

# Answer
> 0 votes
This is an example of a pipelined architecture. You mainly put register files (which introduce some delays) to save data from one stage to another. Think of it like assembling a car, the chasis is done in one stage then it waits (in our case storage is the Register File (RF) then it goes for the other stage...
To implement pipelining properly, you need to equally divide the stages of the pipeline so that you can minimize clock cycle. The clock cycle will be the inverse of the time of the longest stage of the pipeline (longest delay between two RFs) which is usually (in realistic cases) determined by memory accesses stage of the pipeline.
Also note that you always need to save all signals (control and data) between one stage and another.
So all in all different instructions will be using different parts of the pipeline.

# Answer
> 0 votes
If every complete operation takes one cycle, then pipelining using the same cycle time won't give you any advantage whatsoever.

What you would do is to split up each operation in various parts. First you make the cycle say four times shorter, so now each operation executes in four cycles. Then you split each operation into say five parts, and you have a first stage doing the first part and moving the results to the second stage, then a second stage doing the second part and moving it to the third stage, and so on. It will take all in all a little bit longer because you need the time to move data from one stage to the next.

And now you have five different stages, you can start pipelining. The first stage does the first part and moves the result to the second stage in the first cycle, and in the second cycle it starts work on the first part of the next instruction and so on.

You win because now the cycle time is four times shorter, so you can do up to four times more operations per second, working on up to five instructions at the same time.

---
Tags: cpu, cpu-pipelines
---


# Question
Title: Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?
$ \\# a^nb^{2^n} \\# $

such that

• The alphabet of the machine is {, a, b, x}.

• The symbol x will never appear on the input a.

• The contents of the tape at completion may be anything.

• The head begins on the lefthand #.

• n ≥ 0.

I know that a Turing machine could recognize this language. But can a NPDA recognize this language too? I am thinking it can but I do not know how to start proving how/why?

# Answer
> 1 votes
Actually this language is not a CFL.

---

**And here is a proof:**

Let's take string $w: a^mb^{2^m}$ where $m$ is constant guaranteed by pumping lemma for CFLs.

Then $a^{m+k\_1}b^{2^m+k\_2} \in L$ where $1\le k\_1,k\_2\<m$

(cases invloving either $k\_1 = 0$ or $k\_2=0$ are easier.)

Now, that suggests that,

$2^{m+k\_1} = 2^m + k\_2$ (by defination of $L$)

$\therefore 2^m2^{k\_1} = 2^m + k\_2$ ....................................(1)

now, $k\_1 \ge 1\implies 2^m2^{k\_1} \ge 2^m + 2^m \> 2^m + k\_2.$

(because we have $k\_1 \ge 1$ this means left side of equation $1$ will always have value $\ge 2.2^m$ but right side of equation can have maximum value of $2^m + m - 1$)

Hence this language can't be CFL.

# Answer
> 1 votes
No pushdown automaton can recognize this language, because the language is not context-free. This can be shown using the pumping lemma for context-free languages or Parikh's theorem. The latter gives a particularly straightforward proof: the language is not context-free because $2^n$ cannot be written as a finite union of linear functions.

The language *is* context-sensitive. This can be seen by noting that it is possible to write a program that counts the number of a's and b's and checks whether they are correct using linear space. Such a program can be converted into a linear bounded automaton by the standard methods of transforming programs into Turing machines. Context-sensitive grammars are so powerful that it is often easier to think of them as being arbitrary programs with a linear space restriction, rather than grammars in the usual sense.

---
Tags: turing-machines, pushdown-automata
---


title: Converting DFA to RE with Arden's Rule

text:
# Question
Title: Converting DFA to RE with Arden's Rule
So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting correct regexes at least to my knowledge, I was having some weird issues with variables/state names. Please help me understand what my mistake is here in my process:

Consider the DFA that is governed by these equations and $\Sigma = \\{a, b\\}$: $$Q\_0 = bQ\_2 \cup aQ\_1 \\ Q\_1 = bQ\_2 \cup aQ\_0 \\ Q\_2 = aQ\_2 \cup bQ\_2 \cup \varepsilon$$

I'm sorry I don't have a picture of the graph, but I think this should be fairly simple to visualize. It is an unminimized DFA that pretty much accepts every string with at least 1 'b', as it bounces back and forth from $Q\_1$ and $Q\_0$ every time an 'a' is reached, both $Q\_1$ and $Q\_0$ have edges to $Q\_2$ from 'b', and $Q\_2$ is an accept state that stays at $Q\_2$ no matter what character it sees. Now I attempt to do the reduction method we see in Raphael's post:

$Q\_1 = bQ\_2 \cup a(bQ\_2 \cup aQ\_1) \\ Q\_1 = bQ\_2 \cup abQ\_2 \cup aaQ\_1 \\ Q\_1 = (b \cup ab)Q\_2 \cup aaQ\_1 \\ Q\_1 = (aa)^\*(b \cup ab)Q\_2$

$\\ Q\_2 = a^\*bQ\_2 \cup \varepsilon \\ Q\_2 = a^\*b^\* \cup \varepsilon \\ Q\_2 = (a^\*b^\*)^\*$

$\\ \\ Q\_1 = (aa)^\*(b \cup ab)(a^\*b^\*)^\*$

Now I have two questions here:

1. Notice that at the end of my $Q\_1$ manipulation I moved $(aa)^\*$ to the front. This is something that I did out of common sense since thinking about the DFA, $(aa)^\*$ *has* to be first since $Q\_2$ doesn't have any outbound edges. Is there a way to formalize what I'm thinking/doing here?
2. Notice that at the end I have my valid regex equal to $Q\_1$. That doesn't seem right, since we want to find the regex associated with $Q\_2$! But a quick simulation through my head tells me that it actually is the regex associated with $Q\_2$. So what is going on?!

Thanks so much for your help.

# Answer
Your manipulation where you went from $Q\_1 = (b \cup ab)Q\_2 \cup aaQ\_1$ to $Q\_1 = (aa)^\*(b \cup ab)Q\_2$ was not valid. Instead, in this case I suggest that you first start by finding a nice form for $Q\_2$, before trying to manipulate $Q\_1$.

A good way to handle $Q\_2$ is to note that $Q\_2 = a Q\_2 \cup b Q\_2 \cup \epsilon$ implies $Q\_2 = (a \cup b) Q\_2 \cup \epsilon$ (by the distribute law); when then apply Arden's rule to conclude that $Q\_2 = (a \cup b)^\* \epsilon = (a \cup b)^\*$.

Now plug in this expression for $Q\_2$ into your equations for $Q\_0$ and $Q\_2$. You obtain

$$\begin{align\*} Q\_0 &= b (a \cup b)^\* \cup a Q\_1\\ Q\_1 &= b (a \cup b)^\* \cup a Q\_0 \end{align\*}$$

Next, take the expression for $Q\_1$ and plug it into the first equation. We see that

$$Q\_0 = b (a \cup b)^\* \cup a b (a \cup b)^\* \cup a a Q\_0.$$

Now applying Arden's rule tells us that

$$Q\_0 = (aa)^\* (b \cup ab) (a \cup b)^\*.$$

That's the regular expression that you ultimately wanted.
> 0 votes

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


# Question
Title: How to translate automatons (Turing machines) into programs of high level programming language?
Every program in high level ("industrial") programming language can be expressed as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian multiplication of the domains of all the variables and the resulting space can be the state space of the Turing machine, though the handling of computer-representable floats can be tricky - is there such general algorithm or system that does that? https://github.com/Meyermagic/Turing-Machine-Compiler is an example for the programming language for Turing machine and for the transpiler that translates C programs into the language of Turing machines or see https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/19/Small19.pdf for some kind of Turing assembler language). But what about the other direction - can Turing machine be rewritten in concise program in high level programming language that uses functions, compositionality of functions and higher-order functions?

Of course, there can be infinite results to that conversion - starting from the naming of the variables and functions and ending with the data structures, content of functions, etc. But there are metrics for the quality of the software code and maximizing such metrics can result in more or less unique answer to this stated problem.

Such conversion is very actual in the current context of reward machines for the reinforcement learning (e.g. https://arxiv.org/pdf/1909.05912.pdf) - symbolic representation of the reward function (as opposite to tabular or deep neural representation). Such symbolic representation greatly facilitates skill transfer among different tasks and it introduces the inference during the learning process and in such way reward machines reduce the need for data and need for learning time.

One can say that the extraction of first order and higher-order functions is a quite hard task, but this task is being tackled by the higher order meta-interpretive learning, e.g. https://www.ijcai.org/Proceedings/13/Papers/231.pdf.

So - are there research trends, works, results, frameworks, ideas, algorithms about conversion of the Turing machine into program in high level programming language (and possibly back)? I am interested into any answer - be it about the functional, logic or imperative programming.

# Answer
> 1 votes
https://www.longdom.org/articles/reverse-engineering-turing-machines-and-insights-into-the-collatz-conjecture.pdf is one initial effort to do this for some subclass of Turing machines. Actually there is fantastic culture about it http://bluesky-home.co.uk/. These works almost exclusively cite the author itself, that indicates how undeveloped this field is. Nonetheless, the quality of that research is at the level of peer-reviewed research and the main results are published.

---
Tags: turing-machines, reference-request, programming-languages, compilers, software-engineering
---


# Question
Title: Prove the Droid Trader Problem is NP-complete
This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos.

> A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are $n$ different types of droids and $k$ different planets. Each planet $p$ has the following properties: there are $s(j, p) \geq 0$ droids of type $j$ available for sale, at a fixed price of $x(j, p) \geq 0$ each, for $j = 1, 2, \dots , n$, and there is a demand for $d(j, p) \geq 0$ droids of type $j$, at a fixed price of $y(j, p) \geq 0$ each. (We will assume that a planet does not simultaneously have both a positive supply and a positive demand for a single type of droid; so for each $j$, at least one of $s(j, p)$ or $d(j, p)$ is equal to $0$.)
>
> The player begins on planet $s$ with $z$ units of money and must end at planet $t$; there is a directed acyclic graph $G$ on the set of planets, such that $s$-$t$ paths in $G$ correspond to valid routes by the player. (G is chosen to be acyclic to prevent arbitrarily long games.) For a given $s$-$t$ path $P$ in $G$, the player can engage in transactions as follows. Whenever the player arrives at a planet $p$ on the path $P$, she can buy up to $s(j, p)$ droids of type $j$ for $x(j, p)$ units of money each (provided she has sufficient money on hand) and/or sell up to $d(j, p)$ droids of type $j$ for $y(j, p)$ units of money (so I'm assuming you can make multiple buy/sells at each planet). The player’s final score is the total amount of money she has on hand when she arrives at planet $t$.

I'm trying to prove this problem is harder than some NP-complete problem, but I am quite stuck. Since the planets are organized in a DAG, I think the 'hardness' of the problem comes from the fact that you can buy and sell many different types of droids at each planet. Also, this problem is a maximation problem, and I don't know many NP-complete maximization problems other than quadratic assignment.

My thought process is that the droids have to represent something, for example choosing vertices of a graph. Then the price of the droid reflects the 'value' in some way; for example in a vertex cover reduction, the droid representing vertex $i$ would have a sale price equal to the degree of vertex $i$ for example.

Something that worked well for me for the previous 30 exercises was to consider a very simple version of the problem. So in this case, I considered cases where the planets were just a line graph, or there are only two types of droids, or each planets sells exactly 1 type of droid and buys 1 type of droid (so you can force the player to buy/sell instead of just holding on to their cash). I try to simplify in this way and see if it starts to resemble other NP-hard problems, which is why I suspect that it should be a vertex-cover or 3-sat reduction.

**Any hints would be appreciated such as what problem X should I choose to reduce to Droid Trader Problem, or how should I view this problem (e.g. 3-SAT can be viewed as choosing one out of $2^n$ choices and then checking that the choice satisfies some set of contraints)**

# Answer
You can find a simple reduction from Knapsack or from the Partition Problem (which itself reduces to Knapsack).

Let's do it from the Partition Problem:

> Given $n$ integers $S = \\{a\_1, a\_2\ldots, a\_n\\}$ with even total sum, does there exist a subset whose sum is exactly half the sum of all elements ?

So suppose you are given an instance of the Partition Problem. We construct an instance of the Droid Trader problem as follows:

* There will be $n$ types of droids, one for each integer in $S$. There will be two planets $s$ and $t$, with a directed edge from $s$ to $t$.
* On planet $s$, the player can buy a single droid of each type $i$ for a price of $a\_i$, and can sell nothing.
* On planet $t$, the player can sell droids of every type $i$ for a price of $2\cdot a\_i$, and can buy nothing.
* The player starts with $z$ equal to half the sum of all elements in $S$.

Then, it is easy to see that, the player can never end up with more money than $\sum S$. Moreover, he can achieve $\sum S$ if and only if he can buy $\frac{1}{2}\sum S$ worth of droids on the first planet, i.e. there exists a subset of $S$ with sum $\frac{1}{2}\sum S$.

So the original question on the Partition Problem instance is equivalent to asking if the player can end up with $\sum S$ money in the corresponding Droid Trader problem.

Because this is a polynomial time reduction, this proves the claim.
> 3 votes

# Answer
The problem is NP-complete even if the player can buy/sell a fraction number of a droid. We reduce Not-All-Equal 3SAT (NAE3SAT) to this problem.

Given an instance of NAE3SAT with $n$ variables $x\_1,\ldots,x\_n$ and $m$ clauses, we construct a graph like follows.

```
s ---> x_1^0 --> x_2^0 ... x_n^0 ---> t
  \          \/                   /
   \         /\                  /
    -> x_1^1 --> x_2^1 ... x_n^1

```

That is, in every step, the player chooses to go to exactly one of the planets $x\_i^0$ and $x\_i^1$.

We construct two types of droids $d\_j$ and $d\_j'$ for each clause $j$. If clause $j$ is, for example, $x\_1\vee \neg x\_3\vee x\_4$, then there is 1 droid of type $d\_j$ in planet $x\_1^0, x\_3^1$ for sale and 1 droid of type $d\_j'$ in planet $x\_1^1, x\_3^0$ for sale, and there is 1 demand for droids of type $d\_j$ in planet $x\_4^0$ and 1 demand for droids of type $d\_j'$ in planet $x\_4^1$. For each type, the price for the player to buy one droid is always 1, and the price for the player to sell one droid is always 2. The player has $M$ money initially where $M$ is a very large number.

Now we can see the fomula is a valid instance of NAE3SAT if and only if the player can hold $M+m$ money when she arrives at $t$.

By the way, this reduction shows that your problem, no matter whether the player can buy/sell a fraction number of a droid, is strongly NP-complete.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: Proof that $(L_{all})^C$ is not recursively enumerable
**The problem:**

We have the language $L\_{all} = \\{\operatorname{Kod}(M) | M \text{ is a turing machine and } L(M) = \Sigma ^\*\\}$

Hence, $L\_{all}$ is the set of all encoded Turing machines (the $\operatorname{Kod}()$ is the encoding function) which accept all words as input.

One needs to show that $(L\_{all})^C$, the complement of $L\_{all}$ is not in $\mathcal{L}\_{RE}$, that means it is not recursively enumerable.

By definition, in $(L\_{all})^C$ we have all strings which do not represent correctly encoded Turing machines as well as encoded Turing machines which reject at least one word from the alphabet.

**What have I tried so far:**

* One idea was to use the diagonalization argument that can be used to prove that $L\_{diag}$, the diagonal language is not recursively enumerable. This however doesn't seem to work.
* I tried to prove that the statement is wrong (i.e. $(L\_{all})^C)$ is recursively enumerable: The proof would more or less go like this (not very formal): Let $A$ be a Turing machine deciding if $x \in (L\_{all})^C$. We first check if $A$'s input is a correctly encoded Turing machine ($x = \operatorname{Kod}(M)$), if not we reject. If it is, we associate every word from $\Sigma^\*$ with a prime $p$ and then use this to simulate all words on $M$ at once, (in the $p^i$th step of $A$ we simulate the $i$th step of $M$ on the $p$th word). This is where my counter proof fails. Since there are uncountably infinitely many words in $\Sigma^\*$ and only countably infinitely many primes. However I do not see a way how I can use this fact to prove the original statement.

Any suggestion or hints would be greatly appreciated since I am genuinely interested how one approaches such a proof.

**Full disclosure** This was a bonus question on an old exam (not connected to homework) and I am curious how one can prove this, especially since it seems to be somewhat counter intuitive.

# Answer
Let HALT be the following version of the halting problem: Given a Turing machine $T$, determine whether it halts on the empty input.

Here is a computable reduction from HALT to $L\_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which erases its input and then transfers control to $T$. You can check that $T \in \mathrm{HALT}$ iff $T' \in L\_{all}$. This shows that $L\_{all}$ cannot be co-r.e. Indeed, if $L\_{all}$ were co-r.e. then HALT would be co-r.e. Since HALT is also known to be r.e., it would be recursive; but we know that HALT is not recursive.

Here is a computable reduction from HALT to the complement of $L\_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which on input $n$ runs $T$ on the empty input for $n$ steps; if $T$ halted, $T'$ enters an infinite loop, and otherwise $T'$ halts. You can check that $T \in \mathrm{HALT}$ iff $T' \notin L\_{all}$. This shows that $L\_{all}$ cannot be r.e. Indeed, if $L\_{all}$ were r.e. then HALT would be co-r.e., and we get a contradiction like in the preceding paragraph.

In fact, $L\_{all}$ is $\Pi\_2$-complete; it is sometimes known as TOT or TOTAL. Thus $L\_{all}$ is stronger than HALT, which is only $\Sigma\_1$-complete.
> 1 votes

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


# Question
Title: Time complexity for calculating the $LPS$ array (failure function) in KMP algorithm preprocessing
I'm studying the Knuth Morris Pratt pattern searching algorithm from here. I want to know the order of computing the $lps$ array in this algorithm - that is the array of longest proper prefixes that are also suffix. I studied the Wikipedia page for this algorithm and it says this part is of $O(m)$ \- $m$ is the length of the pattern being searched. I just don't understand why.

Can anyone help?

# Answer
> 2 votes
I've copied below the wikipedia algorithm for computing the LPS array (which is usually called the failure function because in the main KMP algorithm you refer to this table whenver there's a failed match). They denote $T\[\]$ where you use $LPS\[\]$

> algorithm kmp\_table: input: an array of characters, W (the word to be analyzed) an array of integers, T (the table to be filled) output: nothing (but during operation, it populates the table)
>
> ```
> define variables:
>     an integer, pos ← 1 (the current position we are computing in T)
>     an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring)
>
> let T[0] ← -1
>
> while pos < length(W) do
>     if W[pos] = W[cnd] then
>         let T[pos] ← T[cnd]
>     else
>         let T[pos] ← cnd
>         let cnd ← T[cnd] (to increase performance)
>         while cnd >= 0 and W[pos] <> W[cnd] do
>             let cnd ← T[cnd]
>     let pos ← pos + 1, cnd ← cnd + 1
>
> let T[pos] ← cnd (only need when all word occurrences searched)
>
> ```

The running time will be dictated by how many times "cnd" gets assigned to. The while loop inside the for loop ($pos$) might make you think the algorithm is $O(m^2)$ but as you learned it is $O(m)$.

Inspect how $cnd$ may change during one step of the for loop; it can either increase by +1, or it can decrease inside the while loop. And when it decreases, it decreases by *at least* 1, since $T\[\]$ satisfies $T\[x\]\<x$ for all $x$ ("proper" in the definition of LPS). Since $cnd$ can increase only by +1 and there are $m$ steps in the for loop, this means the overall increase is bounded by $+m$. You might visualize each change to $cnd$ as a stair of integer height, with upstairs and downstairs representing increases and decreases to $cnd$; the upstairs are all height 1, and the downstairs are each height at least 1. Because the overall height never falls below 0 (that is the termination condition for the while loop), you can bound the total number of stairs by $2m$; there are at most $m$ "up" stairs and there can't be more "down" stairs than up stairs since their height is $\geq 1$.

To put another way, this is basically a twist on the saying "what goes up most come down"; here we have "what comes down must have gone up before"

---
Tags: substrings, string-matching
---


title: Independent set problem

text:
# Question
Title: Independent set problem
I'm referring to a post on a black-box algorithm and the Independent Set problem.

**Question**

> Suppose that someone gives you a black-box algorithm $A$ that takes an undirected graph $G = (V, E)$, and a number $k$, and behaves as follows.
>
> * If $G$ is not connected, it simply returns “$G$ is not connected.”
> * If $G$ is connected and has an independent set of size at least $k$, it returns “yes.”
> * If $G$ is connected and does not have an independent set of size at least $k$, it returns “no.”
>
> Suppose that the algorithm $A$ runs in time polynomial in the size of $G$ and $k$.
>
> Show how, using calls to A, you could then solve the Independent Set Problem in polynomial time: Given an arbitrary undirected graph $G$, and a number $k$, does $G$ contain an independent set of size at least $k$?

**Solution**

> There are two basic ways to do this. Let $G = (V, E)$; we can give the answer without using $A$ if $V = \emptyset$ or $k = 1$, and so we will suppose $V \neq \emptyset$ and $k \> 1$. The first approach is to add an extra node $v^\*$ to $G$, and join it to each node in $V$; let the resulting graph be $G^\*$. We ask $A$ whether $G^\*$ has an independent set of size at least $k$, and return this answer. (Note that the answer will he yes or no, since $G^\*$ is connected.)
>
> Clearly if $G$ has an independent set of size at least $k$, so does $G^\*$. But if $G^\*$ has an independent set of size at least $k$, then since $k \> 1$, $v\*$ will not be in this set, and so it is also an independent set in $G$. Thus (since we’re in the case $k \> 1$), $G$ has an independent set of size at least $k$ if and only if $G\*$ does, and so our answer is correct. Moreover, it takes polynomial time to build $G\*$ and ask call $A$ once.

---

**My question**

I think I don't understand the solution(or the question), like I don't understand why it needs to create a new $G^\*$ to check whether $G^\*$ has Independent set of size at least $k$. I'm thinking naively if algorithm $A$ can solve this problem, can't we just input $G$ into $A$ to get a result?

I'm learning to prove a problem is NP-complete currently, these steps looks like reduction to me. So, whenever we see a problem like given algorithm $A$ able to solve a graph problem, we always need to create a new graph $G^\*$ to verify it?

# Answer
The reason you can't just take $G$ as an input to $A$ is that (strangely enough) $A$ only works on connected graphs.

You want to prove that if $A$ exists, then Independent Set is solvable in polynomial time. The reason you can prove that is by using a *polynomial time reduction*. You have proved that if $A$ exists, then $A$ can solve Independent Set on any graph by using your trick of adding a *universal vertex*.

You have also proved that Independent Set on non-connected graphs is not particularly much easier than on connected graphs.
> 1 votes

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


# Question
Title: Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour
I have implemented the basic algorithm. easily available but I am not getting the complete tour. The visited square never equals N * N;

# Answer
In general Warnsdorff's rule is just a heuristic that guides the search. It is still possible that the search hits a dead-end and we are forced to backtrack.

So let us consider the $n \times n$ chessboard now. Warnsdorff's rule (nor any other method) won't find a solution for $n \< 5$ as a solution exists precisely when $n \geq 5$. Given that $n \geq 5$, an efficient algorithm based on Warnsdorff's rule is described in \[1, Proposition 2.2\]. Other independently discovered algorithms that work in linear time are known as well (see e.g., \[2\]).

---

\[1\] Conrad, Axel, Tanja Hindrichs, Hussein Morsy, and Ingo Wegener. "Solution of the knight's Hamiltonian path problem on chessboards." Discrete Applied Mathematics 50, no. 2 (1994): 125-134.

\[2\] Parberry, Ian. "An efficient algorithm for the Knight's tour problem." Discrete Applied Mathematics 73, no. 3 (1997): 251-260.
> 2 votes

---
Tags: algorithms, time-complexity, optimization, backtracking
---


title: Does any algorithm loops at some point?

text:
# Question
Title: Does any algorithm loops at some point?
Given that any implementable algorithm has a finite number of internal states, and given that any state is determined by the previous one, does that implies that any algorithm loops at some point? If I run the algorithm until the number of state transitions is greater than the number of internal states, by the pigeonhole principle, I should eventually get into a loop. Is that correct?

# Answer
You are technically correct. A modern practical computer has finitely many states, and so any program it runs will eventually repeat a state.

However, I would like to warn against interpreting this observation in the wrong way. It is *not* a problem in practice. The number of possible states is huge (it's huuuuuuuuuuuuuuuuuuuuge). Algorithms that are designed for machines with infinite resources (such as Turing machines) typically run just fine on a modern computer. Of course, they may use up all available memory if they are especially memory-intensive, but that's different from them cycling because they somehow repeated a configuration due to computer limitations. And when programs do cycle forever unintentionally, it is not the limited size of the computer that does it, but rather programming errors.

It is *more practical* to mathematically model modern computers as if they have unlimited memory than to model them as finite-state machines. This situation is a bit like modelling in physics: classical fluid dynamics models a discrete system of atoms as if it were a continuous one.
> 3 votes

# Answer
Consider the following algorithm:

* $n \gets 0$
* repeat: $n \gets n+1$

The algorithm runs for infinitely many steps without repeating the same state.
> 0 votes

---
Tags: algorithms, turing-machines, finite-automata, loops
---


# Question
Title: Convert scientific notation decimal number to binary
I'm given the number: $$8.881784197001252 \cdot 10^{-16}$$ I know it is $2^{-50}$ but suppose I didn't know. I need to convert it to binary.

One way is to apply the school taught algorithm on the fractional part. That'd be:

$.881784197001252\cdot2=1.763568394 \to 1$

$.763568394 \cdot 2=1.527136788 \to 1$

$.527136788 \cdot 2=1.054273576 \to 1$

$.054273576 \cdot 2= 0.108547152 \to 0$

$.108547152 \cdot 2=0.217094304 \to 0$

$...$

It may go on forever so I'd need to determine when to stop.

I then thought I could write the number as: $$8881784197001252 \cdot 10^{-31}$$ Now the number is an integer and I can precisely convert it. It's: $$11111100011011110111110001000000010001011000000100100$$ The problem is that I don't know how to convert the base and its exponent from base 10 to base 2. I can approximate it after some attempts. It should be between $2^{-100}$ and $2^{-99}$.

So what I'm asking is: what is the correct approach to convert that number? And, if different from the former, what method does the computer use?

# Answer
There is more than one correct approach to convert the number. The former is a correct algorithm for the problem. This kind of base conversion would usually be implemented in a library for the programming language you are using. There might be many such implementations out there, and I don't know what all of them are doing.

I would not recommend the latter approach, as I expect computing $2^\alpha$ where $\alpha=31 \log\_2 10$ will be painful.

See also The math behind converting from any base to any base without going through base 10? and https://math.stackexchange.com/q/48968/14578 and https://en.wikipedia.org/wiki/Positional\_notation#Base\_conversion and https://en.wikipedia.org/wiki/Binary\_number#Conversion\_to\_and\_from\_other\_numeral\_systems.
> 1 votes

---
Tags: floating-point, binary
---


# Question
Title: How does a dual core microprocessors run so many programs?
I have a laptop with Intel dual core and it runs, the OS windows, and many application from Opera, age of empires, word, excel etc open at once just fine. If it only has 2 cores, how can so many programs work? How exactly does it manage to do all these? Does operating system have something to with it?

# Answer
> 4 votes
It's great that you're curious. A simplified explanation follows with a few links to delve into:

All of the programs running in parallel is actually an illusion that is created by the OS.

1. Even if we have a uniprocessor system, the OS can still achieve the same thing.
2. For multiple programs running on the system, OS creates separate processes.
3. Separate processes could then time-share the processor(s) available.

Since a processor is very fast (gauged by frequency), it can switch back and forth among multiple processes that may be active in a particular time period (we're talking about the span of time in microseconds/milliseconds). Overall, this gives the user an illusion that the programs are running in parallel. This technique is called Multi-tasking.

Now, adding more processors(let's say one in your case) allows the OS to also use the processors in parallel. In this case, let's say the OS chooses to run half of the programs on one processor and the other half on another processor (in reality, it's a little more complex). Individual processors are still used by the running processes in a time-sharing fashion but since there are two processors, overall the performance of your running programs improve. Using multiple processors in parallel is called Multi-processing.

Although the definitions can be a little confusing, this overall implementation idea remains the same.

---
Tags: dynamic-programming, memory-hardware, process-scheduling, threads, multi-tasking
---


# Question
Title: Complexity of scalar operations for integers
I am currently studying the complexity of matrix multiplication and Wikipedia's article says "The matrix multiplication algorithm that results of the definition requires, in the worst case, n³ multiplications of scalars and (n−1)n² additions for computing the product of two square n×n matrices. Its computational complexity is therefore O(n³), in a model of computation for which the scalar operations require a constant time (in practice, this is the case for floating point numbers, but not for integers)."

I'd like to know why integers' scalar operations does not require constant time.

# Answer
The quote from Wikipedia doesn't say that scalar operations on integers don't take constant time; on the contrary, it says that the analysis of the matrix multiplication is based on the assumption that those scalar operations *do* take constant time. This assumption is stated not because it's false, but because it is true only in some contexts.

If you use a fixed-width integer type, such as 32-bit or 64-bit integers, then arithmetic operations such as `+` or `*` take asymptotically constant time simply because there are only finitely many different inputs, so whichever inputs they are slowest for is a constant bound on their running time.

On the other hand, if you use a language like Python where integers are not bounded by a fixed number of bits, then arithmetic operations are not constant time, and generally cannot be done in constant time on real hardware.

The algorithm we use to add numbers on paper requires adding the rightmost digits, maybe carrying a 1 to the next column left, adding the digits in that column and carrying, and so on in a loop. This algorithm is O(log *n* \+ log *m*) because the number of digits you need to add is logarithmic. The algorithm for adding integers in Python has a lot of special details regarding the data structure used to represent those integers, but the way it works is essentially the same; a loop over the digits of the number from right to left, in O(log *n* \+ log *m*) time.
> 2 votes

---
Tags: time-complexity, complexity-theory
---


title: Voronoi Cell and Voronoi Diagram

text:
# Question
Title: Voronoi Cell and Voronoi Diagram
Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x and V(y) be the Voronoi cell of y. Prove or disprove that V(x) and V(y) share an edge in Vor(P ).

Here,as per my understanding, the shortest edge xy means that no other edge with one red endpoint and one blue endpoint is shorter. However, there may be edges with both red endpoints or both blue endpoints that are much shorter.

# Answer
> 4 votes
Let us assume that $P$ is in general position (no three points colinear, no four points cocircular) to make things easier.

As the Voronoi diagram is the dual of the Delaunay triangulation, this is the same as asking if the edge $xy$ is in the Delaunay triangulation of $P$.

You might know the following characterisation:

> An edge $(a,b)$ is in the Delaunay triangulation of $P$ if and only if there is a disk whose boundary passes through $a$ et $b$ containing no other point of $P$ on its boundary or in its interior.

So let us take a look at the edge $(x,y)$ and let us draw the circle/disk whose diagonal is $(x,y)$.

Notice that if any point other than $x$ or $y$ is in the disk, then it is closer to both $x$ and $y$ then they are to each-other. Thus there is no such point in $P$, as it can't be red nor blue by definition of $(x,y)$. So this disk contains no other point of $P$, which means $(x,y)$ is an edge of the Delaunay triangulation, thus it is an edge of the Voronoi Diagram.

(There was no real need to make a detour through Delaunay triangulations as by duality the characterisation works just as well for Voronoi diagrams but I have always seen that characterisation stated in terms of Delaunay triangulations)

---
Tags: algorithms, computational-geometry, discrete-mathematics, voronoi-diagrams
---


title: Near Triangulation Planar Graph

text:
# Question
Title: Near Triangulation Planar Graph
This is the problem I am dealing with:

Given a set P of n points in general position, let a graph G be defined as follows:

The vertex set is P. Two vertices, a and b, are joined by an edge provided there exists an axis parallel square S with a and b on the boundary and no other point of P in the interior of S.

I need to prove or disprove that G is a near-triangulation where every face except the outerface is a triangle and the outerface is a cycle.

Thanks in advance

# Answer
> 2 votes
An easy contradicting example is three points forming an obtuse triangle. Note that any Axis-parallel square containing $A$ and $B$ on its boundaries, contains $C$ in its interior and hence, the outer face is not bounded by a cycle since $AB$ is not an edge in the graph.

---
Tags: algorithms, graphs, computational-geometry, discrete-mathematics, planar-graphs
---


# Question
Title: Smoothed analysis of the Partition problem
I am studying smoothed analysis and trying to apply it to the Partition decision problem: given $n$ real numbers with a sum of $2 S$, decide whether there exists a subset with a sum of exactly $S$.

The common definition of the smoothed runtime complexity of an algorithm is: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it is perturbed by a perturbation of size $\sigma$, e.g. by adding to each input a number selected randomly from a normal distribution with standard deviation $\sigma$, or from any distribution with support $\[0,\sigma\]$.

If I apply this definition to the Partition problem, it seems that for *any* $\sigma \> 0$, the runtime complexity is $O(1)$, since for any random noise that is added to the original numbers - no matter how small - the answer is "no" with probability 1.

This is strange, since in the more common examples of smoothed analysis, the runtime complexity depends on $\sigma$, and here it does not.

Is there something I misunderstood? What is the smoothed runtime complexity of Partition?

# Answer
> 1 votes
Smoothed analysis, as I have seen it, has typically been used for analyzing optimization problems, not decision problems. The partition problem is a decision problem, which introduces the challenge you mentioned. Perhaps one could consider the optimization variant of the partition problem: given $n$ numbers with a sum of $2S$, find the subset whose sum is as close to $S$ as possible. I don't know whether the smoothed complexity of that optimization problem would be interesting or illuminating, but it eliminates the problems you articulate in the question.

---
Tags: runtime-analysis, partitions
---


# Question
Title: How to get enclosed spaces from a series of connected nodes
I have a bunch of connected walls in a list and the data for them is like so:

```
Wall
{
   Node A;
   Node B;
}

Node
{
   float x;
   float y;
}

```

I want to find the rooms from the connected walls as an array of connected points to represent each room's perimeter.

This is an example visually of what i am trying to find:

The red dots are the nodes, and the lines are the walls, the numbers are the identified rooms that the walls created.

The walls can be at any angle, not sure if that matters though.

I am wondering what algorithms exist that can help me solve this problem, what is the best way to approach this?

# Answer
One approach is to use a data structure for representing a planar graph. Each node corresponds to a vertex in the graph, and each walls corresponds to an edge in the graph. Then, you are looking for the set of faces in this graph. Standard data structures for representing planar graphs should make it easy to retrieve the set of faces.

For instance, one standard data structure is the DCEL data structure. It explicitly contains one record for each face, so once you have converted this to a DCEL data structure, then it is straightforward to iterate over all faces. There are standard algorithms for constructing a DCEL data structure from the set of vertices and edges. Or, instead of a DCEL, it looks like you could alternatively use a quad-edge data structure or a winged-edge data structure. The keyword is to look for data structures for polygon meshes. This has been studied in great detail in the computer graphics and computational geometry fields.

Alternatively, you could solve your problem directly. For each node, find all of the walls associated with it, sort them by their angle, and store that sorted list associated the node. After doing that for all nodes, then you can iterate through all rooms. Pick an wall, then you can find the room to the "right" of that wall by simulating the left-hand rule: stand to the right of that wall, put your left hand on the wall, and walk forward, going in a circle around the perimeter of the room. To simulate that rule, as you walk forward, you'll walk to the endpoint of the current wall; at that node $d$, to find the next wall you proceed to, look in the sorted list of walls incident on $d$, and find the next one in sorted order, then follow that wall. It might be a bit trickier to work out the details of this, than to use an existing implementation of a DCEL data structure.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)
The solution to this problem can be found here. It says:

> To multiply $k$ matrices, we generate the result entry by entry, by running a counter $t$ and generating the $it$th entry in the product of the first $k − 1$ and the $tj$th entry in the last matrix. Inductively, we need to maintain $k$ counters which can be done in $O(k \log n)$ space. Finally, note that using repeated squaring, we can compute $A^p$ using $O(\log p)$ matrices, which are different powers of $A$. To generate each of these matrices, we just need $A$ and a single counter. Hence the total space needed is $O(\log p \log n)$.

What I don't understand is that in the case of multiplying $k$ fixed matrices, they're part of the input tape so no space is needed for them in the work tapes. In the case of the $A^p$ computation, the intermediate results $A^{2^t}$ must be stored somewhere demanding more space. So how can this be done in $O(\log p \log n)$ space?

Thanks!

# Answer
> 1 votes
No. The intermediate matrices $A^{2^t}$ don't need to be stored anywhere. When you need a value, you just recompute it. This might sound very inefficient -- but remember, we're only counting the space complexity here, not the time complexity, so it's fine to take a very long time to recompute the same value many times, if that saves you some space.

---
Tags: complexity-theory, space-complexity
---


title: Efficiently extendable hash function?

text:
# Question
Title: Efficiently extendable hash function?
I'm wondering whether there exist any good hash functions with the following property: Assume that $x$ is some string over some alphabet $A$, then given $H(x)$ we can compute in $O(1)$ time both $H(ax)$ and $H(xa)$ for any letter $a\in A$. In practice one can assume that $A$ is for example the set of $8$-bit integers.

In other words, a hash function for strings that can quickly be extended in both directions. I'm only interested in hash functions that actually distribute the data well and which are very fast to compute in practice.

# Answer
> 2 votes
Use any rolling hash, e.g., the Rabin-karp rolling hash, Buzhash, or CRC. See also the following resources:

---
Tags: strings, hash
---


title: Why in the code i ≃ n?

text:
# Question
Title: Why in the code i ≃ n?
```
i=2;
while(i<n)
{
   write('*');
   i=i*i;
}

```

Why $n ≃ i$?

I mean suppose $n=1000$ and so $i= 2,4,16,32,256,65536$ is in every steps.

In the book wrote $2^2 power(k)$ is pattern for growing $i$ so $n ≃ i$ and...

Now 65536 or 256 isn't equal to 1000 or around 1000.

But why $n ≃ i$?

This chapter is about notations.

# Answer
The symbol $\space ≃ \space$ means "*asymptotically equal to*".

So when you read $ n ≃ i$, you can read it as $n$ *asymptotically* approaches $i$.

This means that the more $n$ increase in size, the more $i$ increase in size but $n$ never become equal to $i$.

> I mean suppose $n=1000$ and so $i=2,4,16,32,256,65536$ is in every steps.

This contains an error: when the program start $i=2$. At the first cicle, $i=2^2 = 4 $. $\space$ At the second cicle, $i=4^2=16$. $\space$ At the third cicle, $i = 16^2= 256$. $\space$ At the fourth cycle, $i=256^2 = 65536$. $\space$ At the fifth cycle the program stops since $i\>n$.
> 1 votes

---
Tags: algorithms, notation
---


# Question
Title: How to divide an unsorted list in linear time where every element in the first part is smaller than every element in the second list
How to divide an unsorted list into two equal parts in linear time, where every element in the first part is smaller than every element in the second part

I tried to use QuickSort but in can result in $O(n^2)$ worst-case time complexity.

# Answer
> 2 votes
Use the median of medians with quickselect allows you to find the $k$th element in linear time. Set $k = n/2$ to find the exact median and use it to partition your array in one more linear time step.

---
Tags: algorithms, algorithm-analysis, data-structures, time-complexity
---


# Question
Title: Voronoi Diagram Drawing Variations and Charateristics
I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays.

Similarly how can we draw the Voronoi diagram for the following: (a) A set of lines and points? (b) A set of disjoint line segments? (c) A set of line segments forming a convex polygon? (d) A set of circles (non intersecting and no circle contains another)?

For each of these sets of objects, how can we describe the shape of the boundary pieces that form the Voronoi diagram.

I believe that the distance between a point and another object is the smallest distance between the point and any point of the object.

# Answer
> 3 votes
The Voronoi diagram of disjoint segments (b) has been thoroughly studied.

---

<sup> Image from GIS. </sup>

---

See:
> CGAL Manual, Chapter 43: 2D Segment Voronoi Diagrams. CGAL link.

---

For the Voronoi diagram of circles (d), see:

> Jin, Li, Donguk Kim, Lisen Mu, Deok-Soo Kim, and Shi-Min Hu. "A sweepline algorithm for Euclidean Voronoi diagram of circles." *Computer-Aided Design* 38, no. 3 (2006): 260-272. Journal link.
>
> Huber, Stefan. Computation of Voronoi diagrams of circular arcs and straight lines. Magisterarbeit, 2008.

To quote the latter: "**Lemma 1.4**. The bisector between two circles (...) consists of ellipses and hyperbolas." PDF download.

# Answer
> 3 votes
The edges of a Voronoi diagram are the curves at equal distance from two geometric entities.

* for two points, the mediatrix,
* for two lines, the bissectrix,
* for a line and a point, a parabola,
* for two circles, a general conic.

The vertices are the intersections of two equidistant curves.

The diagram can also be seen as the set of crest lines of the distance map to the entities.

---
Tags: algorithms, computational-geometry, discrete-mathematics, voronoi-diagrams
---


# Question
Title: Is it possible to estimate the step size and walking velocity of different person with the x-y-z acceleration data from 6 axial accelerometer sensor?
I have a 6-axial sensing device used to record the acceleration data. There is an algorithm used to count the number of step and walking distance of the user, but I want to further increase the accuracy of the result. I want to write an algorithm which can calculate the step size and the walking velocity of the person. Is it possible ?

# Answer
The answer—as with many such applied numerical problems—is, "sure, but you have to decide which of the published heuristics you want to use". Your real problem will be the embarrassment of riches as you try to choose a paper to implement or find an existing library implementation.

Using a quick Google search on `estimating step size from accelerometer`, I was able to find multiple articles proposing different methods for doing this. Apparently the research area is called *Pedestrian Dead Reckoning (PDR)*, which makes sense since dead reckoning is the general term for estimating positioning using only velocity and acceleration data.

Some articles that attempt to estimate stride length as part of a PDR algorithm include:
> 2 votes

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


# Question
Title: NP-completeness for integer linear program
This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come up with a solution.

We have $i\ldots j$ stores and $i\ldots n$ possible places to build a new warehouse. Costs to build a new warehouse are $c\_j$. Between each store and warehouse is a path of cost $d\_{i,j}$. Every store needs to be connected to at least one warehouse.

The decision problem is: is there a set of warehouses and paths so that the sum is smaller than a given number $k$.

# Answer
This is a classic facility location problem. That Wikipedia article suggests that NP-hardness can be proven by reduction from set cover.

---

Since the asker has now stated to have found a solution by reducing from *vertex cover*, I will go ahead and reveal the reduction from *set cover*:

> For each value, create a store; for each set, create a warehouse. Assign the cost of each warehouse to be 1. Assign the cost of the route from a warehouse to a store to be an arbitrarily small value if that warehouse's set contains that store's value, or an arbitrarily large value otherwise. Then the minimum cost solution to the facility problem builds precisely the set of warehouses corresponding to the minimum set cover in the original problem.
> The $k$ value is used to turn the optimization problem (minimize sets/cost) into a decision problem (is there a solution with no more than $k$ sets/cost?). The $k$ from the set cover instance will be the same as the $k$ in the facility problem instance if you are allowed to set the "arbitrarily small" values to exactly 0 - otherwise you might have to fudge the value by some amount, but less than 1 as long as you pick the "arbitrarily small" weights to be small enough. You just need the total of every "arbitrarily small" cost to be less than 1, and every "arbitrarily large" cost to be greater than the sum of the costs of all the warehouses and all the "arbitrarily small" routes.
> Note that, if only integer costs are allowed in the facilities problem, you can still achieve the same result by scaling all the costs by their least common multiple.
> 0 votes

---
Tags: np-complete, reductions, decision-problem
---


# Question
Title: Prove vertices of polygon are endpoints of disjoint line segments
If we are given a set of disjoint line segments in the plane, can we prove (or disprove) that we can always join the line segments to make a simple polygon where the vertices of the polygon are the endpoints of the segments and every segment is an edge on the boundary of the polygon.

# Answer
Here is a simple counter example :

You most join the two leftmost vertices to the two middle vertices, and both ways to do that don't work.
> 4 votes

---
Tags: algorithms, computational-geometry, discrete-mathematics
---


title: Dijkstra with max instead of sum

text:
# Question
Title: Dijkstra with max instead of sum
Is it true that if we replace in the Dijkstra algorithm `+` with `max`, then the resulting algorithm correctly solves the problem of finding the shortest paths where the length of the path is measured as the maximum of its edge weights?

# Answer
> 7 votes
Yes, it is true.

Let $w: E(G) \to \mathbb{R}$ be a weight function on the edges of $G$, $s \in V(G)$ be the start vertex. Let $p(v) = \min\\{\max\\{w(e\_1), \ldots, w(e\_k)\\} \mid e\_1, \ldots, e\_k \text{ is edges of a path from } s \text{ to } v \\}$ i.e. the shortest path between $s$ and $v$.

Let's prove by induction on the step of Dijkstra's algorithm that it does indeed find the shortest paths. Let $S \subseteq V(G)$ be the set of vertices that have been already processed by the algorithm. Then Dijkstra's algorithm finds $p'(v) = \min\\{\max\\{p(u),w(uv)\\} \mid u \in S\\}$ for every $v \in V(G) \setminus S$. Then it is sufficient to prove that there exists $v\_0$ such that $p(v\_0) = \min p'(v)$ the equality $p(v\_0) = p'(v\_0)$ holds. Let $e\_1, \ldots, e\_k$ be the edges of the shortest path from $s$ to $v\_0$. $e\_k = u v\_0$ then $p(u) \le p(v\_0)$. If $u \in S$ the statement is proved. Otherwise pick $v\_0 := u$ instead (this reduction is finite since we can choose a vertex closer to $s$ in terms of the smallest number of edges in a path between them).

So essentially nothing changes comparing to the algorithm and the proof.

But there is another solution that uses Disjoint Set Union (DSU) data structure. Initialize DSU with sets $\\{v\_1\\}, \\{v\_2\\}, \ldots, \\{v\_n\\}$. Then add edges in the increasing order of $w$ and when an edge $uv$ is added unite the sets containing $u$ and $v$ in the DSU. If at some step an edge with a weight $x$ has been added last then all the vertices in the set containing $s$ have distance to it at most $x$. So if you unite sets $A \ni s$ and $B$ put $p(v) = x$ for $v \in B$.

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


title: Joining line segments to make tree

text:
# Question
Title: Joining line segments to make tree
Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and every segment is an edge in the tree.

# Answer
Disclaimer: the proof is quite technical. OTOH, I don't see a comfortable way to do this, because the initial set of segments can be as crazy as possible, even if none of them intersects.

Let's prove that we can make a tree not only from the set of disjoint segments, but also from the set of disjoint trees. So, the initial statement will be just a special case of it when all trees are segments.

The new statement will be proved by downward induction on the number of trees. When we have only one tree, we are done. To make an induction step, it's enough to connect two trees without intersecting or touching other trees.

Define *distance* between different trees $S$ and $T$ as $d(S, T) = min\_{s\in P(S), t\in P(T)}d(s, t)$, where $P(X)$ is a set of all points belonging to tree $X$ (not necessarily vertices), $d(s, t)$ is a usual Euclidean distance.

Then take $(S, T) = argmin\_{R, W \hbox{ are trees}, R \ne W} d(R, W)$. Let $d\_0 = d(S,T)$. Also define $s$ and $t$ as the points which deliver us the minimum distance.

WLOG $s$ is a vertex. This statement requires some geometrical analysis. The most complicated case is when $s$ and $t$ lie strictly inside some segments. But if so, these segments must be parallel to each other, otherwise we can draw a height from some point to the opposite segment and get a distance smaller than $d\_0$. And if they are parallel, the segment $st$ is perpendicular to them both, and we can simply move it to the one of the ends of the segments, so one of points actually becomes a vertex.

First, prove that the segment $st$ doesn't intersect or touch other existing segments. We do it by contradiction. If such segment exists, set the intersection point to $u$. It lies strictly inside $st$, because the tree set is disjoint and not self-intersecting. There is a tree $U$ such that $u\in U$. But either $U \ne T$ or $U \ne S$, thus $d(U, T)$ or $d(U, S)$ is well-defined and is smaller than $d(s, t) = d\_0$. Contradiction.

Second, if $t$ is already a vertex, we are done, because we can draw a new segment connecting vertices $s$ and $t$. Otherwise define the segment which $t$ belongs to as $K$.

Third, let's continuously move $t$ on $K$ to one of the ends of $K$. If we reach the end without $st$ touching any other points, we are done. If not, assume that we got a segment $st'$ for $t'\in T$, and also $st'$ contains some other vertex $v \in V$. If there are more than one such vertex, take closest to $s$.

Let's look what happens if $V \ne T$. Geometry says that $st$ is perpendicular to $K$. So, if we draw a height from $v$ to $K$, we get a segment shorter than $st$, and it will deliver a distance from $V$ to $T$ smaller than $d\_0$.

And if $V = T$, we can just forget about $t$ and connect $S$ and $T$ using segment $sv$.
> 1 votes

# Answer
I'd like to propose a variation on Aleksandr Logunov's proof, that I find to be a bit simpler (arguable).

Let's prove that we can make a tree from a collection of disjoint trees.

So suppose we have a collection of at least two disjoint trees in the plane (if there were only one we would be done).

Without loss of generality, suppose that no two vertices have the same $x$ coordinate (otherwise, just rotate the plane ever so slightly to make this hold).

Choose a vertex $u$ which is the rightmost vertex of some tree but not the overall rightmost vertex (such a vertex necessarily exists if we have at least two trees and no two vertices have the same $x$ coordinate).

Choose a vertex $v$ to the right of $u$. Draw the segment $(u,v\]$ and let $S$ be the first segment $(u,v\]$ intersects, and $p$ the point of this intersection.

If $p = v$, then we can safely draw the segment $\[u,v\]$ and decrease the number of connected components in our forest (remember that $v$ is not in the same tree as $u$ because $u$ is the rightmost vertex of its tree).

If $p \neq v$, then let $w$ be a vertex of $S$ to the right of $u$ ($S$ has at least one such vertex). Just like in Aleksandr's proof, we can now move $p$ on $S$ towards $w$ until the segment $(u,p\]$ intersects a vertex. We can then safely draw the segment joining $u$ to that vertex and decrease the number of connected components by one.

So we can always decrease the number of connected components by one (if we have at least two to start with) and thus the result follows by induction.
> 1 votes

---
Tags: algorithms, graphs, computational-geometry, trees, discrete-mathematics
---


# Question
Title: Complexity of minimizing the maximum inter-cluster distance?
Given $n$ non overlapping points $x\_i \in \mathbb{Q}$, and an integer $k\geq 2$, **what is known about the complexity** of finding $k$ means ($a\_1, a\_2, ..., a\_k$) that minimize the maximum inter cluster distance: $$\min\_{a\_1, ..., a\_k \in \mathbb{Q}}\max\_{1\leq j \leq k} \sum\_{x\_i \in C\_j}||x\_i-a\_j||^2$$

Do we have any polynomial time algorithms for general $k$?, specific $k$ (say $k=2$)? Does the problem have a special name?

# Answer
Because you are working in one dimension, there's a polynomial-time algorithm, using dynamic programming. Assume $x\_1,\dots,x\_n$ are sorted in increasing order. Notice that each cluster must contain a contiguous sequence of $x$'s, say $x\_i,x\_{i+1},\dots,x\_j$. Let $f(n\_0,k\_0)$ denote the minimum of the maximum inter cluster distance for dividing the points $x\_1,\dots,x\_{n\_0}$ into $k\_0$ clusters. Then you can express $f(n\_0,k\_0)$ in terms of $f(m,k\_0-1)$ for $m\<n\_0$:

$$f(n\_0,k\_0) = \min\_m \max(f(m,k\_0-1), \text{variance}(x\_{m+1},x\_{m+2},\dots,x\_{n\_0})),$$

where $m$ ranges over $m=1,2,\dots,n\_0-1$.

Consequently, you can evaluate $f(\cdot,\cdot)$ at all $O(nk)$ inputs in $O(n^2k)$ time. You can improve this to $O(nk)$ time by setting $g(n\_0,k\_0)=\min(f(1,k\_0),\dots,f(n\_0,k\_0))$ and noting

$$\begin{align\*} f(n\_0,k\_0) &= \max(g(m,k\_0-1), \text{variance}(x\_{m+1},x\_{m+2},\dots,x\_{n\_0}))\\ g(n\_0,k\_0) &= \min(g(n\_0,k\_0-1), f(n\_0,k\_0)). \end{align\*}$$

You will need to use the fact that you can compute the mean and variance of $x\_{m+1},\dots,x\_{n\_0}$ from the mean and variance of $x\_1,\dots,x\_m$ and the mean and variance of $x\_1,\dots,x\_{n\_0}$. You can compute the mean and variance of $x\_1,\dots,x\_{n\_0}$ for all $n\_0$ in $O(n)$ time by maintaining a running sum and running sum of squares.
> 2 votes

# Answer
Based on Wikipedia documentation (here), finding the optimal solution to the k-means clustering problem for observations in d dimensions is:

* **NP-hard** in general Euclidean space (of d dimensions) even for two clusters
* **NP-hard** for a general number of clusters k even in the plane
* if $k$ and $d$ (the dimension) are fixed, the problem can be exactly solved in time $O(n^{dk+1})$, where $n$ is the number of entities to be clustered

Thus, a variety of heuristic algorithms such as **Lloyd's** algorithm given above are generally used. The running time of Lloyd's algorithm (and most variants) is $O(nkdi)$ where:

* $n$ is the number of $d$-dimensional vectors (to be clustered)
* $k$ is the number of clusters
* $i$ is the number of iterations needed until convergence.

On data that does have a clustering structure, the number of iterations until convergence is often small, and results only improve slightly after the first dozen iterations. Lloyd's algorithm is therefore often considered to be of "linear" complexity in practice, although it is in the worst case superpolynomial when performed until convergence.
> 0 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Convert ambiguous grammar to unambiguous and SLR(1)
I have the following ambiguous operator grammar:

```
E->E+E*E | E-E*E
E->E+E | E-E | E+E | E*E | E/E
E->(E) | x

```

I must convert it to an **unambiguous** one which is also **SLR(1)**. The following rules regarding precedence and associativity must hold:

* Operators * and / have the **highest** precedence (and precedence between them must be equal)
* Operators - and + have the **same** precedence (lower than * and /)
* All operators are **left** associative.
* Reducing with the first 2 rules is preferred if it does not break the precedence and associativity rules.

My problem is the first line of the grammar `(E+E*E , E-E*E)`. I can't find i way to convert it and the new grammar will be SLR(1).

Edit: The closest i came is this grammar, but it has 2 SLR conflicts:

```
E->E+F | E-F | T
T->T+F | T-F | F
F-> F*C | F/C | C
C-> (E) | x

```

# Answer
> 2 votes
Let's start where you probably started, with the classic expression grammar:

$$\begin{align}E&\to T\mid E + T\mid E - T\\ T&\to F\mid T * F\mid T / F\\ F&\to ( E )\mid x\\ \end{align}$$

and then we add the "fused" productions:

$$\begin{align}E&\to E + T * F\mid E - T * F\\ \end{align}$$

That grammar has a conflict because of the ambiguity:

$$\begin{align}E&\to E+T\*F\\E&\to E+T \to E+T\*F\end{align}$$ (and similarly for the $-$ operator).

So how to get rid of the ambiguity? Clearly, we don't want $E\to E+T$ to match $E+T\*F$. So we need to define $$T' = T \setminus T * F$$ in order to be able to restrict the $E$ production to $E\to E + T'$.

Since the set difference operator is not valid in a CFG, we need to write the definition out the long way:

$$\begin{align}E\to&\\;T\mid E + T'\mid E - T'\\;\mid\\ &\\;E + T * F\mid E - T * F\\ T'\to&\\;F\mid T / F\\ T\to&\\;T'\mid T * F\\ F\to&\\;( E )\mid x\\ \end{align}$$

---
Tags: formal-grammars, parsers, ambiguity
---