# Question
Title: Adder circuit with sign bit (not twos complement)
I've found and implemented a full adder to be able to do unsigned or two's complement addition on wikipedia: https://en.wikipedia.org/wiki/Adder\_(electronics)#Full\_adder

However, in my particular case, I'd like to use a sign bit instead of twos complement, due to there being a variable (unbounded) number of bits involved.

How can i do addition and subtraction with binary numbers using a sign bit? (say, it's a separate bit, not one of the binary digits per se).

I also only have access to AND and XOR.

Edit: Potatoswatter suggested that twos complement is still able to be done with an unbounded number of bits. What do you do when you want to add 6 bits and 8 bits together? Also, is multiply, divide and modulo easily done in twos complement? Keep in mind i have only AND and XOR, so don't have the ability to do if statements, the logic needs to be "branchless".

Thanks!!

# Answer
This is called "sign-magnitide" or "signed-magnitude" representation. A Google search for "sign-magnitude adder" gives lots of useful results. I know this doesn't answer your question directly (I don't have enough reputation to simply comment your post), but you will find the answer there.

As for only having AND and XOR, this is the classic result that any logic gate can be constructed from AND and NOT. Note that XOR(1,a) = NOT(a). Now you have NAND and NXOR. NOR(a,b) = AND(NOT(a),NOT(b)). Now you have OR by negating NOR. All other gates can be constructed by negating inputs of these gates.
> 3 votes

---
Tags: arithmetic, digital-circuits
---


# Question
Title: Is sierpenski's triangle considered to be a computational model?
I was reading about **sierpenski's triangle** and i found that it is similar to **pascal's Triangle**, which can show coefficients in binomial expansion, also rule 90 from ECA.

If Sierpenski's triangle can show coefficients in binomial expansion, and was simulated by other two systems {Pascal's Triangle} and {Rule 90} does that means it is a computationa model ?

What about rule 110, which is proved to be universal, is it a computational model also?

# Answer
I would not call Sierpenski's triangle a computational model. A computational model should be a system that has a way to compute something. This means there needs to be a way to supply an input, and a way that the system does something with that input to compute something. Sierpenski's triangle is a single thing (a single set), and it is fixed -- there is no way to supply different inputs and get a different output.

For similar reasons, I would not call Pascal's triangle a computational model.

However, I *would* call rule 90 a computational model. There are standard ways of providing an input and computing stuff (e.g., the input bitstring is interpreted as a row, and then successive rows are derived using the cellular automaton rules, which is interpreted as a computation). Similarly, I would call rule 110 a computational model. Or, more generally, I might call cellular automata a computational model, and rule 90 and rule 110 as two instances of cellular automata.
> 5 votes

# Answer
DW's answer does not point this out specifically (maybe hes aware of this) but to expand on it somewhat, CA rule 90 can produce a Sierpinski triangle with a simple single black dot input. see here. the same rule 90 leads to other complex patterns.

so reviewing the wikipedia definition of computational model (not to be confused with models of computation!):

> A computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation.\[citation needed\] The system under study is often a complex nonlinear system for which simple, intuitive analytical solutions are not readily available. Rather than deriving a mathematical analytical solution to the problem, experimentation with the model is done by adjusting the parameters of the system in the computer, and studying the differences in the outcome of the experiments. Operation theories of the model can be derived/deduced from these computational experiments.

cellular automata clearly classically fit these criteria although they are not mentioned specifically on the wikipedia page. and the Sierpinski triangle may be created from some of the simple CA rules and inputs. the Sierpinski triangle is an example of emergent behavior of a computational model where that particular output is one "outcome of experiments of experimentation with the model by adjusting parameters of the system". note as a somewhat related angle that Sierpinski triangles have been found naturally in seashells and other basic processes eg:

so in short a Sierpinski triangle may be one of the basic signs of the presence of some kind of "computational model".
> 1 votes

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


# Question
Title: How to check the ability to satisfy demand?
We have Stocks in several discrete positions, let say:

```
A    B   C
40   20  80

```

And Demand, which may be satisfied by one or more Stock positions (if no specified then it would accept any Stock).

Demand for A=20 may be satisfied from A Stock only, and depletes 20 units from it. Demand for AB=20 may be satisfied from any of the A abd B Stocks, and may take partially from both, without any proportion limitations.

So for the Stocks example above:

This Demand may be satisfied (10 strict from A, 20 strict from B, and 30 AB would take from both)

```
AB  B   A
30  10  20

```

And this may not (insufficient B Stocks)

```
AB  B   B
30  10  20

```

This sounds like a more or less common problem which should have a known solution. I would be happy with any reference or idea. Also if the solution is resource heavy a cheaper approximation would be great.

# Answer
You can formulate this as a maximum flow problem, which you can solve using standard techniques.

Turn every stock in to a source node with capacity equal to the amount of stock. Any demand gets turned in to a sink with demand equal to its demand. Add edges between stocks and demands if the stock can fulfill the demand.

If you don't want to have more than one sink or source that is possible too: you create the stock and demand nodes as before, and create an edge between the sink and all stock nodes (with capacity equal to the amount of stock available), similarly create an edge between all demand nodes and the sink (with capacity equal to the demand).
> 3 votes

---
Tags: algorithms, approximation
---


title: Is this a new compression approach?

text:
# Question
Title: Is this a new compression approach?
I've come up with an idea on how to compress data. But I'm not sure if the approach already exists. I would like to know if it does already, and if so, what its name is.

The approach is to:

1. Convert the message to a number
2. Find the smallest equation to represent the number

The result of this is an equation. Which will be much shorter in length than the original message, or its corresponding numerical value.

The process can be reversed by evaluating the equation, and then converting the number back into the message.

Step 1. is similar to base conversion but has the following numerical sequence...

Given an alphabet of "abc"...

```
Message, Value
a,       0
b,       1
c,       2
aa,      3
ab,      4
ab,      5
ba,      6
...

```

Value "aa" shows the difference between base conversation. In normal base conversion the value of "aa" would be 0 because "a" is the first letter of the alphabet and has a value of 0, so two of them would also be zero.

The value is really the permutation sequence number for when the alphabet is iterated over (or "bruteforced"). (Aside: Useful when distributing "bruteforce" problems.)

For step 2. I plan on using state space search to generate the equation. The goal state will be the smallest equation. The search will be performed by applying and accepting a single math operation on the "remaining" value. Initially, the "remaining" value will the original number. By the end of the search it will be reduced to zero.

Non-answer feedback is welcome as comments on the question.

# Answer
"The result of this is an equation. Which will be much shorter in length than the original message, or its corresponding numerical value." If that were true, your scheme would be able to compress every input by at least one bit. This is provably impossible by a simple counting argument (there are $2^n$ $n$-bit strings but only $2^n-1$ strings of length less than $n$), so your claim cannot be true.
> 4 votes

---
Tags: reference-request, data-compression
---


# Question
Title: Find pairs in an array that when multiplied to each other gives you sum x
So this is the pseudo code I came up with but the run time is very slow. Is there a way to write this code to get it in terms of O(n)?

First for loop (starts at 0) grabs the first value of the array and the second for loop is nested inside the first for loop (starts at j =i+1). The second for loop runs through and checks if the second value times the first value is equivalent to x, if not, then there are no pairs.

How would I write this to get the run time down to O(n)?

# Answer
> 1 votes
You can use a hash map to index already visited elements:

```
for ai in A
    if hash[x/ai] // product = x
    hash[ai] = true
end

```

Which is $\mathcal{O}(n)$ in time.

# Answer
> 0 votes
I'm not sure that $O(n)$ is possible. A good trick is to sort the array (in $O(n\log n)$), then have 2 pointers in to the array, one at the start and one at the end. These two numbers give you the smallest number times the biggest number. What does it mean if the resulting product is smaller (or bigger) than the target?

# Answer
> 0 votes
I can think of O(nlogn) complexity. Sort the array in O(nlogn) time, have two pointers( say *head* and *tail* ), head pointing to the first element and tail pointing to the last element of the sorted array. Now, run a *for* loop i.e O(n) , in which multiply the head and the tail element, if (product = sum) then output head and tail elements, else if (product \< sum) then increment head. Else decrement tail.

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


# Question
Title: How is the complexity/size of a problem (for instance SAT) determined?
We say an algorithm runs in polynomial time if it is of the form $O(n^k)$ where $n$ is the size of the input, right?

So how do we judge how many inputs there are in: $(x\_1 \vee x\_2 \vee \overline{x\_3}) \wedge (\overline{x\_1} \vee \overline{x\_2} \vee x\_4) \wedge (x\_2\vee x\_3\vee x\_5)$

...actually, in looking for an actual definition of an algorithm running in polynomial time, wolframAlpha says: "*An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is $O(n^k)$ for some non-negative integer $k$, where $n$ is the complexity of the input.* "

So, then my question is, for my example, what is the complexity of the input? Is the complexity based on how many variables, or how many clauses?

# Answer
> -2 votes
The complexity of SAT relates to the number of arguments to the Boolean function (i.e. the "distinct literals" in the expression), not the number of terms in a particular normal form.

The complexity of an *algorithm which solves SAT* is related to the size of the input that you give it. So if the input is the Unicode string `(x1∨x2∨¬x3)∧(x1¬∨x2¬∨x4)∧(x2∨x3∨x5)`, then the size of that is the number of Unicode codepoints (or bytes or bits used to encode those codepoints).

The subject of SAT is the function, not the representation of the function. The complexity class (i.e. the complexity of any solver which is optimal for its computer) is the same whether functions are written as product-of-sums or a sum-of-products. This complexity varies with the number of arguments to the function.

The input to a SAT solver is the representation of the function. Your example is in the product-of-sums normal form, which is a common way to express SAT problems. This is not a coincidence — SAT is solved mindlessly if you instead give it a sum-of-products expression! The brute-force method of solving SAT is to enumerate the sum-of-products, where each term either contradicts itself (b ¬b) or represents a satisfied piece of the function's domain. This simple approach doesn't trivialize SAT because going from one normal form to the other causes a combinatorial explosion. The size of the domain of a function of $n$ Boolean arguments is $2^n$.

Thus, feeding a gigantic problem description into a simple algorithm may have the same computational (and space) complexity as feeding a simple but equivalent description into a sophisticated algorithm. For brevity, we tend to prefer to imagine the description to be simple and the algorithm to be complicated.

---
Tags: computability, np-complete, logic
---


# Question
Title: lower bound of checking if in array are two different elements
Considering the lower limit to the problem of checking whether the array are only the same number via comparisons. And thnik about $ n-1 $. Consider the diagram hasse. This diagram must be consistent (one piece), so you need at least $ n-1 $ edges (comparisons),.

However, I would like to consider a decision tree. Unfortunately, I can not consider this, look how I think about it.

# Answer
Decision tree lower bounds don't quite work here. The obvious way to apply a decision tree lower bound is to consider the output of the algorithm, which is either TRUE or FALSE. Since there are two possible outputs, the decision tree lower bound gives a lower bound of one comparison. Not very helpful.

A more interesting example of the decision tree technique forces the algorithm to output a little more, namely either it outputs YES (all the elements are the same), or a pair of different elements (represented as their indices). You can argue that whenever the algorithm returns NO it actually knows two elements which are different. Considering all inputs of the form $x\_1 = \cdots = x\_{i-1} = x\_{i+1} = \cdots = x\_n = 0, x\_i = 1$, we see that for each $i$ there must be a leaf of the form $(i,\ast)$. This means that there must be at least $n/2$ NO leaves, resulting in a lower bound of $\log\_2(1+n/2)$ on the number of comparisons. This can plausibly be improved to $\log\_2(1+\binom{n}{2})$, but both quantities are $\Theta(\log n)$.

The correct way to argue here is using an *adversary argument*. Consider any algorithm, and trace its execution, always answering YES to any query. Consider the graph whose vertices are all elements (i.e., all indices), and the edges correspond to queries performed by the algorithm. If the graph is not connected, the algorithm can't know whether all elements are the same (indeed, it is consistent both that all elements have the value $0$, or that the elements in the $i$th connected components have the value $i$). Since a connected graph has at least $n-1$ edges, any algorithm must perform as least $n-1$ comparisons. It's not hard to see that this bound is achievable.
> 1 votes

---
Tags: arrays, lower-bounds
---


# Question
Title: Balanced weight distribution in buckets, with different weight per bucket
Is this problem a know variant of the optimisation version of the bin packing problem? There is an approximating algorithm for it?

> Let $A = \\{a\_1,a\_2,...a\_n\\}$ be a set of items, $B = \\{b\_1,b\_2,...b\_m\\}$ be a set of buckets, with $m \leq n$. Each $a\_i$ has a weight, based on the bin it is placed on (the item $a\_i$ when placed on bin $b\_j$ has weight $W\_{i,j}$). Let $T(b\_j)$ represent the total weight of the bucket $b\_j$, $T(b\_j) = \sum\_{c=1}^t W\_{c,j}$, which is the sum of the weights of each $a\_c$ placed in $b\_j$.
>
> What is the optimal way to distribute all the items $a\_i$ into the buckets $b\_j$, such that each bucket $b\_j$ has the almost same $T(b\_j)$?

This problem came up when I'm trying to distribute a load in a distributed system, with distributed memory, such that each computer has almost the same amount of work. However, in my problem, when an item $a\_i$ is placed in a specific computer, some other items from another set, say $x\_{d..t}$, aggregate the work load on that server. The matrix $W\_{c,j}$ is the map of the aggregated weights, for all choices of $b\_j$ for the item $a\_i$.

# Answer
This problem is known as Unrelated Parallel Machine Scheduling. Minimizing $max\_j T(b\_j)$ has a 2-approximation, by LP-relaxation and rounding.
> 2 votes

---
Tags: optimization, packing
---


# Question
Title: Selection algorithm variant for an array
Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with.

> Let $A = A\[1\], ..., A\[n\]$ be an array of $n \ge 4$ distinct keys.
>
> Describe an *efficient* algorithm to find the **three** smallest keys in $A$. Use words.
>
> What is the *worst case* number of comparisons performed by your algorithm? Try to find an **exact** number. Ignore floors and ceilings. Explain your answer.

I would assume you use the randomized $k$-selection algorithm where $k=3$, but if you're recursively partitioning a group of integers around a pivot I'm not sure how you'd find $k=2$ and $k=1$ short of running the algorithm 3 times.

Ideas?

# Answer
> -1 votes
Well, here's what I came up with.

You could use Merge Sort, which has a worse-case time complexity of $O(n (log (n))$, then take the first 3 values of the array, but it felt like this question was seeking the use of the Randomized Select algorithm.

Best case for Randomized Select would be select $3$ (or $1$) as your random pivot and then make a comparison to the left or right of that for the other two spots, giving you a complexity of $n-1+1$ or $\Omega(n)$.

But this is asking for worst case. By my calculation if an adversary is always picking the furthest pivot from the target (say $k=3$), then the time complexity would be: $$\frac{n(n-1)}{2} $$ For example. Let's say you have an unsorted array of $7,5,9,8$. The third smallest number is $8$ so the worst pivot is $5$. Compare $7,8,9$ (which is $n-1$ comparisons), you see there are 3 numbers greater.

The next worst pivot is either $7$ or $9$, so pick one of those, and $n-2$ comparisons, you see $8$ and $9$ are greater than 7. You know that $5$ is the smallest, $7$ is the second smallest, but you still need the third smallest. Repeat.

Pick $9$ as your pivot and make $n-3$ comparisons to see that $9$ is the 4th smallest, meaning $8$ is your 3rd smallest.

Add up those comparisons and simplify, you get the formula quoted above. Worst-case this seems less efficient than Merge Sort and selecting the first three numbers, but this seemed like the application of Randomized Select that the question was leaning toward (based on the book and classroom work).

Hope this helps someone else.

---
Tags: algorithms, asymptotics, partial-order, selection-problem
---


# Question
Title: Efficient algorithms for dealing with linear algebra over the rationals
I'm an academic mathematician. While trying to verify a counterexample to something in my research, the following computational problem has arisen:

Fix a vector space $V = \mathbb{Q}^n$. Here $n$ is something on the order of $20,000$. I have a procedure that spits out a sequence of vectors $\vec{v}\_1,\vec{v}\_2,\ldots$ in $V$. The vectors $\vec{v}\_i$ all have integer entries; these entries are bounded in size (by something on the order of 20 or 30). For each $k \geq 2$, I need to decide if $\vec{v}\_k$ is in the $\mathbb{Q}$-span of the set $\\{\vec{v}\_1,\ldots,\vec{v}\_{k-1}\\}$.

What algorithm should I use for this? The naive thing to do would be to just use Gauss-Jordan elimination (or, if I want to mostly stick with integers, compute the Hermite normal form). However, experiments I have done show that the size of the numbers that arise when you do this explode in complexity even for much smaller problems. This accords with stuff I have found while searching the literature, though I don't know the computer science literature very well and have trouble determining the state of the art in stuff like this.

# Answer
One trick I've seen elsewhere is to pick a random prime $p$, reduce everything modulo $p$, and check whether the vectors are linearly independent over $(\mathbb{Z}/p\mathbb{Z})^n$. If $p$ is not a divisor of any of the entries of the vectors, and if $v\_k$ is not in the $(\mathbb{Z}/p\mathbb{Z})^n$-span of $v\_1,\dots,v\_{k-1}$, then $v\_k$ isn't in the $\mathbb{Q}$-span of $v\_1,\dots,v\_{k-1}$, either. By picking $p$ to be large enough (larger than the largest of the vector-entries), you can be sure $p$ won't be a divisor of any of the entries.

So, this provides a pre-test you can use. You run the pre-test first (working modulo $p$), and if it outputs "linearly independent", then you don't need to run the expensive $\mathbb{Q}$-span test; on the other hand, if it outputs "linearly dependent", then you do need to do the expensive $\mathbb{Q}$-span test (e.g., Gaussian elimination).

And, I think there's a heuristic argument that if $p$ is random and large enough, then if it's $\mathbb{Q}$-independence then with high probability (over the choice of $p$) it'll be $(\mathbb{Z}/p\mathbb{Z})^n$-independent, too. Or something like that. But it's just a heuristic and no guarantee that it'll work for all situations.

I hope I have this right. I'm going from memory so I might have something backwards. Check my logic, and try it on your situation, and see if it helps in your application or not.
> 2 votes

---
Tags: algorithms, linear-algebra
---


# Question
Title: I know Binary Search is more efficient than Ternary search, but my results are opposite. Help interpreting results?
I have a piece of code that applies recursive Binary and Ternary searches on sorted arrays of increasing size, i.e. 500, 1000, 2000, 4000, etc. The entire code segment is about 200 lines so I've been forced to upload it to Pastebin which you can find here. When the main method is executed, arrays are created and populated according to some heuristic, which here happens to be A\[i\] = 8 * sqrt(i). The arrays are then searched to see if they contain a key that's randomly generated and may or may not be in the array.

I've ran the tests over a dozen times and each time, the ternary search outperforms the binary search in terms of average comparisons needed before finding the key or knowing that it's not in the array. Shouldn't Binary Search have fewer comparisons if it's a better complexity (log(2) (n) instead of 2\*log(3)(n))? Are my sample sizes too small or have I made a mistake in my code somewhere? For example, here's some sample output:

```
Binary search results:

Average number of comparisons for array of size 500: 7.4
Average number of comparisons for array of size 1000: 7.0
Average number of comparisons for array of size 2000: 8.1
Average number of comparisons for array of size 4000: 9.3
Average number of comparisons for array of size 8000: 9.0

Ternary search results:

Average number of comparisons for array of size 500: 4.6
Average number of comparisons for array of size 1000: 7.0
Average number of comparisons for array of size 2000: 5.3
Average number of comparisons for array of size 4000: 5.9
Average number of comparisons for array of size 8000: 6.0

```

Note: The 'y' variable in the code is the number of comparisons, this is an assignment and that's what it's supposed to be named as per the specs.

# Answer
As already noted in the comments, the experiment doesn't measure the amount of comparison operations, but instead it measures the depth of the recursion needed to find the given number. Here's code that should produce a proper experiment (replacing value $\rightarrow target$, lo $\rightarrow low$, $hi \rightarrow high$, $y \rightarrow comparisons$ for readability):

**int** $\texttt{binarySearch}$(array $a$, **int** $target$, **int** $low$, **int** $high$, **int** $comparisons$):

$\quad$\__int\__ middle = $\frac{low+high}{2}$;

$\quad$ **if** ($a$\[middle\] $= target$) **then**

$\quad\quad$\__return\__ comparisons+1;

$\quad$ **else if** ($target$ \< a\[middle\]) **then**

$\quad\quad$ **return** $\texttt{binarySearch}(a, target, low, middle-1, comparisons+2)$

$\quad$ **else**

$\quad\quad$ **return** $\texttt{binarySearch}(a, target, middle+1, high, comparisons+2)$;

And similarly for $\texttt{ternarySearch}$:

**int** $\texttt{ternarySearch}($array $a$, **int** $target$, **int** $low$, **int** $high$, **int** $comparisons$):

$\quad$\__if\__ $a\left\[low + \frac{high-low}{3}\right\] = target$ **return** $comparisons+1$;

$\quad$\__else if\__ $a\left\[low+ 2\frac{high-low}{3} \right\] = target$ **return** $comparisons+2$;

$\quad$\__else if\__ $target \< a\left\[low + \frac{high-low}{3} \right\]$ **return**

$\quad\quad\texttt{ternarySearch}(a, target, low, low + \frac{high-low}{3}-1, comparisons+3)$

$\quad$ **else if** $target \< a\left\[low + 2\frac{high-low}{3} \right\]$ **return** $\texttt{ternarySearch}(a, target,$

$\quad\quad low + \frac{high-low}{3}+1, low + 2\frac{high-low}{3}-1, comparisons+4)$

$\quad$ **else return** $\texttt{ternarySearch}(a, target, low + 2\frac{high-low}{3}, high, comparisons+4)$

Hope this helps. You might still have to catch the $low \> high$ case. Lastly, you test your cases by populating your array with $a\_i = \sqrt{i}$, and then measuring with $\texttt{xSearch}(rand(max = 8\sqrt{n}))$. Is there any reason you test specifically that way? Your results will be skewed because you will (especially with larger $n$) query your array for relatively low indices. It is better methodologically, unless your target application is representative of this test case, to populate your list with numbers $1 \ldots n$, and then to shuffle the list at random, to produce a random permutation. Then query for item $rand(max=n)$.
> 2 votes

---
Tags: algorithm-analysis, binary-search
---


# Question
Title: A variation of the baseball elimination problem
I suppose you are all familiar with the baseball elimination problem (it is about determining whether some team with particular number of points can finish in the first place, when there are still such and such games to be played by other teams).

The rules there are rather simple - the winner gets a point, while the loser gets nothing. But what if we changed those rules, so that the loser would get -1 point for each game lost. Could it still be brought down to the max-flow problem then? I've been thinking about this, but there's no way to do that in my opinion.

# Answer
> 1 votes
I am not familiar with the baseball elimination problem, but nevertheless, if you can solve the original problem, then you can solve the new problem. Here is why. For each game that a team has to play, deduct 1 from its score. Instead of awarding it 1 point if it wins, award it 2 points. It still gets 0 if it loses. This moves us closer to the original problem.

In order to get the original problem as stated, we divide all scores by 2, converting the 2 point award to a 1 point award. This reduces the new problem to the original one, which you already know how to solve.

---
Tags: graphs, max-flow
---


# Question
Title: Backpropagation for 'Classification' Neural Network
Question: How does one formulate a back propagation algorithm (either batch, gradient, anything that works) for a neural net, playing a game of Tic Tac Toe?

(Java is being utilized)

Scenario: There are 9 input neurons, one for each square. A value of -1 represents X, 1 represents O, and 0 represents an empty space. These values are stored in 1x10 array (the tenth input being bias). These lead to a single hidden layer, with n nodes (n selected on boot). The weights between the input and hidden layer are stored in a 10 x n array. A typical sigmoid activation function is used on the hidden layer. The hidden layer then leads to 9 output neurons, with weights stored in a n x 9 array. A separate function is used to normalize the output, dividing every point by the largest output, and whichever neuron is storing "1", the next move is made there. I've gotten this portion to work.

The cost function is as follows- Every board has an "advantage", which is equal to 10(turns till lose) - 8(turns till win) - 100(boolean invalid\[i.e. placing a piece over another piece\]). A negative advantage is bad for the AI, positive is good. Cost therefore, is cost = 1/2(best possible delta(advantage), - the delta(advantage) that the AI comes up with)^2. Squared in order to make the function convex, multiplied by .5 for the power rule to make it cleaner.

Here lies the problem: I need to calculate the derivative, so I know what way is down hill. How do I calculate the derivative for the advantage function, if it uses if statements, loops, etc.? It really is more of an operator, than a function- is there a way to re-write a cost function for tic-tac-toe which would be more conducive to machine learning? Or is there a way to derive around this?

I hope I explained that correctly- P.S. This is not for a class, rather my own blatant curiosity.

# Answer
As D.W. points out, please consult a textbook on neural networks, or Wikipedia. The answer to your question lies in the insight that neural networks do not inspect the cost function or algorithm used to compute it, but it is an empirical method. That is, you will have to play many games of Tic Tac Toe (or generate configurations at random, whichever), compute the cost function yourself, and then feed the configuration with its cost function to your neural network, which then does backpropagation, and repeat. Alternatively, you may collect a large batch of data and feed the batch to the neural network. Either way, the gradient of the network at a particular configuration is a value computed only from available data.

That said, and while most numerical algorithms have no well-defined derivatives, there are edge cases, for example the identity function $f(x) = x$, but most have no practical use. Then there are algorithms that estimate the derivative of a function such as the one you supplied form a large batch of data that a neural net can use to aid its search by improving its gradient estimate, but that will get you into some very deep waters. Deep waters, but fun waters, so consult a textbook if you want to know about that.
> 1 votes

# Answer
The way you do back propagation for neural network has nothing to do with what you are using the neural network for. It depends only on the structure of the neural network.

Consequently, all that information about tic tac toe doesn't seem relevant.

Lots of textbooks explain how to do backpropagation for a neural network. I suggest you try applying the description of how to do backpropagation from a textbook; or seek out an existing implementation of a neural network that does backpropagation for you.
> 0 votes

---
Tags: machine-learning, neural-networks, classification
---


title: Computing mod inverse?

text:
# Question
Title: Computing mod inverse?
How might one compute $4^{-1} \mod 17$ I know the answer is 13. I'm just not sure how to arrive at that number, and can't find any good explanations. Any help would be great

# Answer
In order to compute the inverse of $a$ modulo $n$, use the extended Euclidean algorithm to find the GCD of $a$ and $n$ (which should be 1), together with coefficients $x,y$ such that $ax + ny = 1$. The inverse of $a$ modulo $n$ is thus $x$.

The extended Euclidean algorithm gives a constructive proof of Bézout's identity, which states that for all integers $a,b$ there exist integers $x,y$ such that $ax+by = \mathrm{gcd}(a,b)$. A different proof shows that the minimal positive value of $ax+by$ (over all $x,y$) is $\mathrm{gcd}(a,b)$.

The extended Euclidean algorithm works in greater generality, for any Euclidean domain. An important example is the ring of polynomials over a field.
> 3 votes

---
Tags: modular-arithmetic
---


title: Root Color of a Black Red Tree

text:
# Question
Title: Root Color of a Black Red Tree
It is required that, in a black red tree, the color for the root is always black. However, wikipedia argues that this rule can be omitted as a red root can always be changed to black but not vice versa. I get the first half, that a red root can be changed to black at any time, but in what circumstance is it impossible to change a black node to red?

For instance, consider the branch: `black`--`red`--`black`--`red`--`black`. We can always change it to `red`--`black`--`black`--`red`--`black`, since a black node does not need to have red children.

# Answer
The root colour of a red-black tree carries no significance. In fact, you can save memory by not encoding it. Didactically, it is meaningful to talk about a root's colour to illustrate what it means to be red or black, because it is a special case because it has no parent which is going to count it when it evaluates the sixth restriction in Wikipedia's list (that the path from a particular node to a leaf should contain the same number of black nodes).

As for your more general question about when changing a black node to a red one is allowed: a set of nodes can be repainted if afterwards, the black-height criterion is still satisfied. For example, if a row of the tree is saturated (if it is at depth $k$, there are $2^{k}$ nodes), then you can colour that row black. You may not colour only part of a (saturated or not) red row black. Another example: in the tree $1:red \rightarrow\\{ 2:black, 3:black\rightarrow\\{4:red, 5:red\\}\\}$, you can flip the colours of $\\{3,4,5\\}$ and still have a legal RB tree. This is true generally for subtrees of even height and alternating colours. Maybe you can think of more examples.
> 2 votes

---
Tags: sorting, balanced-search-trees
---


# Question
Title: How does FDS (flat datacenter storage) make optimizations around locality unnecessary?
I was reading the following computer systems paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

And I was trying to understand why it claims that it does not need data locality for it be perform well.

Basically, in the abstract it says:

"...FDS multiplexes an application's large scale I/O across the available throughput and latency budget of every disk in a closer. FDS therefore makes many optimizations around data locality unnecessary."

What I was not sure was, why does multiplexing an applications I/O across the servers in the datacenter, make it unnecessary to have to optimize in terms of data locality?

Basically, as I read the paper they make a big deal that locality is something they don't need and that they can achieve the benefits of it without having servers being close to the clients they provide data access. The part I am not sure is, what is the crux of what makes them not depend on data locality? Is it the CLOS network? Is it because they don't serve clients around the world? Is it because their servers are all in one data center anyways and not scattered around the world? What is it that makes their performance be so amazing?

---

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin

# Answer
> 2 votes
The paper you cited is exploring the consequences of the question "what if datacenter network bandwidth was free?" There are two reasons you might care about data locality. One is latency and the other is bandwidth. The workloads they are looking at (mostly) don't care about latency, and they've made bandwidth irrelevant, hence locality doesn't matter. (Note however that at the end of Section 6.2 (on Page 12) they discuss how the inefficiency of non-local accesses forced them to use more compute nodes for their sorting algorithm.)

They also aren't *completely* eliminating locality optimizations. Each compute node is still caching/buffering reads and writes in its local DRAM. The rule of "avoid unnecessary I/O" still stands. It's just that you don't make a distinction when you do a disk access of whether the disk is near or far from your compute node. All disk accesses are assumed to include the extra latency of a round-trip network traversal.

Here's a picture to show the difference. The authors' "flat" storage model is on the left, the traditional "distributed" storage model is on the right:

In the distributed model (on the right) data is either on a local disk or a remote disk. In the flat model (on the left) data is *all* remote. But since the network bandwidth is (effectively) infinite, this doesn't reduce your maximum data bandwidth.

# Answer
> 0 votes
Their design is based on a "non-oversubscribed full bisection-bandwith network" (the CLOS network you mentioned). And due to this assumption you can consider accessing remote disks as fast as local ones.

Now comes the trick: if you regard every blob as a file, then this "file" is essentially **scattered uniformly on a bunch of servers (disks)** . And you can read/write this file parallely with a aggregated bandwidth (thanks to the full-bisection-bandwidth assumption) of all these servers. By the way, another important reason that enables this parallism is that: since the data distributing scheme is generated by a deterministic function, it is unnecessary to contact the metadata server most times.

On the contrary, although traditional designs store the whole dataset distributedly, each "file" (or anything that represents the data unit) is stored on a single server (as well as some replicas, maybe), and that exactly causes the problem of data locality.

Strictly speaking, each "tract" in the FDS is stored locally in a tractserver. But a tract could be so small compared with the blob size that, it's unlikely to do some computation with a single tract -- you always deal with plenty of tracts within some blob, which by design are scattered around, thus eliminate locality problems.

This viedo explains the thinking behind the FDS neatly.

---
Tags: distributed-systems, fault-tolerance
---


# Question
Title: efficient cumulative all over combinations of boolean vector elements
### Problem

Given a vector of bools of length `n` I wish to compute the *logical and* over all subsets up to length `k`.

By *logical and* I mean that for a subset to give `true` all of its elements must be `true`.

### Example:

With a boolean vector of 3 elements (indexes below each for reference below)

`v = [true, true, false]`
`i = 0 1 2`

The intended result for all subsets (i.e. up to `k = n`):

`result = [true, true, false, true, false, false, false]`
`i.e 0 1 2 0&1 0&2 1&2 0&1&2`

where the `true` at `01` is the result of `true & true` from the `0` and `1` indices in the original vector.

If we limit up to `k = 2` the intended result is:

`result = [true, true, false, true, false, false]`
`i.e 0 1 2 0&1 0&2 1&2`

The order of the output need not be this one.

### What I want

I want an algorithm that will not perform more operations than it needs to specify the entire result. Reducing the number of operations should lead to improved performance.

My current approach is to iterate the combinations and subset the vector with each and reduce it via logical `&`. But this is very wasteful as for `012` I recompute the result of `01`... There must be a better algorithm but I am having no success.

# Answer
You can do this without computing the logical AND's at all: you can enumerate all subsets that consist entirely of "true" and enumerate all subsets that contain at least 1 "false".

First, enumerate all subsets of length $k$ with all "true".

Then, enumerate all subsets of length $k$ that contain the first occurrence of "false" in the vector.

Then, enumerate all subsets of length $k$ that contain the second occurrence of "false" but not the first.

Etc...
> 1 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Determine the move in which a LOGO turtle crosses a point that it has already visited
I was given the following problem in an test (at codility.com)

> A turtle starts at (0, 0) on a cartesian graph. We have a non-empty zero-indexed "moves" list that contains positive integer numbers. Each number represents the distance moved. The first number is the distance north, the second is the distance east, the third is the distance south, the fourth is the distance west, and so forth. Therefore the directions cycle every four moves.
>
> Find an algorithm that gives the move number that makes the turtle cross a point that it has already visited before.
>
> The move number is the index of the "moves" list.
>
> This algorithm should have O(n) time complexity and O(1) space complexity.
>
> Example:
>
> If given this move list: \[1, 3, 2, 5, 4, 4, 6, 3, 2\]
>
> The move number answer is then 6. (It's the 7th move).
>
> Draw it on a graph, the turtle will go:
>
> (0,0) -\> (0,1) -\> (3,1) -\> (3,-1) -\> (-2,-1) -\> (-2,3) -\> (2,3) -\> (2,-3)
>
> At this 6 move number (7th move) it will meet (2,1) which is a point that the turtle has already crossed.

I have been struggling with for quite a time, because I intuitively think there's no way to meet both space and time complexity requirements, unless there's some hidden structural property in the problem I'm not noticing. For example, if the path does not cross itself it forms an spiral-like curve, and therefore each north move must be greater than the previous south move, and viceversa. The same applies to the east and west moves. Therefore, not meeting this property implies the curve will eventually cross itself, but gives no indication on which move does it.

My main problem is that I've not been able to identify the type or algorithmic problem this problem relates (e.g. sorting)

# Answer
> 2 votes
Hint: Find some constant $C$ such that if the turtle ever crosses its own path, then it must hit one of the last $C$ segments in the path. (I think that $C=5$ should work.)

# Answer
> 2 votes
Complementing Yuval's hint: the turtle will necessarily produce one (and only one, possibly infinite) outward spiral, and possibly an additional inward spiral, necessarily finite. For each of these two stages, the algorithm is a bit different.

For the first stage (see picture below) there are at most 4 reachable segments, two of them (numbers 3 and 4) possibly in two different ways $-$ from the inside, or from the outside. The blue area is completely unreachable.

For the second stage, the number of reachable segments is three. The transition between these two stages is shown in the next picture. The dotted segments are now unreachable.

From then on, the inward spiral obeys the following pattern:

---
Tags: computational-geometry
---


# Question
Title: Finding median of three sorted array (the same length)
I think about following problem:
There are given three sorted arrays $A,B,C$ (each of them is length $n$).
Every array has distinct elements. Find median of union $A,B,C$.

I consider following approach:
Let's consider $A\_i, B\_i, C\_i$, where $i=n/2$. There are six cases - but I consider only one (rest of them is analogous). Let $A\_i\le B\_i\le C\_i$: Now we may dispse $1/3$ elements - $A\[1...n/2\]$ and $C\[n/2 + 1... n\]$.
Unfortunately I can't estimate time of run this algorithm.
I should solve recusrion equality: $T(n) = T(2/3n) + 1$
$(T(0) = T(1) = 1$, but I can't.

I am thinking about better algorithm. Can you suggest something ?

**Edit**
I am goint to say more about this algorithm. The key idea is using Divide and conquer method. In each step we may dispose $\frac{1}{3}$ elements. Lets $i = n/2$. Let suppose that $A\_i \le B\_i \le C\_i$ (rest of cases is analogous). Look at example:

In every case I dispose $1/3$ elements and get smaller problem.

# Answer
The recurrence relation can be solved as follows: for large $n$,

$$T(n) = T\left(\frac{2}{3}n\right) + 1 = T\left(\frac{2^{2}}{3^{2}}n\right) + 2 = \cdots = T\left(\left(\frac{2}{3}\right)^kn\right)+k$$

This iterative process ends when a $T(m)$ is called with $m \leq 1$. Now for what $k$ do we have $\frac{2^{k}}{3^{k}}n \leq 1$? It is $ ^{\frac{3}{2}}log(n)$. (verify this for yourself)

A good way to do this is using an insight from the $\texttt{MergeSort}$ algorithm. It sorts an algorithm by consequtively merging increasingly long sorted substrings. Here's how it goes: you keep three indices, say $i,j,k$, which start at $0$. You iterate them over the three arrays, each time incrementing the index which points to the highest value of its respective array, until you've encountered half of all elements, i.e. $i+j+k=\frac{3n}{2}$. When that has happened, you have encountered the median. Here's this algorithm as pseudocode:

$\texttt{TernaryMedian}(\texttt{array } A, \texttt{array } B, \texttt{array } C):$

**int** $i, j, k :=0$

**while** $i+j+k \< \frac{3n}{2}$ **do**

$\quad$ **if** $A\_i \> B\_j$ **then**

$\quad\quad$ **if** $A\_i \> C\_k$ **then** $i := i + 1$

$\quad\quad$ **else** $k := k + 1$

$\quad$ **else if** $B\_j \> C\_k$ **then** $j := j + 1$

$\quad$ **else** $k := k + 1$

**end while**

$median := max(A\_i, B\_j, C\_k)$

This algorithm runs in time $O(n)$ and makes $3n$ comparisons in the best case and $\frac{9}{2}n$ comparisons in the worst; I'll leave the average case to you. This algorithm can be improved if you keep a pointer to the array containing the highest value of any of the pointers but which was not the subject of last iteration's increment. I'll leave it up to you to figure out why. Then you get $\frac{3}{2}n+1$ comparisons in the best case and $3n$ comparisons in the worst.

It may help to first look up $\texttt{MergeSort}$ on Wikipedia for merging two substrings, and then think about how you would merge three substrings. Hope this helps.
> 1 votes

---
Tags: arrays, search-problem, binary-search
---


title: Total number of edges in the graph

text:
# Question
Title: Total number of edges in the graph
Consider a `directed` graph with nodes `{1,2,3...n}` and include an edge `(i,j)` whenever `i<j`.

According to me, it should be `n(n-1)/2` but the book says it's nC2(combinations).

# Answer
> 1 votes
Did you try working out what n choose 2 evaluates to?

---
Tags: graphs
---


title: number of edges in a graph

text:
# Question
Title: number of edges in a graph
I got a problem related to graph theory -

Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1\<=i,j \<=12}. There is an edge between (a, b) and (c, d) if |a-c|\<=1 and |b-d|\<=1 The number of edges in this graph is

Answer is given as 506 but I am calculating it as 600, please see attachment.

I am unable to get why it is coming as 506 instead of 600.

Thanks

# Answer
> 6 votes
For a grid in the range of $\[n\_1,n\_2\]$, according to the problem statment, the number of edges is:

$$\\#edges=\frac{8 \times (n\_2-n\_1+1)^2- 4\times 5-4\times3\times(n\_2-n\_1-1)}{2}$$

**explanation**: suppose every node has a degree of 8, then sum of the degrees is $8\times(n\_2-n\_1+1)^2$; For each corner we included 5 extra edges that must be removed (the term $4\times5$) and for every other border node we considered 3 more edges (the term $4\times3\times(n\_2-n\_1-1)$).

The solution for your problem is:

$$\frac{8(12-1+1)^2-4(5)-4\times3\times(12-1-1)}{2}=\frac{8(144)-20-12(10)}{2}=\frac{1012}{2}=506$$

# Answer
> 2 votes
**Method 1**

This is one kind of problem you can write a program to solve instantly. We are counting the number pairs satisfying the conditions you state. First generate the vertices (I'm using Python).

```
vertices = []
for x in range(1, 13):
  for y in range(1, 13):
    vertices.append([i, j])

```

Next count the pairs satisfying the conditions.

```
count = 0
for p in pts:
  for q in pts:
    if p != q:
      a, b = p
      c, d = q
      if abs(a - c) <= 1 and abs(b - d) <= 1:
        count = count + 1

```

Every edge has been counted twice, hence the answer is `count / 2`.

**Method 2**

There are four types of edges: vertical, horizontal, diagonal (slope 1 and -1). Observe that the number of vertical edges is equal to the number of horizontal edges and the number of slope -1 diagonal edges is equal to the number of slope 1 diagonal edges. So the total number of edges is 2 * #vertical + 2 * #diagonal.

The number of vertical edges is $11\times 12=132$. The number of diagonal edges is $2\times(1+2+\dots+10)+11=121$. $132\times 2 + 121 * 2 = 506$. This can be generalized to a square grid of any size: if the $1\le i,j\le n$, then the number of edges is $$2(n(n-1) + (n-1)(n-2) + (n-1)) = 2(n-1)(2n-1)$$.

Plug $12$ in the formula and you get $506$.

# Answer
> 1 votes
This is simple math no need to generalize any folrmula.

condition type1 :a=c

condition type2: a-c=1 or c-a=1.

total combinations satisfying condition1 : 12

total combinations satisfying condition2 : 11 (I am taking only one case either a-c=1 or c-a=1 .Think about it why?)

so satisfying combinations for 'a' and 'c' = 11+12 =23

IN Similar way satisfying combinations for 'b' and 'd' = 23

```
[ a     b]
      *
[ c     d]

```

So total solutions = 23\*23 = 529

Now there are some cases where loop exists like :

```
[1,2]        [5,5]
[1,2]   OR   [5,5]

```

There will be 23 such cases .Why ?? :)

So remove such cases : 529-23 = 506

visit : http://yougeeks.blogspot.in/2015/01/consider-undirected-graph-g-where-self.html#more

# Answer
> 0 votes
Total number of vertices $= 12\*12 = 144.$

The graph formed by the description contains $4$ (corner) vertices of degree $3$ and $40$ (external) vertices of degree $5$ and $100$ (remaining) vertices of degree $8.$

According to (handshake theorem's)

$2|E|=$ sum of the degrees

$ 2|E| = 4\*3+40\*5+100\*8= 1012$

$|E| = 1012/2 = 506$ edges.

---
Tags: graphs, combinatorics, counting
---


title: Alternative graph data structures

text:
# Question
Title: Alternative graph data structures
Are there any graph implementation data structures beyond the standard adjacency list/matrix ones? If so, what are they?

I welcome experimental ones as well as highly specialized ones.

A little background: I'm developing an algorithm that relies heavily on graph operations, so I'm doing research in graph implementation. I'm not looking for out-of-the-box solution, but rather for additional material in hope to combine my findings into something that will optimize my algorithm.

An adjacency matrix is not suitable for me in its core form, because it is costly to resize. In my environment, vertices are expected to be frequently added/removed.

An adjacency list is a bit better approach. Yet, it lacks the ability to efficiently cross-reference information from different nodes. Further, the graph is weighted, so I need immediate neighbors sorted for a fast search. However, the weights are also dynamic: they change frequently (are explicitly updated) and decay with time (change implicitly based on the type/time of the last operation).

The graph is expected to have somewhere between 50 and 100 vertices. Once a new vertex is added, it will form edges with some or all of the other vertices, depending on its life time.

I've tried using sorted lists, but still haven't found any efficient way to accommodate all the criteria listed above. I also considered hash-tables, similar to the answer below, but they don't solve the problem with sorting.

# Answer
Here are some examples of slightly different approaches:

# Hash-table

Key into hash-table is a vertex, value is a list of vertices it is connected to, the edge is thus a relation between the key and the element of the value in the hash-table. This is not so different from adjacency list except that testing for presence of the vertex will be faster, but it will take more spece to store the graph.

This, obviously, describes a directed graph. You could include the reversed edges to make it work as undirected graph.

Example (JavaScript):

```
function graph() {
    var vertices = {}, g = { vertices: vertices };
    g.getVertex = function (vertex) {
        return vertices[vertex];
    };
    g.getEdge = function (from, to) {
        var adjacent = vertices[from], result;
        if (adjacent.indexOf(to) > -1) result = [from, to];
        return result;
    };
    g.addEdge = function (from, to) {
        var edges = vertices[from] || [];
        edges.push(to);
        vertices[from] = edges;
    };
    [].slice.call(arguments).forEach(function (edge) {
        g.addEdge.apply(g, edge);
    });
    return g;
}
graph([1, 2], [1, 3], [2, 1], [2, 3], [3, 5], [3, 6], [3, 4],
      [4, 7], [5, 2], [5, 6], [6, 3], [6, 7]);
// { vertices:
//    { '1': [ 2, 3 ],
//      '2': [ 1, 3 ],
//      '3': [ 5, 6, 4 ],
//      '4': [ 7 ],
//      '5': [ 2, 6 ],
//      '6': [ 3, 7 ] },
//   getVertex: [Function],
//   getEdge: [Function],
//   addEdge: [Function] }

```

# Graph-proper data structure

We define vertex as a tuple of the value and a list of edges from this vertex to other vertices it is directly connected to. This is a little bit more compact than the hash-table, but testing whether vertex is in a graph becomes linear (just as in adjacency list / matrix). Same as before we can add edges in the opposite direction to make this graph undirected. This is different from adjacency list in that retrieving all adjacent vertices to a given vertex is a constant time operation, while in the list it is linear in time. Adjacency matrix would also give constant time for this, but will use more space, especially if a graph is sparse.

Example (Prolog):

```
:- use_module(library(record)).

:- record vertex(value, arcs=[_ | _]).

lookup(X, [X | _]).
lookup(X, [Y | Xs]) :- X \== Y, lookup(X, Xs).

instantiated(Goal, [X | _], []) :- \+ call(Goal, X).
instantiated(Goal, [X | Xs], [X | Ys]) :- call(Goal, X), instantiated(Goal, Xs, Ys).

vertex_instantiated(Vertex) :-
    make_vertex([], Vertex),
    vertex_value(Vertex, Value),
    ground(Value).

find_vertex_helper(Value, _, Vertex) :- vertex_value(Vertex, Value).
find_vertex_helper(V1, Cache, V2) :-
    vertex_arcs(V2, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    subtract(InstArcs, Cache, FilteredArcs),
    union(Cache, InstArcs, NewCache),
    findnsols(1, V, (member(V, FilteredArcs),
                     find_vertex_helper(V1, NewCache, V)),
              [V2]).

find_vertex(_, [], _) :- !, fail.
find_vertex(Value, [V | Graph], Vertex) :-
    vertex_value(V, Value), Vertex = V
    ;
    vertex_arcs(V, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    include(find_vertex_helper(Value, []), InstArcs, [Vertex])
    ;
    find_vertex(Value, Graph, Vertex).

find_or_create_vertex(Value, Vertex, Graph, Graph) :-
    find_vertex(Value, Graph, Vertex), !.
find_or_create_vertex(Value, Vertex, OldGraph, [Vertex | OldGraph]) :-
    make_vertex([value(Value)], Vertex).

add_arc(From, To, OldGraph, NewGraph) :-
    find_or_create_vertex(From, VertexFrom, OldGraph, Graph1),
    find_or_create_vertex(To, VertexTo, Graph1, NewGraph),
    vertex_arcs(VertexFrom, Arcs),
    lookup(VertexTo, Arcs).

make_graph_helper([], Graph, Graph).
make_graph_helper([From-To | Vs], GraphIn, GraphOut) :-
    add_arc(From, To, GraphIn, NewGraph),
    make_graph_helper(Vs, NewGraph, GraphOut).

make_graph(Vs, Graph) :- make_graph_helper(Vs, [], Graph).

make_graph([x1-x2, x1-x3, x2-x1, x2-x3, x3-x5, x3-x6, x3-x4,
            x4-x7, x5-x2, x5-x6, x6-x3, x6-x7], G).
/*    G = [vertex(x7, [_G3910|_G3911]),
           vertex(x4, [vertex(x7, [_G3910|_G3911])|_G3891]),
           _S1, _S2,
           vertex(x3, [_S2, _S1, vertex(..., ...)|...]),
           vertex(x2, [_S3, vertex(..., ...)|...]), _S3],
           % where
          _S1 = vertex(x6, [...]),
          _S2 = vertex(x5, [...]),
          _S3 = vertex(x1, [...]) */

```
> 4 votes

---
Tags: graphs, data-structures
---


title: What does $CS - CF$ means?

text:
# Question
Title: What does $CS - CF$ means?
What does $L\_1 \in CS - CF$ means?

I think the meaning is $L\_1$ can be generated by context-sensitive grammars, but cannot be generated by context-free grammars.

Am I understanding this correctly? Just to be sure.

# Answer
You understand this correctly. the set $CS - CF$ denotes the strict difference between these two levels of the Chomsky hierarchy. If you are reading this in a textbook, you will soon learn that $CS-FS \not= \emptyset$, that is, context-sensitive grammars are strictly more expressive than context-free ones. For example, context-sensitive grammars can *count*, whereas context-free ones, not so much: the language $\\{a^nb^nc^n | n \in \mathbb{N}\\} \in CS-CF$.
> 3 votes

---
Tags: formal-languages, notation
---


# Question
Title: What's the formal definition of Big-O notation for functions of more than one variable?
For functions of a single totally ordered variable, I already know that $f(n)$ is $O(g(n))$ if and only if $\exists m. \exists c. \forall n. (n \ge m) \rightarrow \[ f(n) \le c \cdot g(n) \]$.

What I don't know is the meaning of $O(g(n\_1, n\_2 \dots n\_k))$ for $k \> 1$ totally ordered variables. What's the formal definition?

# Answer
There are many possible definitions; see e.g. Rutanen et al. \[1\].

Generally speaking, if you define your $O$ over domain $X$, you will need an order relation $\leq$ on $X$. The definition then reads:

$\qquad O(g) = \\{ f : X \to \mathbb{R}\_{\geq 0} \mid \exists\\,x\_0 \in X, c \in \mathbb{R}\_{\>0}.\ \forall\\,x\in X.\\ \qquad\qquad\qquad x\_0 \leq x \implies f(x) \leq c \cdot g(x) \\}.$

So if $X = \mathbb{N}^k$ you can use lexicographic order, element-wise $\leq$, ...

Beware that the properties your $O$ has depend on both the definition and the the order you choose. The outcome may not be as expected.

---

1. A general definition of the O-notation for algorithm analysis by K. Rutanen et al. (2015)
> 3 votes

---
Tags: asymptotics, landau-notation
---


title: Comparing two graphs

text:
# Question
Title: Comparing two graphs
I want to compare the vertices of two graphs. Given two graphs, $G\_1 = (V\_1, E\_1)$ and $G\_2 = (V\_2, E\_2)$, I want to compare $u\_n$ and $v\_m$ for $u \in V\_1$ and $v \in V\_2$. I came up with double loops for doing this:

```
for all u in G1
  for all v in G2
    if u.label == v.label then
       do something here
    end if
  end for
end for

```

Now the above two loops have the time complexity of $O(n) = n^2$. Is there a better way of doing this , i.e. a more efficient algorithm, assuming that no other information is available?

I looked at the raph isomorphism problem (https://en.wikipedia.org/wiki/Graph\_isomorphism\_problem). But here I am not trying to find out if the two graphs are isomorphic.

Is there a better/more efficient approach for doing this?

# Answer
A more efficient approach would be to group the vertices according to their labels, and only run the double loop for vertices in the same group. In the worst case (if all vertices have the same label) this is still $\Omega(n^2)$, but if there are relatively few vertices sharing the same label this is much more efficient.

This also assumes that the "do something"-bit doesn't change the label (and that the order of the "do something"s doesn't matter).
> 2 votes

---
Tags: algorithms, graphs, lower-bounds
---


# Question
Title: How does one make an unambiguous context-free grammar for arithmetic expressions?
Say I have a context-free grammar defined by the following rule.

$$ \langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x $$

This grammar is ambiguous since, for instance, I can generate the string $x + x \times x$ via more than 1 leftmost derivation.

How could I make this grammar unambiguous? Should I make sure that no $\langle EXPR\rangle + \langle EXPR\rangle$ is evaluated after a $\langle EXPR\rangle \times \langle EXPR\rangle$ as such:

$$ \langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle MUL\\\_EXPR\rangle \times \langle MUL\\\_EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\ \langle MUL\\\_EXPR \rangle \rightarrow \langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\ $$

# Answer
Indeed you made a step to resolve ambiguity, but your solution does not give a fully unmabiguous grammar yet. The string $x+x+x$ can be parsed in two different ways, like $x + \[x+x\]$ or like $\[x+x\]+x$, where the brackets indicate parses. As far as I see your solution resolves semantical ambiguities (it fixes the relative order of + and x) but not the syntactical ambiguity. So obtaining an umambiguous grammar is not the only goal for an example like this: we want to respect meaning (here operator precedence). (Perhaps there is more official terminology for that)

Your example is a familiar one, and is used in wikipedia/Syntax diagram:

```
<expression> ::= <term> | <expression> "+" <term>
<term>       ::= <factor> | <term> "*" <factor>
<factor>     ::= <constant> | <variable> | "(" <expression> ")"

```

Probably you will know that not every grammar has an unambiguous equivalent, so no general approach is possible.
> 3 votes

# Answer
i don't think there is a fixed method of derivations to make a grammar unambiguous. you have to try by trail and error method by adding new non-terminals to the grammar without changing the definition of that grammar.
> 2 votes

# Answer
If you do not care about semantics, the way to remove ambiguities is to

1. derive different operators in non-overlapping "phases" (operator precedence) and
2. create the same operators in a fixed order (associativity).

So, for instance, if you want $\times$ to bind stronger than $+$ and left-associativity, you'd do

$\qquad\begin{align\*} S &\to S + A \mid A, \\ A &\to A \times T \mid T, \\ T &\to \text{\[any atoms you want\]}. \end{align\*}$

This is now unambiguous, and quite restricted in terms of what expressions we can write down (semantically speaking); the user has to multiply all their expressions out completely.

You note, of course, that I left out the parentheses. That is because they pose no problem; if we demanded parentheses everywhere, we would not have ambiguity. Therefore, we can add parenthesized expressions to our grammar without introducing ambiguity. By adding an alternative $(S)$ ("start anew inside a new scope") to every "move to the next phase" non-terminal, we get this:

$\qquad\begin{align\*} S &\to S + (S) \mid S + A \mid (S) \mid A, \\ A &\to A \times T \mid A \times (S) \mid (S) \mid T, \\ T &\to \text{\[any atoms you want\]}. \end{align\*}$
> 2 votes

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


# Question
Title: Schedule tasks from a weighted list with time frame constraints
I'm attempting to create an automatic scheduler from a list of tasks I have available. Here are the key points:

* Each task has been given a priority beforehand and the algorithm should try to maximize the total 'priority points' it can get from the tasks it schedules.
* There should be no overlap between any tasks.
* Each task might have several time constraints.

Here's an example:

$$ \begin{array}{c|c|c|c} \text{Task} & \text{Duration (min)} & \text{Time Frames} & \text{Priority} \\ \hline \text{Read a book} & 80 & \text{5:00pm-8:00pm} & 2 \\ \text{Go to the store} & 45 & \text{5:00pm-7:00pm} & 5 \\ \text{Eat popcorn} & 15 & \text{6:00pm-8:00pm} & 1 \\ \text{Ask the internet} & 25 & \text{5:00pm-6:00pm,7:00pm-8:00pm} & 8 \\ \text{Exercise} & 60 & \text{5:00pm-7:00pm} & 6 \end{array} $$

And a schedule it could make would be (each character is 5 mins): `| 5:00-6:00 | 6:00-7:00 | 7:00-8:00 |
| Store || Exercise | |Ask||E| |` Which scores a total of 20 points (which I believe is the maximum in this example)

I realize this problem may be NP-Hard so, because of the nature of this project, the solution doesn't need to be optimal.

What I've come up with so far is something like the following:

1. Sort the task list based on priority (t\*lg(t))
2. Find each 'block' of time, divided on each time frame boundary of the tasks (t) and store in a set. Then sort the set (f\*lg(f)).
3. For every block, attempt to place a task, starting with the highest priority, at the earliest point available in the block. Repeat until there is no room for any task in the block. (t)
4. Extend the end of the block to the end of the next block and repeat 3. If no task can fit into the earliest point, move the earliest point to the beginning of the next block used for the beginning. (For instance, block 1 is filled as much as possible, so it is expanded to the beginning of block 1 to the end of block 2. No tasks can start at the beginning of the remaining space between blocks 1 and 2, so it moves the beginning of the active block up to the beginning of block 2).
5. Repeat 4 until there are no more blocks. (f)

Total: f\*t + f\*lg(f) + t\*lg(t)

This greedy algorithm doesn't seem ideal and it will certainly fail horribly in some scenarios (such as a 60 min, high priority task from 1:00-3:00, and a lower priority task from 1:00-2:00). What is the best way to approach this problem?

# Answer
This smells like it's probably NP-hard, but for the number of tasks you are likely to have in real life, there are reasonable algorithms to compute the best solution.

For instance, you could solve this using integer linear programming. Take the LCM of all durations, so that each task takes an integer number of time slots (in your example, the LCM is 15 minutes, so each slot is 15 minutes long). Now introduce zero-or-one variables $x\_{i,j}$, with the intended meaning that $x\_{i,j}=1$ if your schedule starts doing task $i$ at time slot $j$. You can add linear inequalities to require that no two tasks be scheduled at an overlapping time (e.g., $x\_{i,j}+x\_{i',j}\le 1$ and so on), and linear inequalities to require that each task be performed within its allowable time frame (e.g., $x\_{i,j}+x\_{i,j+1}+\dots +x\_{i,j'} \le 1$; $x\_{i,j''}=0$ for all other $j''$). Finally, introduce an objective function that captures the total score of your solution, $\sum\_{i,j} c\_i x\_{i,j}$, where $c\_i$ is the priority of $i$.

Finally, solve this ILP using an off-the-shelf ILP solver. I expect that in practice, with a reasonable number of tasks this will often find an exact optimal solution. And even if the number of tasks is too many to find an exact solution, many ILP solvers have a mode of operation that will tell them to output the best solution they found so far after (say) 5 minutes of CPU time.
> 1 votes

# Answer
I'd be inclined to punt the problem to an integer linear programming problem solver. (Note that many solvers will take a timeout argument that'll return the best solution they've found so far if/when the timeout triggers)

Encode each task as a rational (or potentially integer, depending) for the time of the start of the task and a boolean for if the task is going to be done, with appropriate bounds constraints predicated on if the task is going to be done (note that when you have multiple possible time slots for a task you'll need to encode the bounds as "at least one of these time slots are valid").

Then for each pair of distinct tasks add a constraint that either the first task starts after the second one finishes or vice versa.
> 2 votes

---
Tags: algorithms, scheduling
---


# Question
Title: How powerful is a k-stack pushdown automaton with a unary stack alphabet?
I'm interested in pushdown automata with a unary stack alphabet: let's call them UPDA's. Define a $k$-UPDA to be a pushdown automaton with $k$ stacks, each with a unary stack alphabet.

I've figured out that a $k$-UPDA is at least as powerful as a $(k-1)$-PDA (see proof at the end). This implies that a $k$-UPDA is equivalent in power to a Turing machine when $k \ge 3$ (as it is at least as powerful as a Turing machine when $k \ge 3$, as you can simulate a TM with a 2-PDA, and by the Church-Turing thesis, no more powerful).

A 1-UPDA is more powerful than a NFA/DFA, as a 1-UPDA can recognize, for instance, the language $\\{0^n1^n:n \in \mathbb{N}\\}$. But, at the same time I *suspect* (although I do not know) that a 1-UPDA is less powerful than a 1-PDA.

My questions are as follows:

1. What is the complexity class recognized by a 1-UPDA? Or at the very least, are there better bounds than "more powerful than a NFA/DFA and no more powerful than a 1-PDA"?
2. What is the complexity class recognized by a 2-UPDA? Or at the very least, are there better bounds than "at least as powerful than a 1-PDA and no more powerful than a 2-PDA"? In particular, is a 2-UPDA more powerful than a 1-PDA?
3. Is there a $k$ such that you can simulate a TM with a $k$-UPDA without exponential overhead?
4. Is there a standard name for a UPDA?

---

Proof that a $k$-UPDA can simulate a $(k-1)$-PDA: use one stack for scratch space. You emulate a stack alphabet of $m$ symbols with a unary number, base $m$. To push a number $x$ to a stack, you multiply the number of elements in the stack by $m$ and then push $x$ more symbols. (You also need to check for if the stack is empty, but that is simple enough.) To pop a number, you modulo the stack by $m$ for the number to pop, and divide the number of symbols in the stack by $m$.

# Answer
> 4 votes
Such automata are called counter-automata. Each counter holds a natural number, which can be tested for zero. (So your UPDA has a single stack symbol plus a way to recognize the empty stack.)

Two push-downs are Turing complete, i.e., they can compute any Turing computable function. Basically, because two stacks can simulate a queue. So you have proved yourself that 3-UPDA is Turing complete. But actually two counters are enough. The trick is to code two numbers $(i,j)$ into a single number $2^i 3^j$ and doing your own construction again.

The family of languages is called one-counter languages, which have some fame in formal language theory. I browsed my own old answers and found: Which languages are recognized by one-counter machines?

Also: The simulation of TM's by counter automata is explained in the old textbook by Hopcroft and Ullman (Intro to Automata Theory, Languages, ...) in two steps. First using four counters and coding the contents of (half of) a working tape of a TM by a single number. The result is attributed to Minsky (1961).

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


# Question
Title: Hardness of a special GAP-CLIQUE problem
In the GAP-CLIQUE$(k,\ell)$ problem, we are given a graph $G$ over $n$ vertices and have to decide whether $G$ contains a clique of size $k$ or no clique of size $\ell$. Using a PCP system, it can be shown that GAP-CLIQUE$(k,\varepsilon k)$ is NP-hard for any positive constant $\varepsilon$ less or equal to $1$. In fact, even GAP-CLIQUE$(k,n^{\varepsilon - 1}k)$ is NP-hard. However, I am interested in GAP-CLIQUE instances, where $k$ and $\ell$ depend on the size of $G$. In particular, I am wondering if GAP-CLIQUE$(3/4n,1/4n)$ is NP-hard.

# Answer
> 4 votes
The problem is solvable in polynomial time, using the following algorithm:

> Keep removing pairs of unconnected vertices, until a clique remains.

If the graph has a clique of size $(3/4)n$, then the clique you end up with contains at least $n/4$ vertices (exercise).

Source: Boppana and Halldórsson, Alon and Kahale.

---
Tags: np-hard, approximation, clique
---


# Question
Title: Time complexity of minimizing Boolean expression
Given any arbitrary boolean expression using AND, OR and NOT gates what is the time complexity of minimizing the expression such that minimum number of gates are used.

The following Wikipedia article only talks about the space complexity of the problem (which is PSPACE), but does not talks about the time complexity.

https://en.wikipedia.org/wiki/Circuit\_minimization\_for\_Boolean\_functions

# Answer
> 1 votes
The Wikipedia article states that the problem is $\Sigma\_2^P$-hard, and in particular it's NP-hard. Therefore it's probably not solvable in polynomial time (unless P=NP).

---
Tags: time-complexity, space-complexity, circuits
---


title: How to deal with Multiple Logs? (Big O)

text:
# Question
Title: How to deal with Multiple Logs? (Big O)
So I couldn't figure this one out, what do i do when i have multiply logs as the running time of an algorithm.

For example:

f(n): loglogn g(n): logloglogn

Does f = Omega(g) in this case? as in g is a much slower growing algorithm than f?

# Answer
> 2 votes
The starting point is the limit $$ \lim\_{n\to\infty} \frac{\log n}{n} = 0, $$ which can also be stated succinctly as $\log n = o(n)$. If $f(n)$ is any function such that $\lim\_{n\to\infty} f(n) = \infty$, it then follows that $$ \lim\_{n\to\infty} \frac{\log f(n)}{f(n)} = 0, $$ or more succinctly, $\log f(n) = o(f(n))$. In particular, taking $f(n) = \log n$ we get $\log\log n = o(\log n)$, taking $f(n) = \log\log n$ we get $\log\log\log n = o(\log\log n)$, and so on.

More generally, if $a(n) = o(b(n))$ and $f(n) \to \infty$ then $a(f(n)) = o(b(f(n))$. (The case above was $a(n) = \log n$ and $b(n) = n$.) There are similar rules for big O, which I leave for the reader to discover.

---
Tags: algorithms
---


# Question
Title: Why is a deterministic Turing machine a special case of a probabilistic Turing machine?
I have no formal training in computer science as I have not yet taken any such classes, so perhaps this question appears naive. I was reading about BPP and it was claimed that a deterministic Turing machine is a special case of a probabilistic Turing machine. I don't understand why this is.

# Answer
Deterministic turing machines have one transition at any given time. Nondeterministic machines are allowed to have multiple transitions out of a given state but can have just a single. Probabilistic turing machines pick one of the possible transitions and perform it based on a probability distribution. So if you make a deterministic turing machine then it is also a probabilistic turing machine where there is only ever one transition to choose from at any given time.
> 6 votes

# Answer
Probabilistic Turing machines are similar to deterministic Turing machines, but have the additional power of tossing coins. If you never make use of this power, you get a deterministic Turing machine.

In a similar fashion, a non-deterministic Turing machine is allowed to make guesses, but if it doesn't it is just a deterministic Turing machine.
> 6 votes

---
Tags: turing-machines
---


title: Can NP-Hard be converted to NP?

text:
# Question
Title: Can NP-Hard be converted to NP?
I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem.

Can an NP-Hard problem be reduced to an NP problem, which is not already an NP-Complete problem?

Also, are NP-Hard problems inter-convertible?

# Answer
The picture I always visualize for this is the one featured on here on the Wikipedia page for **NP**-Completeness. The definition of **NP**-Hard is that it is the set of problems to which all **NP** problems can be reduced in polynomial time, so, for example, the bounded halting problem - does a Turing Machine $M$ halt within $k$ steps, is strictly *not* in **NP**, because there is no way to check in polynomial time whether a Turing Machine halts in $k$ steps. However, all problems can be converted to the bounded halting problem very easily, simply by building a Turing Machine which ostensibly solves the problem and asking whether it halts in some appropriate amount of time.

This answers your first question: not all **NP**-Hard problems are in **NP** or can be reduced to them. As for the second: Some **NP**-Hard problems can be converted to one another. For example, the **EXP-TIME** class, which can be though of as the next class beyond **P**, has **EXP-TIME**-Complete problems just like **NP** has **NP**-Complete problems, and there are classes even beyond that, indefinitely.
> 5 votes

# Answer
> Can an NP-Hard problem be reduced to an NP problem, which is not already an NP-Complete problem?

No. Suppose that $X$ is **NP**-hard and it reduces to $Y$. By definition of **NP**-hardness, every problem in **NP** reduces to $X$. By transitivity of reduction, every problem in **NP** also reduces to $Y$, so $Y$ is **NP**-hard. Since $Y$ is postulated to be in **NP**, $Y$ is **NP**-complete.

> Also, are NP-Hard problems inter-convertible?

Not necessarily, no. **NP**-hard problems aren't even necessarily decidable: the halting problem is **NP**-hard, for example.

For more examples, consider the classes $k$-**EXP** for integers $k\geq 1$. $1$-**EXP** is just **EXP** (exponential time, i.e., time $O(2^n)$), $2$-**EXP** is problems decidable in time $O(2^{2^n})$, $3$-EXP is triply-exponential $O(2^{2^{2^n}})$ and so on. By the time hierarchy theorem, all of these classes are different, which means that a $k$-**EXP**-complete problem is not in $(k-1)$-**EXP**. But a $k$-**EXP**-complete problem is certainly **NP**-hard because **NP**$\\,\subseteq\\,$**EXP**$\\,\subseteq k$-**EXP**. So, you can take an infinite sequence $X\_1, X\_2, \dots$ of problems where $X\_i$ is $i$-**EXP**-complete for each $i$. Each of these problems is **NP**-hard but $X\_k$ is provably not reducible to $X\_j$ for any $j\<k$.
> 3 votes

---
Tags: np-complete, np-hard, complexity-classes, np
---


# Question
Title: implementation of queue using stack with REVERSE
> Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions.

---

I'm looking for implementation of queue where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction , or any better algorithm .

# Answer
Your queue should append items to the rear of the stack, and get them off the top, so here's a pseudocode implementation of your two functions:

$\texttt{Queue::Enqueue}(e):$
$\quad$Reverse;
$\quad$Push($e$);
$\quad$Reverse;

$\texttt{Queue::Dequeue}():$
$\quad$\__return\__ Pop;

Verify for yourself whether and why these functions produce the desired behaviour: why does the $\texttt{Enqueue}$ function reverse the stack, but not $\texttt{Dequeue}$?
> 2 votes

---
Tags: data-structures, stacks
---


title: Kleene star differences

text:
# Question
Title: Kleene star differences
We have languages $A= \\{a\\}$ and $B = \\{b\\}$. If we consider $(A\cup B)^\*$, where ${}^\*$ means Kleene star, we have a set of words like $\\{\lambda, a,b,aa,ab,aaa,\dots\\}$, where $\lambda$ is the empty word. Another example we do is $A^\*(BA^\*)^\*$. If we concatenate two languages, $\lambda$ will not be in the set, but the Kleene star adds the $\lambda$. Question is, is this set same as the set with union so $\\{\lambda,a,b,aa,ab,aaa,\dots\\}$ or is the set for the second example $\\{a,b,aa,ab,aaa,\dots\\}$, in which case the langauages would not be equal. My opinion is that concatenation is the last operation so sets are not equal but I'm not sure.

# Answer
> 3 votes
Unless parentheses say otherwise, the customary precedence is ${}^\*$ (like exponentiation), then concatenation (like multiplication), then union (like addition).

Your second example is the concatenation of starred expressions, so it does contain the empty string.

---
Tags: formal-languages, regular-languages, kleene-star
---


# Question
Title: What's the time complexity of this algorithm? And Why?
I am stuck by analyzing the time complexity of the following algorithm:

```
def fun (r, k, d, p):
    if d > p:
        return r
    if d = 0 and p = 0:
        r <- r + k
        return r
    if d > 0:
        fun (r, k + 1, d - 1, p)
    if p > 0:
        fun (r, k - 1, d, p - 1)

```

The root call will be `fun (0, 0, n, n)`, and `n` is the size of the problem.

I guess that: The recurrence relation is $ T(n, n) = T(n-1, n) + T(n, n-1)$, which is equivalent to $T(2n) = 2T(2n-1) \iff T(m) = 2T(m - 1)$, and so $O(2^m) \iff O(4^n)$.

Is my analysis correct (I know it's not very complete and exact)? If it does have serious flaw, please point it out or show me a correct and complete proof on the time complexity of this algorithm.

# Answer
> 10 votes
The only two arguments relevant to asymptotic analysis are $d$ and $p$. These arguments (virtually) satisfy $d,p \geq 0$ and $d \leq p$ (we need to shuffle the logic in the function slightly to get this). At each point in the execution, you take the current pair $(d,p)$ and then recursively call the function with the pairs $(d-1,p),(d,p-1)$, avoiding pairs which invalidate the constraints stated above.

We can picture the resulting call tree as a path starting at $(0,0)$. Each time you decrease $p$, add a / step. Each time you decrease $d$, add a \ step. The condition $d \leq p$ guarantees that you never go below the X axis. Moreover, you have a "budget" of $n$ of each step. The total number of *leaves* in this call tree is exactly the Catalan number $\binom{2n}{n}/(n+1) = \Theta(4^n/n^{3/2})$, and this gives us a lower bound on the running time of the function.

To get an upper bound, note that on the way to each leaf we pass through $2n$ nodes, and this gives an upper bound $2n$ larger than the lower bound, i.e., $\Theta(4^n/\sqrt{n})$.

We have a lower bound of $\Omega(4^n/n^{3/2})$ and an upper bound on $O(4^n/\sqrt{n})$. What are the exact asymptotics? They grow like the total number of paths not crossing the X axis which have at most $n$ steps in each direction. Using Bertrand's ballot theorem we can get an exact expression for this: $$ \sum\_{0 \leq d \leq p \leq n} \frac{p-d+1}{p+1} \binom{p+d}{p}. $$ It thus remains to estimate this sum asymptotically: $$ \sum\_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum\_{0 \leq d \leq p \leq n} \frac{d}{p+1} \binom{p+d}{d} = \\ \sum\_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum\_{0 \leq d \leq p \leq n} \binom{p+d}{p+1} = \\ \sum\_{p=0}^n \binom{2p+1}{p+1} - \sum\_{p=0}^n \binom{2p+1}{p+2} = \\ \sum\_{p=0}^n \frac{1}{p+1} \binom{2p+2}{p} = \Theta\left(\sum\_{p=0}^n \frac{4^p}{p^{3/2}}\right) = \Theta\left(\frac{4^n}{n^{3/2}}\right). $$

# Answer
> 0 votes
Case by case:

1. **d \> p**: *Constant* time
2. **d=0 ∧ p=0**: *Constant* time
3. **d \> 0**: Note that d ≯ p, so we have 0 \< d ≤ p, and `fun` recurses on d-1 until d ≯ 0; since p \> 0, this is *Linear in d + (case 4)*.
4. **p \> 0**: Note that d ≯ 0, so we have d ≤ 0 ≤ p (with d \< p), and `fun` recurses on p-1 until p ≯ 0; this is *Linear in p + (one of case 1, 2, or 5)*
5. **d ≤ p \< 0**: Undefined; I'm assuming this is *Constant* time

Starting with d = p = n \> 0 hits case 3, which is followed by case 4. If n is a whole number, the final case is 2, otherwise the final case is 5. The total time for those cases is d+p+1, or 2n+1.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Complexity of calculating average across distributed network?
What is the communication complexity of the **best known** algorithm for computing the average of a set of N\*D numbers distributed across N nodes with D values per node? Assume you have full control over the network topology and protocol.

# Answer
You could rely on the fact that, as @polygeric alluded to, the average of a set of numbers is the average of the averages over any partition of the original numbers. In other words, have each node compute the average of its $D$ numbers, send those $N$ averages somewhere and compute their averages.

How you do that efficiently will depend on the network topology and the communication protocol.
> 2 votes

---
Tags: complexity-theory, distributed-systems, parallel-computing
---


# Question
Title: Binomial coefficient to approach multi-way choices DP problem?
I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book. Not homework: i've already a solution, just considering if i'm ok with the theory.

> Suppose we want to replicate a file over a collection of $n$ servers $S\_1, S\_2 , \ldots , S\_n$. Each server $S\_i$ has a placement cost $c\_i$ to place a copy of the file at $S\_i$. If a user requests the file from $S\_i$ and no copy is present, then servers $S\_{i+1}, S\_{i+2}, S\_{i+3}, \ldots$ are searched in order until a copy is found, say at $S\_j$ (where $j \> i$). This results in an access cost $a\_i$, where $$ a\_i= \begin{cases} j-i \qquad \hbox{if $S\_i$ does not contain a copy the file} \\ 0 \qquad \hbox{ if $S\_i$ contains a copy of the file} \end{cases} $$ We require that $S\_n$ contains the file, so that all searches will terminate. Given $I \subset \left\\{1,\ldots, n − 1\right\\}$, a subset of servers to place the file on, we define the total cost
>
> $$ c(I) = c\_n + \sum\_{i \in I} c\_i + \sum\_{i=1}^{n} a\_i $$
>
> To be the sum of the placement costs for each server that contains the file (recall that $S\_n$ must contain the file), plus the sum of the access costs associated with all $n$ servers. Design a polynomial-time algorithm to compute a subset I of servers to contain the file that minimizes total cost.

My approach is to consider every possible choice, like for other problems e.g. segmented least squares, ending up with a $O(n^4)$ running time algorithm.

Anyway it looks like there is a better solution, given by the following recurrence:

$$ OPT(j) = c\_j + \displaystyle\min\_{0 \leq i \< j}(OPT(i)+\binom{j-i}{2}) $$

With the initialitazions $OPT(0)= 0$ and $\binom{1}{2}=0$. The answer is given as usual by $OPT(n)$. This is to me very counterintuitive: why the binomial coefficient, and why the number $2$?.

Is it a standard way to approach similar problems?

# Answer
> 4 votes
The binomial coefficient here appears through the formula $$ \sum\_{i=1}^{n-1} i = \binom{n}{2}. $$ In the formula, $OPT(j)$ is the minimal cost of a solution for the first $j$ servers. Another way of looking it that it's the minimal cost up to $j$ of a solution which puts the file in $S\_j$.

Where does the recurrence come form? Take an optimal solution for the first $i$ servers. We know that the file appears in $S\_j$. Let $S\_i$ be the next largest server it appears on (or $i=0$ if it only appears in $S\_j$). Without loss of generality, we can assume that the solution restricted to $S\_1,\ldots,S\_i$ is optimal, and so of cost $OPT(i)$. Putting the file in $S\_j$ costs $c\_j$. Accessing the file at positions $i+1,\ldots,j-1$ costs $(j-(i+1)) + \cdots + (j-(j-1)) = \binom{j-i}{2}$. This gives the recurrence formula. (We also have to verify the case $i=0$ separately, which I leave to you.)

---
Tags: dynamic-programming
---


title: Negation of 8-bit hexadecimal

text:
# Question
Title: Negation of 8-bit hexadecimal
I am looking for a mathematical formula / algorithm to find the negation of a 8-bit hexadecimal without having to expand into a binary form.

E.g;

0000BDDA -\> 48602

FFFF4226 -\> -48602

Need to get from 0000BDDA -\> FFFF4226 without 2' complements / expanding it to binary.

I've been cracking my head at it but to no avail.

Any ideas?

# Answer
Use the same formula as you do for two's complement. First, compute the *complement* of the number by complementing all letters. Then add 1. Complementing works using the following table: $$ 0 \leftrightarrow F, 1 \leftrightarrow E, 2 \leftrightarrow D, 3 \leftrightarrow C, 4 \leftrightarrow B, 5 \leftrightarrow A, 6 \leftrightarrow 9, 7 \leftrightarrow 8. $$ Example: starting with 0000BDDA, we first get FFFF4225, and after adding 1, we get FFFF4226.

Why does this work? Exercise.
> 0 votes

---
Tags: discrete-mathematics
---


# Question
Title: Prove: possible to construct automata accepting all strings of other automata sans 1-length strings
I believe that I have a procedure for doing this, but I don't know how to approach the proof (and for that matter I'm not entirely sure the procedure is correct).

Here's the exact problem statement:

> Given DFA $A = (\Sigma, Q, q\_0, F, \delta)$ construct DFA $B$ from $A$ s.t. it accepts all words of the language of $A$ which have length distinct from 1.

And here's pseudocode that has to solve the problem followed by some explanation:

```
def ensure_word_length_ne_one(alphabet,
                              states,
                              initial,
                              final,
                              transition_function)
 loops = [i for i in alphabet if transition_function(initial, i) == initial)]
 new = make_new_accepting_state()
 # all arcs to the states directly accessible from the initial state
 # except the arcs from the initial state
 backarcs = [(arc.source, arc.destination, arc.input)
             for arc in arcs_to(set(for arc in arcs_from(initial))) -
                                set(arcs_from(initial))]
 for input in loops:
   # Remove all loops from the first state
   add_transition(initial, new, input)
   remove_transition(initial, initial, input)
   add_transition(new, new, input)
 for input in alphabet:
   # Bounce back from the new state to the first state
   add_transition(new, initial, input)
 for source, destination, input in backarcs:
   # For each state directly reachable
   # from the first state reattach
   # all inbound transitions
   # to the new state
   new = make_new_accepting_state()
   remove_transition(source, destination, input)
   add_transition(source, new, input)
   outbound = [(arc.input, arc.destination) for arc in arcs_from(new)]
   for input, destination in outbound:
     # Bounce back from the new state
     # to the states immediately
     # reachable from source state
     add_transition(new, destination, input)

```

The code tries to be more or less Python. Auxiliary functions do what their name suggests. The basic idea is as follows:

A DFA can accept words of length 1 in only these two scenarios:

1. It loops on some input in the first accepting state.
2. The state directly linked from the first state is accepting.

Below is the procedure to remove these accepting states while accepting all other inputs.

1. If the first state loops on some inputs add a new state $q\_1$, remove all transitions from $q\_0$ to itself and add transitions for the same inputs from $q\_0$ to $q\_1$. Add transitions on all inputs from $q\_1$ back to itself.

For any input which on which $q\_0$ used to loop $B$ now necessary makes at least two transitions before accepting it, possibly accepted string with prefixes that did not cause the automate to loop on $q\_0$ are still accepted (nothing has changed).
2. For each accepting state $q\_n$ directly linked from $q\_0$ we do the following:
    * change $q\_n$ from accepting to non-accepting.
    * add a new accepting state $q\_2$.
    * remove transitions from states $Q\_i$ directly leading to $q\_n$, unless they originate in $q\_0$, for each transition removed add a new one for the same input from $Q\_i$ to $q\_2$.
    * for each outbound transition from $q\_n$ add new transition on the same input from $q\_2$.

---

Most proofs related to automata I've read so far use structural induction for similar tasks, but I cannot think about a way to approach the proof. The difficulty is in ensuring that all strings accepted by $A$ are still accepted.

PS. I have the pseudocode set in LaTeX, if it is necessary, I can add it to the post.

# Answer
Basically, the answer is what @Shaull says in the comments: construct a product automaton with the one that accepts all strings of length unequal 1. What we use here is the fact that regular languages are closed under intersection. The product construction takes two automata, and simulates them in parallel. States are pairs of states of the original two automata. The combination accepts if both components accept.

But you ask for "minimal operations". So, have a look at what is in fact the automaton that accepts strings of length not 1. It simply has three states "zero", "one" and "many" with a loop for each letter at the last state. It simply counts letters up to length two (and then keeps in that state).

The product construction for this specific automaton is rather straightforward. Set aside a copy of your original automaton $A$. (You might add label "many" to each of the states, but that is extra.) Now add to these fresh copies of the original initial state and all states reachable in one step from the initial state. If the initial state has a loop, it is copied twice. (If you fancy it these get extra labels "zero" and "one"). Now remove final states from the "one"s and copy the original wiring.

Like I said, this is just a particular case of the product construction. In fact it might be even what is in your own pseudo code.
> 3 votes

# Answer
1. Create a new starting state, which is accepting/non-accepting according to the original starting state. (The original starting state is still included, but is no longer the starting state.)
2. Identify all accepting states that can be reached in one transition from the starting state
3. Create new non-accepting states with the same outbound transitions as the states found in step 2.
4. Create transitions from the new starting state to each state created in step 3.
5. Create transitions from the new starting state to each non-accepting state reachable from the original starting state.

All inputs of length one now go to a non-accepting state.

(Updated: original answer was essentially steps 2 through 4 operating on the original starting state.)
> 1 votes

# Answer
The simplest way to do this is to add a new starting state, with transitions exactly like the original starting state. If the new state isn't final, the result doesn't accept $\epsilon$, and you are done. If the starting state of the original automaton isn't accepting, none of this is needed.
> -1 votes

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


# Question
Title: Inference rule with two conclusions or rather inverse function application
I want to express a simple correctness theorem for a term-desugaring function $\Delta$. The goal is to express that if the evaluation of a desugared term yields a value, this value is the desugared result of evaluating the original term.

Since the implication operator $\Rightarrow$ is already used in my dynamic semantics, I'd rather use an inference rule to express the implication. However, in the premise I have to introduce a variable $v$ that is the result of applying $\Delta$ to a variable bound in the conclusion. Since there is no inverse of $\Delta$ I am somewhat stuck between two odd variants to express the relation.

The first variant uses two conclusions (like multiple premises the idea is that **both** always hold):

$$ \frac{\Delta(t) \Downarrow v}{t \Downarrow v^\prime \quad \Delta(v^\prime) = v} $$

This looks odd to me. The alternative would be to see the rule as a scheme subject to some substitution over the meta-variables $t$ and $v$. In that case I could also write:

$$ \frac{\Delta(t) \Downarrow \Delta(v)}{t \Downarrow v} $$

This is obviously cleaner, but I am not quite happy with the implications (pun not intended) to the theorem: In the first case, if $v \neq \Delta(v^\prime)$ the premise still holds, but the conclusion does not, so $\Delta$ is not correct. In the second case the premise would not apply - so correctness simply does not cover the case at all.

Is there a common pattern to deal with such problems? Did I overlook something?

# Answer
Let us introduce an auxiliary predicate $t \downarrow$ whose intended meaning is "$t$ evaluates to something". Its inference rule is $$\frac{t \Downarrow v}{t \downarrow}.$$ Now you can express your condition with the following two rules:

1. If $\Delta(t)$ evaluates to $v$ and $t$ evaluates $v'$ then $v$ equals $\Delta(v')$: $$\frac{\Delta(t) \Downarrow v \qquad t \Downarrow v'}{\Delta(v') = v}$$
2. If $\Delta(t)$ evaluates to something then so does $t$: $$\frac{\Delta(t) \downarrow}{t \downarrow}$$.

This is not quite the same as using first-order logic and writing $(\exists v . \Delta(t) \Downarrow v) \implies \exists v' . t \Downarrow v'$. You have to go "meta" and use inversion to conclude from $t \downarrow$ that there exists $v'$ such that $t \Downarrow v'$.

By the way, you said that *"since the implication operator $\Rightarrow$ is already used in my dynamic semantics, I'd rather use an inference rule to express the implication"* That's a pretty awful reason to choose inference rules over axioms (which is what an implication would give you). You should ask instead what your semantics is for. If you are interested in operational semantics, i.e., you want to express how your programs will be executed, then the rule you are talking about does not really contribute anything. If you want your semantics for reasoning about $\Delta$ and $\Downarrow$, then it might actually be use good old first-order logic.
> 3 votes

---
Tags: formal-languages, programming-languages, correctness-proof
---


# Question
Title: how to make a regex that don't accept bab
hi how to make regex and 'DFA' to don't accept this 'bab' on this alphabet = {a,b} and accept all language except 'bab'

# Answer
> 1 votes
Here is a hint: For the DFA, first construct a DFA that will accept 'bab'. Then make final states into non-final states and vice versa. All you have to do is to think about error states. Finally, you might want to find the Regex from the DFA. Hint: How to convert finite automata to regular expressions?.

---
Tags: automata, regular-expressions
---


# Question
Title: Complexity for finding a ball that maximizes the number of points lying in it
Given a set of points $x\_1, \ldots, x\_n \in \mathbb{R}^2$ and a radius $r$. Which is the complexity of finding the point with higher number of points at a distance smaller than $r$. E.g the one that maximizes $\sum\_{i=1}^n \mathbb{1}\_{\\|x - x\_i\\| \leq r}$?

A brute force algorithm would be to go over every point and count the number of points that are at distance smaller than $r$. That would give a complexity of $\mathcal{O}(n^2)$.

Is there a better approach?

# Answer
It looks like a sublinear algorithm for the Ball Range Counting Problem isn't known for now.

However, if you could accept a non-exact answer then you could approximate a disk by a set of squares with different orientation. For each orientation you'll have to build a Range Tree, which will allow you to count all points inside a square in $O(log^2(n)+k)$ time (k - a number of resulting points).

Each range tree will require $O(n \cdot log(n))$ memory, the better approximation you want the more orientations you should use. For example, two orientations will give you an octagon, which approximates a disk with area error less than 6%.
> 5 votes

# Answer
The answer is not so simple, there is advanced study of this question in complexity theory; it seems to be studied e.g. as the following problem, which is focused around fast "spherical range counting" queries. Yes, improved theoretical bounds are possible, but these seem to be abstract algorithms that haven't been implemented by anyone. If you want actual implementations, that is a different question.
> 3 votes

---
Tags: algorithms, complexity-theory, computational-geometry
---