title: BinaryTree minimum possible height

text:
# Question
Title: BinaryTree minimum possible height
I have one question for which I don't know any good solution (and my solution doesn't satisfy constraints). Namely, on one of the interviews i got problem like this:

> Determine the minimum possible height of the binary tree, if you could remove `numNodes` leaf nodes from the tree (where after removal of all leaf children of node `n`, the node `n` becomes the new leaf node, and can be also counted as leaf). You are given the function `int minimumHeight(Node* root, int numNodes)`, where root is the pointer to the root of the tree, which should be completed, using any oop language.

Constraints are that you can't actually delete node from tree, and you can't use queue or stack, arraylist, list, hashmap, hashset, etc. (you cannot use any built-in c++ stl data structure, you can though make your own from scratch)
My solution used BFS where I stored for each node its level in tree using hashmap `m`, and created an array `arr` which contained all nodes, and then sorted it based on node levels in ascending order, and after that the function should return `m.get(arr[arr.length-numNodes-2])`. (i wrote code in java)
Without constraints I think this could work,but I guess it's not good enough.. Does someone maybe know is there some more elegant way to solve this? (without using unnecessary data structures, and maybe without any sorting) Thank you in advance!

Here if numNodes is 5, the minimum height you could obtain is 2,because first you must delete nodes with 5,11,4 or 2 value,and then you can delete nodes with values 9,6,etc. so in total you will have 5 possibly removed nodes, and 2 will be the minimum height of the tree.

# Answer
> 0 votes
I would leave a comment but I have less that 50 rep.

So, if I understand the question, DFS (or a way to parse the tree) is inevitable and all you need is an array (one cell for each level, plus one for the leaves) to count how many nodes are on each level. So given the numNodes you can start decrementing from the last (non-zero) element and check which would be the last non-zero element you will reach.

Also you don't actually need a stack, cause it is **already implemented** from the OS for you. So you just need to use a recursive algorithm passing each time the correct part of the array to the next call to calculate the nodes in the sub-tree. Now, all you need to know is the initial length of the tree. You run again the kind-of the same recursive algorithm but this time you are interested to know the total number of elements in the tree. Then the length of the array would be equal to the length of the total elements in the tree.

Time: O(n)

Space: O(n)

I'm not sure if I can write code here. I hope I was clear :)

---
Tags: algorithms, binary-trees
---


# Question
Title: Setting a cutoff for string distance filtering with different length strings
I'm working to filter a table of pairwise names (1.1 M rows) based on string distance algorithms. Most are names, though some are businesses.

Edit-based algorithms seem to be best, however in attempting to set a cutoff value for match vs. non-match, there is an issue with the length of the string. In a 16 character string, a score of 4 is usually a good match. But of course in a 4 character string, a score of 4 is a complete non-match.

What are good options for using a string distance algorithm, but scaling the scores relative to the length of the comparison strings? This doesn't seem to be built into any of the algorithms I've found.

# Answer
You can use normalized edit distance, where you divide the edit distance by the length of the larger of the two strings. Whether this is better will depend on what you are trying to achieve.

There are many other techniques for fuzzy matching, which you might want to investigate. The Levenshtein edit distance is only a starting point.
> 2 votes

---
Tags: string-matching
---


# Question
Title: Guessing the smallest unique positive integer
Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the players made their moves, computer outputs a name of winner – who submitted the *lowest unique* number.

How do you think, what is the best strategy for this game?

# Answer
There are a number of discussions of this game online, but you should be wary because some of them give incorrect solutions. This website gives an excellent exposition of how to solve this game. (Based in part on this paper.) You assume that all players use the same mixed strategy, and that when all players use this strategy, there is a Nash equilibrium. This gives equations which for three players have a closed form solution: you choose the integer $i$ with probability

$$ 0.839286 \cdot (0.543689)^{\textstyle i}$$

where 0.543689 is the solution of $x^3 + x^2 + x = 1$.

For $k$ players, if $k \geq 4$, the equations can still be derived, but they appear to have no closed form solution. However, in the optimal strategy the probability of playing a number larger than $k$ is very small, so an explicit nearly-optimal strategy can be found by solving the equations numerically.
> 12 votes

# Answer
Not enough reputation to comment, but, it is worth noting that if your opponents are playing by the Nash equilibrium strategy Peter Shor described for a 3 player game your chances of winning are around 29.6% irrespective of the number you choose. If you are only playing a single game (so no one can determine your strategy) and consider a draw between all players no better than a loss, a large number such as 89285829358008871 will give you the same chance of victory as a 1 or 2.

In this specific case, there's nothing to lose from trying a different strategy, just in case your opponents don't conform to your assumptions.
> -1 votes

---
Tags: game-theory, randomness
---


# Question
Title: Compute e^x given starting approximation
I have been looking for an algorithm to calculate $e^x$ to arbitrary precision (millions of digits). The best way I know is to use Taylor polynomials. However, the Taylor polynomial algorithm seems to have no way to enhance the precision of already existing estimates of $e^x$.

For example:

I already have an exact approximation for $e^{0.7}$ calculated to 1000 decimal places, but now I want an exact approximation of $e^{0.700000001}$ calculated to 100000 decimal places.

Because $e^{0.7}$ is very close to $e^{0.700000001}$, I should be able to use $e^{0.7}$ as a starting estimate for $e^{0.700000001}$. However, using Taylor polynomials, I know of no way to input a starting approximation.

Does anyone know of an algorithm that efficiently converges to $e^x$ given an initial estimate?

To clarify, I'm looking for an algorithm that can actually surpass the accuracy of the given estimation. For example, if I give it an estimate to 1000 digits, it should still be able to converge accurately beyond 10000000 digits. This rules out the optimization $e^{0.70001} = e^{0.7} \cdot e^{0.00001}$.

# Answer
The obvious answer to "I have an approximate solution to an equation and I want to improve it" is Newton-Raphson. If you have an approximation $y \approx e^x$ then you can improve it to $$y' = y - \frac{(\ln y) - x}{y^{-1}} = y(1 + x - \ln y)$$

Now you need an efficient way of calculating $\ln y$, but here I note that Wikipedia, commenting on high precision logarithms, says (my emphasis):

> Another alternative for extremely high precision calculation is the formula $$\ln x \approx {\frac {\pi }{2M(1,4/s)}}-m\ln 2,$$ where $M$ denotes the arithmetic-geometric mean of $1$ and $4/s$, and $$\displaystyle s=x2^{m}\>2^{p/2},$$ with $m$ chosen so that $p$ bits of precision is attained. (For most purposes, the value of $8$ for $m$ is sufficient.) **In fact, if this method is used, Newton inversion of the natural logarithm may conversely be used to calculate the exponential function efficiently.**

The references given are *Practically fast multiple-precision evaluation of log(x)*, Sasaki and Kanada (1982), Journal of Information Processing 5(4) pp247–250; and *Fast Computations of the Exponential Function*, Ahrendt (1999), Stacs Lecture Notes in Computer Science 1564 pp302–312.
> 1 votes

---
Tags: approximation, mathematical-programming
---


# Question
Title: Why is the complete state of a turing machine representable by a finite word?
At the moment I'm just reading through this article on the word problem for groups (https://projecteuclid.org/euclid.bams/1183548590), and I'm wondering about a certain snippet.

On page 40 the article describes a word that can encode the state of a turing machine, namely $S\_{k\_{u}}...S\_{k\_{1}}q\_{i}S\_{j\_{1}}...S\_{j\_{v}}$ where $S\_{k\_{u}}...S\_{k\_{1}}S\_{j\_{1}}...S\_{j\_{v}}$ is the tape expression, $q\_{i}$ is the current internal state of the turing machine, and $S\_{j\_{1}}$ is the currently scanned symbol.

I'm just wondering why this word is necessarily finite. Why can't the input of the turing machine have an infinite amount of non-zero characters?

# Answer
> I'm just wondering why this word is necessarily finite. Why can't the input of the turing machine have an infinite amount of non-zero characters?

No, it can not.

When the Turing machine starts, the tape contains the input (a finite-length word) followed by an infinite amount of blank symbols (often written as `#`). It is common to simply omit the trailing infinitely many blanks, and just represent a finite prefix instead, adding blanks as needed when the head moves right past the end of the tape.

When the machine runs, in each step it can at most (over-)write over *one* tape symbol, and move right by at most one position. This is an essential feature of any Turing machine.

Hence, after finitely many steps, we still have a finite amount of non-blank symbols. The tape again contains infinitely many trailing blanks (usually not represented), so it can be represented by a suitable finite prefix.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: How can the binary OR function be computed by a MOD3 gate of constant fan-in?
I've been working on a problem and in order to prove the bigger picture, I need to understand how a binary OR function can be computed by a constant fan-in MOD3 gate. I would seem that the output would need to depend on every input bit as just looking at some of them would leave out the possibility that those that weren't looked at could change the answer. Any help is appreciated.

# Answer
> 0 votes
> Well a MOD3 gate would output 1 iff the remainder after dividing the sum of the input bits by 3 is non-zero.

Well in this case an OR gate is simply a MOD3 gate with fan-in 2. Consider the truth table:

```
A  B  (A + B) % 3  OUT
0  0      0         0
0  1      1         1
1  0      1         1
1  1      2         1

```

---
Tags: arithmetic, circuits, binary
---


# Question
Title: Can a perfect matching always be found by a picking sequence?
There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference graph (encoding the "like" relation).

In some cases, this may be done using a *picking sequence*: order the people in a queue and let each person in turn pick a single item he likes. For example, suppose that:

* $A$ likes $\\{1,2\\}$
* $B$ likes $\\{2,3\\}$
* $C$ likes $\\{3\\}$

Then, $\langle C,B,A\rangle$ is a good picking sequence, since $C$ necessarily picks $3$, then $B$ picks $2$, then $A$ picks $1$ and we get a perfect matching. On the other hand, $\langle C,A,B\rangle$ is not a good picking sequence, since after $C$ picks $3$, it is possible that $A$ will pick $2$, and then $B$ will remain without an item.

So, my question is: If a perfect matching exists, can it always be found by a picking sequence?

# Answer
> 2 votes
Yes, it can. This can be proved by mathematical induction on $n$.

Denote by $U$ the set of people. For a subset of people $P$, denote by $N(P)$ the *neighborhood* of $P$, that is the set of items that at least one person in $P$ likes. By Hall's marriage theorem, $|P|\le |N(P)|$ for all $P$.

If $|P|\< |N(P)|$ for all $P\subsetneq U$, then we can let an arbitrary person pick first. After his picking, $N(P)$ is decreased by at most 1 for all $P$, so $|P|\le |N(P)|$ holds for all $P$ in the remaining graph. Therefore there is still a perfect matching in the remaining graph by Hall's marriage theorem, and there is a valid picking sequence by inductive assumption.

If there exists $P\subsetneq U$ such that $|P|=|N(P)|$, then there is a perfect matching in the subgraph induced by $P\cup N(P)$, and by inductive assumption there is a valid picking sequence for people in $P$ in this subgraph. We can apply this picking sequence in our orignial graph first, and the result is the same, that is, exactly all items in $N(P)$ are picked. Note there is still a perfect matching in the remaining graph, so we can again use the inductive assumption to complete the picking sequence.

# Answer
> 0 votes
Assuming that the order in which a person would pick is consistent IOW everyone will always pick 1 over 2. Then yes there is always an order in which the solution will come out: the picking sequence of the persons is the same as the order of the items they pick.

In your example ABC is also a good picking order, A will pick 1, B will pick 2 and C will pick 3.

---
Tags: graphs, discrete-mathematics, matching, bipartite-matching
---


# Question
Title: Is IEEE 754 float arithmetic associative, commutative, distributive, etc? Why?
Does the associative/commutative/distributive/etc property hold for arithmetic performed with IEEE 754 floats?

Obviously the answer is no to most of those questions, but do any of the properties of standard arithmetic hold? How can one formulate proofs (or at least proof-like statements) explaining why any particular property does or does not hold?

# Answer
> 5 votes
The IEEE 754 standard defines exactly how floating-point arithmetic is performed. For many interesting theorems, you will need to examine the exact definition. For some less interesting ones, like a+b = b+a or ab = ba, all you need to know that IEEE 754 always calculates the exact result, rounded in a deterministic way. For non-theorems, like (a+b)+c = a+(b+c), which is false, all you need is a counterexample which is usually easy to find.

# Answer
> -1 votes
Check e.g. Goldberg's "What every computer scientist should know about floating point". Heavy reading, but a must.

---
Tags: proof-techniques, arithmetic, floating-point
---


# Question
Title: Datastructure for insertion and scored extraction
I have a simple program (assume a shop) that is actually just returning the $m$ most active customers from a total list of $n$ users (so $m \leq n$). I only use this program on one machine with one process, so assume no distribution of data to be necessary.

I require a data structure storing $\mathrm{userId}$ and $\mathrm{score}$, where $\mathrm{score}$ is an unsigned integer. In the beginning it's $\mathrm{score}:=0$ for all $n$ users. I can `extract` $m$ users beginning with the highest $\mathrm{score}$ (filling up with any other user, so the first `extract` just returns any $m$ users).

I have an `increment(x)` function that is called often. It increases $\mathrm{score}$ of the user with $\mathrm{userId} = x$ by $1$. Afterwards I want to call `extract` again, where the result may differ by $1$ user (the last incremented score may lead to that $\mathrm{userId}$ replacing another $\mathrm{userId}$ within the $n$ members).

At the moment my prototype uses a hashmap for the scoring and a linear *min-search*, so complexity for `increment` is $O(1)$ and for `extract` is $O(n\cdot m)$. I feel like there should exist a data structure where `extract` is $O(m)$ (min-heap maybe?) while `increment` is either $O(\log n )$ or even $O(1)$. Assuming $m = \log n$, this would lead to a speedup of $n$ which would be immense even for small datasets.

What data structure should I use? Is there such a data structure for the operations `extract` and `increment(x)`? And if not, is there a theoretical proof that there is none?

# Answer
You can use left threaded AVL trees with score as key and hash (expected $\mathcal O(1)$ insert/delete or simple AVL, logarithmic but with value much smaller than $n$) as values to keep id's, and all the time keep the data sorted with $\mathcal O(1)$ inorder traversal and $\mathcal O(\log n)$ insert (which in case of your increment operation is one delete, one insert). Also you might want to keep the last result (which is sorted) to check whether some new id appeared and use binary search if it did.

Overall this gives $\mathcal O(m)$ extract (which cannot be better) and two $\mathcal O(\log n)$ operations per increment.
> 3 votes

# Answer
Since you're interested in the ordering of scores, use a data structure that's designed to store ordered values: a search tree. Balanced search trees have $O(\log(n))$ lookup and insertion for $n$ elements. In practical terms, there's little difference between $O(\log(n))$ and $O(1)$: for typical data sizes, the constant in front tends to matter more.

The search tree is indexed by scores. If you also need to look up users by their ID, keep multiple data structures that are updated together, e.g. a hash map from user IDs to user records as well as the search tree from scores to user records. Depending on whether you use mutable data structures and what else you have in the records, the search tree for scores may contain (pointers to) user records, or user IDs. To insert a user, add an entry to both the hash map and the score tree. To update a score, update the user record, remove the existing entry from the tree and add a new entry.

If you're changing the score by 1, its final position in the tree will often be close to the original, so this can be optimized a bit from a basic remove-then-add. This is only an optimization in some cases: in the worst case you'll need to rebalance the tree all the way to the root.

To extracting the $m$ users with the highest score, walk the tree in decreasing order, and stop when you've seen $m$ users. This takes $O(\log(n)+m)$ time ($\log(n)$ is the depth of the tree to reach the largest element, then walking the next elements takes $O(m)$ time).

There are several ways to deal with ties. Given your scenario, I'd expect it to be desirable to select users at random when there are ties. So in each tree node, store a set of user IDs, using a data structure that lets you extract a random $m$-element subset easily. This can be a balanced search tree where you can extract $m$ elements among $k$ with $m$ queries of cost $\log(k)$. Another possibility is a hash map implemented as an array of buckets where you read from random buckets, though this will have a bias related to how users fit in buckets.

If you want ties to be resolved in a deterministic way, (e.g. always select the older users), then use a search tree where each node contains a single user, indexed by (score, user rank) pairs (e.g. user rank = account creation date).
> 3 votes

# Answer
Here's the datastructure I have in mind:

The list stays being sorted by score.

* extracting the highest $m$ users goes through the end of the list, $O(m)$.
* incrementing a score of a user goes by looking up the list entry through the hashmap, and then moving the user to the next list entry if the next list entry is score+1, or inserting a new entry with score+1 otherwise. If the Set the user came from is then empty, that list entry is removed. The link for the user in the hashmap is updated to point to the new list entry. This all is expected time $O(1)$.
> 3 votes

---
Tags: data-structures
---


# Question
Title: Sort already sorted array - after changing several elements
**Problem**:

Given $S$ — a sorted array where some of the elements were randomly changed, assuming that you're provided with an $S\_1$ — an array of indexes of changed elements. Design an algorithm that will sort the array in $O(n)$ time.

Additionally, we know that $\text{length of }S\_1\le\log\_2(\text{length of }S)$.

**Example**:

$S$ — \[3, 5, 7, (20), 15 ,(0) ,16\]

$S\_1$ — \[3, 5\]

() - Changed elements

**Question**:

I have some troubles designing the algorithm. My first idea was to just use Count or Radix sort algorithm, but as the values which are changed can be random I've ruled out count sort as potential candidate.

The second idea is to:

1. Load the values based on indexes of $S\_1$ into new array $S\_x$.
2. Rewrite $S$ without the elements of indexes provided in $S\_1$.
3. Sort $S\_x$.
4. Use "Merge" procedure from Merge Sort on $S\_x$ and $S$.

However that still will leave me with $O(n\log n)$ as I'll need to sort $S\_x$ array. I'll appreciate any advice on the approach.

# Answer
> 2 votes
Note the length of $S\_1$ is no more than $\log\_2n$, so the time you need to sort $S\_x$ is $O(\log n\log\log n)$, which is $O(n)$.

# Answer
> 1 votes
If you are given the indices, it is trivial. Sort the indices. Remove the changed elements into a separate array and pack the first one together. Sort the changes elements and merge with the first array. All in O(n) as long as the number of changed elements is O(n / log n).

Much more difficult if you don’t know which elements are changed.

---
Tags: algorithms, data-structures, sorting, arrays
---


# Question
Title: What is the relationship/difference between best/worse/expected case and big O/omega/theta?
In the big O section of Cracking the Coding Interview 6th edition, I read the following.

`"Best, worse, and expected case describe the big O for expected inputs and scenarios."`

`"Big O, big omega, big theta describe the upper, lower and tighter bounds for the run-time."`

I understand what best, worse, and the expected case is describing.

I know what bounds are but still don't understand the decoupling of the two concepts. Why would an algorithm have different bounds if the inputs/scenarios are the same?

Thanks in advance!

# Answer
> 3 votes
> Why would an algorithm have different bounds if the inputs/scenarios are the same?

A deterministic algorithm has a single running time on each input. However, this is not what best case, worst case and average case are about. Let us consider a deterministic sorting algorithm. Its running time on an array of length $n$ depends on the array (and on the algorithm). The *best case running time* is the minimal running time of the algorithm on an array of length $n$. The *worst case running time* is the maximal running time of the algorithm on an array of length $n$. The *average case running time* with respect to a distribution on arrays of length $n$ is the average running time of the algorithm on an array chosen at random from the given distribution.

For a randomized algorithm, it makes sense to consider the best case, worst case and average case for a single input, but this is not what these terms usually refer to.

> "Best, worse, and expected case describe the big O for expected inputs and scenarios."

This is simply wrong. I have explained above the meaning of best case, worst case and average case running time for the particular case of sorting algorithms, and the general case is similar.

How is running time measured? One way to measure running time is via an experiment – choose an actual machine, code the algorithm in a particular way, and measure the running time. However, this approach is problematic – which machine should we run the code on? How should we implement the algorithm? Another problem that the exact formula for the running time might be very complicated, and so not very helpful.

The way out is to state the running time *up to a constant factor*. This makes sense since under reasonable assumptions, the exact machine used and the exact implementation only affect the running time by a constant factor. Moreover, this allows us to hide the complexities of the exact running time by sweeping them under the rug of asymptotic notation. (As an aside, we measure the running time on an *abstract* machine known as the RAM machine, which has unbounded memory. This allows us to make sense of arbitrary input sizes.)

Consequently, we always quote the running time in asymptotic notation. It is common to use big O notation, but this is in fact only an upper bound on the running time. Merge sort, for example, runs in time $O(n^5)$. It also runs in time $O(n\log n)$, and this upper bound is tight, in the sense that the worst case running time is $\Theta(n\log n)$. When quoting the running time as $O(f(n))$, what one usually means is that the worst case running time is $\Theta(f(n))$. The reason we use big O rather than big $\Theta$ is that on some inputs the algorithm may run faster, and so for arbitrary inputs it may not be correct that the running time is $\Theta(f(n))$, but it is always correct that the running time is upper-bounded by $O(f(n))$.

> "Big O, big omega, big theta describe the upper, lower and tighter bounds for the run-time."

Big O, big $\Omega$ and big $\Theta$ are general-purpose asymptotic notation. They can be used to express asymptotic estimates on the rate of growth of arbitrary functions. Even in computer science, it is common to use asymptotic notation not only to measure running time, but also to measure memory consumption; and in other fields asymptotic notation is used for functions not related to algorithms at all.

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


title: Concurrency and fairness

text:
# Question
Title: Concurrency and fairness
I'm studying the concurrency in programming and the atomic instructions. What i have not understood is the concept of "fairness" applied to this matter. Can you give me an hint ?

# Answer
Suppose you are running two concurrent processes (or threads), which both perform intensive disk I/O. Both repeatedly attempt to read/write on some file.

Now, the scheduler must decide which requests to handle. The scheduler could serve the first process, then the second on, then the first, etc. in a round-robin fashion. This would guarantee fairness: any process request is eventually served.

Suppose instead that the scheduler wants to maximize disk throughput. One way to do that is to move the disk head as little as possible. This can be done by serving the I/O request which operates on the closest file (roughly speaking) to where the head is found at the moment. Assume the first process only accesses file A, while the second process accesses only file B. If both continuously perform requests on their files, the only one of them will be served: e.g. if A is the first accessed file, B will never get accessed since keeping the disk head on A optimizes performance with respect to moving the head to file B. Hence, the second process will never get served, and will "starve". This scheduler is not fair.
> 1 votes

---
Tags: programming-languages, concurrency, multi-tasking
---


title: Resolution Algorithm - No new clauses

text:
# Question
Title: Resolution Algorithm - No new clauses
The standard resolution algorithm returns false if *no new clauses are added*.

I know that if $KB \land \neg a \implies \[\]$, it returns true by proof by contradiction, but how can I understand the false case intuitively?

# Answer
> 4 votes
When $new\subseteq clauses$ then, if we continued, the next line would be $clauses \leftarrow clauses\cup new$ but $clauses\cup new = clauses$ so we'd be doing the exact same calculation the next time through the loop deducing nothing new and looping forever.

The point is, if we "resolve" all pairs of clauses and deduce nothing new, then we've derived *all* the consequences from the original set of clauses. If we still haven't derived a contradiction at that point, then $\neg\alpha$ is consistent with $KB$ and thus $\alpha$ is not provable. This last isn't necessarily completely accurate either, as it only shows that $\alpha$ is not a *propositional* consequence of $KB$. For example, if $KB$ was $\forall x.P(x)$ and $\alpha$ was $P(t)$, then $\alpha$ is provable from $KB$ but not via propositional reasoning.

---
Tags: logic, artificial-intelligence, propositional-logic
---


# Question
Title: Average-case analysis of linear search given that the desired element appears $k$ times
The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array":

> Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A\[1\], A\[2\], \ldots, A\[n\]$, until either it finds $A\[i\] = x$ or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.
>
> Suppose that there are $k \ge 1$ indices $i$ such that $A\[i\] = x$. What is the average-time running time of this algorithm?

Let $X$ be a random variable denoting the number of comparisons.

$$ \begin{align\*} E(X) &= \sum\_{i=1}^{i=n-k+1} i \cdot \Pr(X = i) \\ &= \sum\_{i=1}^{i=n-k+1} i \cdot \left(\frac{n-k}{n} \cdot \frac{n-k-1}{n-1} \cdot \frac{n-k-2}{n-2} \cdot \cdots \cdot \frac{n-k-i+2}{n-i+2} \cdot \frac{k}{n-i+1}\right) \end{align\*} $$

How to evaluate this summation? Or is there a simple solution to this problem?

Note that when $k=1$, $E(X)$ is $\frac{n+1}{2}$. When $k=n$, $E(X)$ is $1$.

# Answer
> 3 votes
Note $$ \begin{align\*} E(X)&=\sum\_{i=1}^{n-k+1} i \cdot \Pr(X = i)\\ &=\sum\_{i=1}^{n-k+1} \sum\_{j=1}^i\Pr(X = i)\\ &=\sum\_{j=1}^{n-k+1} \sum\_{i=j}^{n-k+1}\Pr(X = i)\\ &=\sum\_{j=1}^{n-k+1} \Pr(X \ge j), \end{align\*} $$ and $X\ge j$ means all $x$ are distributed among $A\[j\],\ldots,A\[n\]$, so $$ \Pr(X \ge j)=\frac{\binom{n-j+1}{k}}{\binom{n}{k}}. $$ Therefore $$ E(X)=\sum\_{j=1}^{n-k+1} \frac{\binom{n-j+1}{k}}{\binom{n}{k}}=\frac{1}{\binom{n}{k}}\sum\_{r=k}^{n}\binom{r}{k}=\frac{1}{\binom{n}{k}}\binom{n+1}{k+1}=\frac{n+1}{k+1}. $$

---
Tags: algorithms, algorithm-analysis, search-algorithms, probability-theory, average-case
---


# Question
Title: What is the connection between combinatorial circuits and finite state automata?
The diagram on the Wikipedia page of FSA shows the hierarchy of the computational devices, in that diagram it is denoted that the finite state machines are superior to the combinatorial circuits.

Combinatorial circuits are the model of propositional logic i.e. both are equivalent, where we do a discussion about the truth values of variables and the logical connectives. Whereas the models beyond the FSA process the strings and decides the membership of a string with for some language.

If there is some connection between these two models then there must be some relation between propositional logic and regular/context-free/recursive languages.

How can we construct a corresponding FSA for a given combinatorial circuit?

# Answer
> 5 votes
You can associate with a combinatorial circuit with $n$ inputs and a single output the language consisting of the $n$-bit strings on which the circuit outputs $1$. This language is finite and so, in particular, regular. This is not particularly enlightening, however.

Combinatorial circuits have a fixed number of inputs. In contrast, finite automata get as input a word of unbounded length. The goals of circuits and automata are thus rather different – circuits attempt to solve a finite problem efficiently, whereas automata attempt to solve an infinite problem. Every finite problem can be computed by some circuit, and so the challenge is to come up with a small circuit that computes it. In contrast, not all infinite problems can be solved by a given type of automata.

The more interesting relation between circuits and automata is that of *translation*. Given a language $L$ of binary words, let us denote by $L\_n$ its restriction to inputs of length $n$. A well-known result is the following:

> If $L$ can be solved in polynomial time, then there is a polynomial $p(n)$ so that for every $n$, the finite language $L\_n$ can be computed by a circuit of size $p(n)$.

Therefore one way to show that $L$ cannot be solved in polynomial time is to show that the finite languages $L\_n$ cannot be computed by polynomial size circuits.

The circuits produced by the translation alluded to above are related to each other, in the sense that they can all be generated by a program which on input $n$ outputs the circuit $C\_n$ for the fragment $L\_n$. Such a family of circuits is known as a *uniform* family of circuits. When comparing the strength of circuits and automata, the correct comparison is between uniform families of circuits and automata. For example, we can strengthen the result above to an equivalence:

> A language is in polynomial time iff its finite restrictions can be computed by a uniform family of polynomial size circuits.

Thus uniform polynomial size circuits have exactly the same power as polynomial time computation. Uniform circuits often appear in practice – a good example is circuits for doing arithmetic, from whose structure their uniformity is apparent. Non-uniform circuits – ones which cannot be produced uniformly – can have unlimited power. For example, non-uniform circuits can solve the halting problem in its unary formulation, $$\\{ 1^n : \text{ the $n$th Turing machine halts on the empty tape} \\}.$$

Nevertheless, it is believed that even non-uniform polynomial size circuits cannot solve NP-hard problems, a conjecture known as $\mathsf{NP} \neq \mathsf{P/poly}$. At some point in time this looked like a promising avenue for proving $\mathsf{P} \neq \mathsf{NP}$, though at the moment this point of view seems naive.

---
Tags: automata, finite-automata, propositional-logic
---


# Question
Title: Data structure with init $O(n)$ and interval max $O(\log n)$
I need to find a data structure that supports the following operations:

* init(A): gets an array of size $n$ of different numbers and builds the data structure - should be $O(n)$.
* max(i,j): gets two indexes $i\<j$ and returns the maximum value between these two cells, that is, $A\[i\],A\[i+1\],\dots,A\[j\]$ - should be $O(\log n)$.

It should be a tree related data structure.

# Answer
> 2 votes
Assume for simplicity that $n$ is a power of 2. Construct a complete binary tree in which the vertices at depth $k$ correspond to subarrays of length $n/2^k$, and contain as auxiliary information the maximum element of the subarray.

This data structure can be initialized in $O(n)$, and it supports your type of range queries in $O(\log n)$. You can also update the data structure by modifying arbitrarily a single element of the array in $O(\log n)$.

Details left to you.

---
Tags: data-structures
---


# Question
Title: inclusion and concatenation of languages
so for a homework assignment i need to prove the following:

We have arbitrary languages `L1⊆∑1*, L2⊆∑2*, L3⊆∑3*, L4⊆∑4*`

Prove that the followging is either true or false:

`If L1 ∪ L2 ⊆ L3 ∩ L4, then L1◦L2 ⊆ L3◦L4` (◦ = concatenation)

Now i know this is true, but i don't know how to approach this problem...

Any tips on pointing me into the right direction are appreciated!

# Answer
The assignment tests basic definitions (and some elementary set theory).

As you know, for arbitrary $L\_1,L\_2$, you have $L\_1\cdot L\_2 = \\{ x\cdot y \mid x\in L\_1, y\in L\_2\\}$.

Now if $L\_1\subseteq L\_3$ and $L\_2\subseteq L\_4$ then $L\_1\cdot L\_2 \subseteq L\_3\cdot L\_4$. This is rather clear, or if you want, can shown with elementary steps. Take any $z\in L\_1\cdot L\_2$, then $z=xy$ for $x\in L\_1$ and $y\in L\_2$. However, because of the inclusions, $z=xy$ for $x\in L\_3$ and $y\in L\_4$, thus $z\in L\_3 \cdot L\_4$.
> 1 votes

---
Tags: formal-languages, sets
---


title: Approximation factor for graph problems

text:
# Question
Title: Approximation factor for graph problems
I am attempting to figure out how to use approximation factors to determine the answers an algorithm can return for graph problems.

For example, if a graph G actually has a maximum clique with 13 vertices, and we use a 1.5-approximation algorithm to approximate the maximum clique - what is the minimum size clique that can be returned by this algorithm?

My first thought was to simply divide 13 / 1.5 since this would represent the worst that the algorithm could do. However, since that is ~ 8.6, would the minimum the algorithm returns be 9 or 8?

# Answer
> 1 votes
An approximation algorithm for a maximization algorithm has an approximation ratio of $\alpha \geq 1$ if whenever the true answer is $m$, the algorithm is promised to return a solution with value at least $m/\alpha$.

In your case, $m = 13$ and $\alpha = 1.5$, and so by definition, the algorithm must return a clique whose size is at least $13/1.5$. Since the size of the clique is an integer, if a clique is of size at least $13/1.5 \approx 8.6$, then it is in fact at least $\underline{\quad}$ (fill in the blanks).

---
Tags: graphs, approximation
---


# Question
Title: The optimal way to find leaves in a weighted full binary tree
Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e *w*(v, v.right) = *a* while *w*(v, v.left) = *b*

How do I find optimal paths to all leaves from the root. I don't think classical graph traversals are helpful in this context as I don't need to visit all nodes.

# Answer
Hint: How many paths are there from a given leaf to the root?
> 1 votes

---
Tags: algorithms, optimization, trees, search-algorithms, binary-trees
---


title: Simulate $n$-PDA with $n-1$-PDA

text:
# Question
Title: Simulate $n$-PDA with $n-1$-PDA
I've heard that every $n$-PDA when $n \> 2$ is as powerful as $2$-PDA. Unfortunately every proof I'm able to find uses references to Turing Machines, which I haven't learned about yet. I'm sure there must exist an alternative proof, supposedly one that converts $n$-PDA to $n-1$-PDA, and then proceeds by induction, but I'm unable to find it. Any references, or hints are greatly appreciated.

What I tried: to simulate two stacks using just one, therefore going from $n$ to $n-1$. But it would also mean that $2$-PDA are as powerful as $1$-PDA, so it's clearly a wrong way.

# Answer
> 3 votes
Yes, any PDA with $n\>2$ stacks can be simulated by a pda with $2$ stacks. It is possible to show this without explicitly using Turing machines.

Assume that you have $n$ stacks, with contents $\alpha\_1$ to $\alpha\_n$. Store all these stacks on top of each other, with special separator symbols $\square\_i$. So a single stack contains $\square\_1\alpha\_1 \dots \square\_n\alpha\_n$ (top left). Now assume that I want to perform an operation on stack $k$ (look at the top, check it is empty, push or pop symbols). In order to do this use the second stack. Move all stacks up to the $k$th to the second stack (popping from the one pushing to the other). The two stacks are now $\square\_1\alpha\_1 \dots \square\_k\alpha\_k$ and $\alpha^R\_n\square\_n\dots \alpha^R\_{k+1}\square\_{k+1}$. it is now easy to operate on stack $k$ (since it is on top of one of the stacks). and in general we continue moving the $n$ stacks around between the two stacks to continue the simulation.

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


# Question
Title: How does the processing happen in a CPU when it uses Virtual Memory?
I am just trying to visualize how computers work with Virtual Memory/Address.

Assume there is a program on the disk that looks like this:

`a b c d e f g h i j k l m n o p` where the `a .. p` are instructions and their address is from `0` to `15`.

What happens inside the CPU while executing this program? Assume that the operating system uses `pages` of `8 bytes`.

To begin with, my understanding is that the operating system loads the program into physical memory in page-sized chunks and creates a mapping to the `pages` of the program numbered from 0..n which looks like:

```
# assume it is in reverse in the real memory (16-31)!

[i j k l m n o p] [a b c d e f g h]

# cpu's view of the program

  page1 (24-31)     page2 (16-31)
[a b c d e f g h] [i j k l m n o p]
 |
 PC

```
1. Depending on the program size, `program-size/page-size` `page`'s will be created. So here it would be `16B/8B = 2` pages numbered as page1 and page2.
2. Now, the Program Counter (PC) would be set to the Virtual Address of `a` which is `0` and the CPU will somehow resolve it and load the corresponding instruction from the real physical address of `a` which is `24` here.
3. But wait, how did CPU know that it has to look up into a certain page map, `page1` in this case? The operating system knows that but how does the CPU know that? Is it something like the Virtual Address of a program corresponds to one and only one page map and that can be determined directly from the Virtual Address itself? For example, `0x00` automatically means to lookup in `page1`, `0x08` means to lookup in `page2`. Divide by 8 and look into the `page{quotient}` with the remainder indicating the offset to look into the real memory?
4. Suppose there is an instruction `d` that refers to the memory corresponding to `o` which is in `page2`, how will that be resolved? Is it using the same principle? If you know the Virtual Address, then you know the place to look up for the real address?
5. Now, when there are multiple programs how do we uniquely determine what is `page1`? Could another program have a `page1` as well? Is it like page maps are unique (which I think is complex because I thought it has to be sequential and starting from 1 so that given a Virtual Address you can calculate the page map + offset) or is there a per process Page Table managed by the Operating System?
6. Suppose we finished executing the instruction `h`, the PC would automatically load the Virtual Address of `i`, which gets automatically resolved to `page2` using the same above principle?

# Answer
Virtual memory is handled just in the part of the CPU that handles reading and writing memory.

At some point, the CPU has calculated a memory address and has decided to read or write memory at that location. If there is no virtual memory used, then the memory address is the actual address in the physical memory connected to the CPU. With virtual memory, the memory access part of the CPU will first translate the virtual memory address to a real memory address.
> 1 votes

# Answer
Your first step might be with two of the following books: Design Unix Operating System or Design Implementation FreeBSD Operating System.

Also this https://en.wikipedia.org/wiki/Virtual\_memory and this http://www.cs.jhu.edu/~phi/csf/slides/lecture-virtual-memory.pdf will help.
> 0 votes

---
Tags: cpu, virtual-memory
---


title: Peterson algorithm for mutual exclusion

text:
# Question
Title: Peterson algorithm for mutual exclusion
In the Peterson Algorithm for mutual exclusion an implicit assumption is that the operations with the shared global variables happen **atomically**.

To me, this is not a superficial assumption , cause it's another mutual exclusion issue . In which way we make the operations with the shared global variables happen **atomically** ?

# Answer
> 1 votes
The Peterson Algorithm uses only memory read and memory write operations, which are atomic in almost every computer ever built. (All the bits in a word are read or written on the same cycle, and the memory bus of the computer is built in such a way that only one of the processors has access on any specific cycle.)

That said, the atomicity of the write operations is *not* necessary. Leslie Lamport is quite clear about this in his commentary on his web page about his classic "Bakery Algorithm" for mutual exclusion (http://lamport.azurewebsites.net/pubs/pubs.html#bakery):

> Several books have included emasculated versions of the algorithm in which reading and writing are atomic operations, and called those versions "the bakery algorithm". I find that deplorable. There's nothing wrong with publishing a simplified version, as long as it's called a simplified version.
>
> What is significant about the bakery algorithm is that it implements mutual exclusion *without relying on any lower-level mutual exclusion*. Assuming that reads and writes of a memory location are atomic actions, as previous mutual exclusion algorithms had done, is tantamount to assuming mutually exclusive access to the location. So a mutual exclusion algorithm that assumes atomic reads and writes is assuming lower-level mutual exclusion. Such an algorithm cannot really be said to solve the mutual exclusion problem. Before the bakery algorithm, people believed that the mutual exclusion problem was unsolvable--that you could implement mutual exclusion only by using lower-level mutual exclusion. Brinch Hansen said exactly this in a 1972 paper. Many people apparently still believe it.

(emphasis added)

For more details about this aspect of the problem see Lamport's 1991 paper, "The Mutual Exclusion Problem Has Been Solved," http://lamport.azurewebsites.net/pubs/pubs.html#lamport-mutual-solved.

---
Tags: algorithms, operating-systems, mutual-exclusion
---


# Question
Title: E-Unification: “Goal seeking” pattern matching between directed trees
## Preamble

Suppose we have some symbols `x`, `y`, ... and wildcards `(ξ)`, `(ζ)`, ... which have any meaning. Wildcards are said to ‘match’ any symbol: *wildcard `(ξ)` matches symbol `x` under the mapping `{(ξ): x}`*. Now suppose we can construct directed trees from these symbols and wildcards. The notion of matching should extend to these trees, like this:

```
  x                 x
 / \               / \
a   y   matches  (ξ)  y   under the mapping {(ξ): a, (ζ): b}.
   / \               / \
  z   b             z  (ζ)

```

It is easy to implement an algorithm which takes two trees like those above and gives the necessary mapping. (Does it have a name?)

I want to introduce certain ‘equivalence relations’ `<n>` between trees. For instance, if I wanted to capture the notion of the symbol `f` being commutative and associative, I could write:

```
       f         f
<1>:  / \   =   / \     # commutativity f(ξ, ζ) = f(ζ, ξ)
    (ξ) (ζ)   (ζ) (ξ)

        f         f
       / \       / \
<2>:  f  (χ) = (ξ)  f   # associativity f(f(ξ, ζ), χ) = f(ξ, f(ζ, ξ))
     / \           / \
   (ξ) (ζ)       (ζ) (χ)

```

This is where things get interesting, because I now want to implement a more intelligent matching algorithm which, given a set of equivalence relations like those above, is able to perform ‘indirect’ matches like this:

```
  f                          f
 / \  (indirectly) matches  / \  under the mapping {(ξ): x}...
y   x                     (ξ)  y

                f  <1>  f                            f
   ...because  / \  =  / \  which directly matches  / \ .
              y   x   x   y                       (ξ)  y

```

## Question

How would one go about finding an algorithm which is able to transform a given tree (via given rules) so that it ‘matches’ another tree?

Is there a name for this kind of problem?

---

## More examples

Matches aren’t always unique. Ideally, the algorithm should be able to find all of them.

```
   f                 f
  / \               / \
 x   f   matches   f  (ξ)  under {(ξ): y, (ζ): z} or {(ξ): z, (ζ): y}...
    / \           / \
   y   z        (ζ)  x

         ...using rules <1> and <2>.

```

*A quintessential demonstrative example:*

For brevity, define the symbols `1`, `2`, `3`, ... in terms of `0` and a unary symbol `s`:

```
1 = s(0), 2 = s(s(0)), 3 = s(s(s(0)))...

```

Now, define two transformation rules `s(n) = +(n, 1)` and `s(+(n, m)) = +(n, s(m))`:

```
       +      s
<1>:  / \  =  |
    (n)  1   (n)

     s       +
<2>: |  =   / \
     +    (n)  s
    / \        |
  (n)  (m)    (m)

```

Check this out:

```
            +
5 matches  / \  under {(ξ): 2}, because...
          3  (ξ)
                     <1>          <2>
...5 = s(4) = s(s(3)) = s(+(3, 1)) = +(3, s(1)) = +(3, 2) which matches 5 with {(ξ): 2}.

   (as trees:)
       s   s  <1>  s  <2>   +       +                  +
...5 = | = |   =   |   =   / \  =  / \  which matches / \  with {(ξ): 2}.
       4   s       +      3   s   3   2              3  (ξ)
           |      / \         |
           3     3   1        1

```

---

(I apologise for the size of this question. I don’t have a background, so feel free to improve this post.)

Perhaps you can direct me to some reading, or set me off in the right direction? Thanks heaps!

# Answer
This is called unification. There is a one-to-one correspondence between terms and trees; the tree is the parse tree of a corresponding term. It sounds like you want the most general unifier. There are standard algorithms for solving this. However, this doesn't handle equivalence relations like commutativity or associativity. E-unification might be what you are looking for.
> 3 votes

---
Tags: algorithms, trees, unification
---


# Question
Title: Big Oh notation for a function with two inputs of linear growth
I'm quite new to time-complexity analysis so I might have misunderstood some basic concepts but lets say we have the following function:

```
    function(int x, int y)
    for (int i = 0; i < x; i++)
    {}

    for(int i = 0; i < y; i++)
    {}

```

From my understanding this function will for large inputs of $x$ and $y$ have two loops of linear growth. If the first loop is said to run $k$ times and the second $m$ times, will the big Oh notation be $O(k + m)$, or can the two inputs be merged into one variable of linear growth, like $n$, $O(n)$? Can $k$ and $m$, since they both have the same growth rate and (in the case of Big Oh analysis) equally large inputs be simplified into one variable or should they stay separate?

# Answer
> 2 votes
There is a common misconception that the running time always have to depend on a single parameter. This misconception is strange since in graph theory, the running time of many algorithms is stated in terms of two parameters, the number of vertices and the number of edges. As an example, DFS and BFS run in time $\Theta(V+E)$. A priori, we do not know of any relation between $V$ and $E$ other than $E \leq \binom{V}{2}$, and so $\Theta(V+E)$ cannot be simplified further. Since $E = O(V^2)$, any algorithm running in time $O(V+E)$ also runs in time $O(V^2)$. If we know that the graph is connected then $E \geq V-1$, and so $\Theta(V+E)$ is the same as $\Theta(E)$. But for general graphs, we have no reason to assume any relation between $V$ and $E$.

In your case, you seem to want to assume that $k$ and $m$ have the same order of growth. This might be the case or might not be the case, depending on the application you have in mind. Only you can tell. It is possible to state the upper bound $O(k+m)$ in terms of a single variable: it is $O(n)$, where $n = \max(k,m)$ (or $n = k+m$). Whether this is helpful or not is up to you.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, loops
---


# Question
Title: shortest notation for "set of all maps from $A$ to $B$"?
I usually write the following:

$$\\{m| m:A\to B\\}$$

Is there a more succint notation?

# Answer
The standard notation is $B^A$.
> 4 votes

# Answer
$A \to B$ is a common notation for the set of functions. For instance

$$ \begin{array}{l} f : (A\to B)\times A \to B \\ f(g,x) = g(x) \end{array} $$
> 3 votes

---
Tags: notation
---


# Question
Title: What is the relationship between minimum vertex cover and minimum clique cover
**Question: What is the relationship between minimum vertex cover of a graph G and minimum clique cover of conflict graph of G?**

**Thanks!**

I believe the minimum vertex cover of G is equivalent to minimum clique cover of the conflict graph of G, or their sizes are equal, but today I find a ***counterexample***.

***Example***: in the figure below, a minimum vertex cover is {1, 2}, but the minimum clique cover contains one partition, that is vertext set {$e\_1, e\_2, e\_3$}. The size of minimum vertex cover is 2, while the size of minimum clique cover is 1.

A **graph** is an ordered pair G = (V, E) comprising a set V of vertices, nodes or points together with a set E of edges, arcs or lines, which are 2-element subsets of V (i.e., an edge is associated with two vertices, and the association takes the form of the unordered pair of the vertices).

A **vertex cover** of a graph G is a set S of vertices of G such that every edge of G has at least one of member of S as an endpoint.

A **minimum vertex cover** is a vertex cover having the smallest possible number of vertices for a given graph.

A **conflict graph** is the graph G = (V, E) where every edge in E is represented by a vertex. Two vertices are adjacent if and only if the edges in E these vertices correspond to intersect each other.

A **clique cover** or partition into cliques of a graph is a partition of the vertices of the graph into cliques, subsets of vertices within which every two vertices are adjacent. A **minimum clique cover** is a clique cover that uses as few cliques as possible.

# Answer
The minimum clique cover of the conflict graph is at most the minimum vertex cover of the original graph. In other words, if the original graph has a vertex cover of size $k$, then the conflict graph has a clique cover of size $k$. This is essentially because all edges adjacent to a vertex in the original graph constitute a clique in the conflict graph (though as the example of the triangle shows, there are also other cliques in the conflict graph). Details left to you.
> 2 votes

---
Tags: graphs
---


# Question
Title: What's the problem of using the clock to generate random numbers?
If the clock shows 14:15:36.909302, why not just use the fractions of a second part (09302) as a kind of random number?

What is wrong with this form of generating random numbers?

I am aware that obtaining truly random numbers is a difficult task, so I am assuming that there is something wrong with this method.

# Answer
> 8 votes
Quick answer:

1. If the run time of your algorithm to pick a random number is not random you could get a pattern of times which is not random.

As an example. Suppose the function to read the time is triggered by an event, and the event is timed to the clock, now your functions based on the clock.
2. If the run time of your algorithm is faster than the precision of the clock, then you will get duplicate times and thus duplicate numbers which are not random.

As an example. You write a function for use by others, and someone decides to generate 10,000 random numbers and store them. The loop is so tight for reading the clock and saving the values that you get 10,000 numbers all identical.

These are just cases that can make the data non-random. In reality if it is not security related I run a large sample through a test for randomness and if it were reasonable I would use it, but if it is security related I would ask at Security or Crypto

# Answer
> -2 votes
If you use a clock to generate a number for a roulette machine then every hour you will have 3600 seconds to use as your seed number,multiply this seed number by the same fixed number every second and you will produce a different number every second. If you make the fixed number the date then every day you will get a different sequence of numbers,even better,if you started with pi at the very beginning then the very last 4 digits could be your fixed number as pi never repeats a sequence? The number generated would be the last digit of the equation,as long as it is between Zero and 37,if it outside this range it gets disguarded and the next number used,if there are a few numbers in succession that fall outside our scale then this is when you get repeat numbers or zero!!! Any thoughts?

---
Tags: randomness, random-number-generator
---


# Question
Title: A* 8-puzzle problem worst case memory usage
We are testing the A\* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem. We have to answer the following question but I can't figure out what it should be.

Our assignment is derived from this.

> How many board positions are in worst case in memory in function of board size N (where N is the side of a board of size NxN). Give a as low as possible upper bound. You can assume that a board configuration is never in the priority queue several times.

I was thinking about N^2! but that is impossible because not every board position can be reached.

# Answer
Since the number of possible positions is quite low when N = 3 (9! / 2 = 181,400), you can do an exhaustive search to find the worst case. Check the result, and maybe it leads to some insight.
> 0 votes

---
Tags: graphs, algorithm-analysis, searching, space-analysis
---


# Question
Title: What is the only condition that would cause the Insert operation of a dynamic data structure to return a “data structure full” error?
I want to know where can I find some resources on this question, because, after researching for a day and half, I couldn't find information specific to my question. Can anyone help me answer my question? I know that dynamic data structures (such as linked lists) can expand the amount of nodes at runtime, but if that's the case, how could it ever return a "full error" message if has an unlimited amount of storage to get keep holding nodes inside of it?

# Answer
I think this belongs more to StackOverflow than here.

As for your question, *nothing* in reality is unlimited. Computers have finite memory, finite storage. Words have a fixed (usually 32 or 64-bit) length, which might overflow. Or there might be some other engineering decision that limits the size of these data structures. Unlimited anything only exist in textbooks.
> 2 votes

# Answer
In addition to the previous answer by John Doe:

There's one more reason: "Dynamic" does not always mean "infinitely variable in size". A good example would be Q-Heaps by M. Fredman and D. E. Willard, which can only store up to $\mathcal{O}(w^{1\over 4})$ numbers when running on a $w$-bit system.
> 0 votes

# Answer
There are of course other reasons why a "data structure full" error code be returned. Three obvious possibilities are plain old bugs in the software, incorrect assumptions (like "users will never add a record over 100 KB to this list, so if they try it's a bug and we return 'data structure full'") and limitations in the software (like a 32 bit counter that mustn't overflow, which causes "data structure full" to be reported even when running on a 128 GB machine where there is plenty of memory still available).
> 0 votes

---
Tags: data-structures, dynamic-programming, linked-lists
---


title: Recurrence relation T(n) = 3T(n-1) + n

text:
# Question
Title: Recurrence relation T(n) = 3T(n-1) + n
I'm trying to solve the recurrence relation T(n) = 3T(n-1) + n and I think the answer is O(n^3) because each new node spawns three child nodes in the recurrence tree. Is this correct? And, in terms of the recurrence tree, is there a more mathematical way to approach it?

# Answer
> 1 votes
Using the substitution method, we find out that $$ \begin{align\*} T(n) &= n + 3T(n-1) \\ &= n + 3(n-1) + 3^2T(n-2) \\ &= n + 3(n-1) + 3^2(n-2) + 3^3T(n-3) \\ &= \cdots \\ &= n + 3(n-1) + 3^2(n-2) + \cdots + 3^{n-1}(n-(n-1)) + 3^n T(0) \\ &= \frac{3^{n+1}-2n-3}{4} + 3^nT(0) \\ &= \Theta(3^n). \end{align\*} $$ Even without doing the full calculation it is not hard to check that $T(n) \geq 3^{n-1} + 3^n T(0)$, and so $T(n) = \Omega(3^n)$. A cheap way to obtain the corresponding upper bound is by considering $S(n) = T(n)/3^n$, which satisfies the recurrence relation $S(n) = S(n-1) + n/3^n$. Repeated substitution then gives $$ \frac{T(n)}{3^n} =\sum\_{m=1}^n \frac{m}{3^m} + T(0). $$ Since the infinite series $\sum\_{m=1}^\infty \frac{m}{3^m}$ converges, this implies that $\frac{T(n)}{3^n} = \Theta(1)$ and so $T(n) = \Theta(3^n)$.

---
Tags: recurrence-relation
---


title: PCA with Bishop's book

text:
# Question
Title: PCA with Bishop's book
I am reading PCA in Bishop's Pattern Recognition and Machine Learning pg. 562, here in Lagrange multiplier but I don't get it in the highlighted: I wonder is it $u\_1$ or $u^T\_1$?

Your help is appreciated!

# Answer
> 3 votes
You should take the *gradient* of the function, that is, the vector of partial derivatives with respect to all coordinates of $\mathbf{u}\_1$, and equate it to the zero vector. Let us suppose that the individual coordinates of $\mathbf{u}\_1$ are $u\_1^1,\ldots,u\_1^n$, so that (12.4) reads $$ \sum\_{i=1}^n \sum\_{j=1}^n S\_{ij} u\_1^i u\_1^j + \lambda\_1 \left(1 - \sum\_{i=1}^n (u\_1^i)^2\right). $$ The derivative with respect to $u\_1^t$ is $$ \sum\_{i=1}^n (S\_{it} + S\_{ti}) u\_1^i - 2\lambda\_1 u\_1^t = 2 (\mathbf{S} \mathbf{u}\_1)\_t - 2\lambda\_1 u\_1^t, $$ since $S$ is symmetric. The gradient is thus $$ \nabla (12.4) = 2\mathbf{S} \mathbf{u}\_1 - 2\lambda\_1\mathbf{u}\_1. $$ Equating it to zero, we obtain the condition $\mathbf{S} \mathbf{u}\_1 = \lambda\_1 \mathbf{u}\_1$, that is, $\mathbf{u}\_1$ is an eigenvector of $\mathbf{S}$ corresponding to the eigenvalue $\lambda\_1$.

---
Tags: mathematical-programming
---


# Question
Title: How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?
I am trying to find the frame check sequence in cyclic redundancy check(CRC). Given that the generator polynomial is $\ g(x)= (x+1)(x^3 + x^2 + 1)$. Let's say the data sequence is $\ 10110001$.

In this case, $\ g(x) = x^4+x^3+x+x^3+x^2+1 $ after multiplying. But how do I handle 2 $\ x^3 $ terms? Is it okay to convert it into binary without worrying about it? For example, $\ 1 1111$ and continue with the division?

# Answer
> 2 votes
When computing CRC, we are working over the field of two elements. In this field, 2=0. Therefore $$ (x+1)(x^3+x^2+1) = x^4+x^2+x+1. $$

---
Tags: error-correcting-codes, polynomials, crc
---


# Question
Title: Complexity of Verification for Clique with Adjacency Matrix
I am having trouble getting my head around what the complexity of the verification step for the CLIQUE problem would be -- specifically if an adjacency matrix is used. I know in general the complexity for this problem would be `O(k^2) * edges in G.`

This is the specific question I am attempting to solve: Select the correct complexity of the verification step for CLIQUE problem. Assume that the candidate solution is size k, and that the Graph with n vertices is represented by an adjacency matrix (i.e., constant time edge lookups).

My thoughts: If there are k vertices in the candidate solution, I will need to iterate `k` times. For each of those vertices I will need to check that corresponding row in the adjacency matrix to see if the sum of that row is `k - 1.` in other words checking to see if the `deg(k)` for each `k` is `k-1`.

Should I consider that `k^2`? Or would it be `(k^2 * n)` since I would need to add 1 for each of the n vertices on that row to find out if the row sum is `k-1`?

# Answer
> 2 votes
Here is an algorithm for verifying that the clique $C\[1\],\ldots,C\[k\]$ is contained in the graph whose adjacency matrix is $A$:

```
for i from 1 to k:
   for j from 1 to i-1:
      if A[i,j] = "no edge", then return "No"
return "Yes"

```

What is the running time of this algorithm?

---
Tags: complexity-theory, graphs
---


# Question
Title: If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?
I am confused interpreting the statement of this question:

"If L is a regular language then also is the language $L1 = \\{ w \in L | w \in L^R \\}$?"

Should the symbol "|" (such as) be understood as an logical and?

The language L1, so, would be $ L \cap L^R $ - a subset of L?

Or should the symbol "|" be understood as an logical or?

The language L1, so, would be $ L \cup L^R $?

In both cases it is regular (I believe), since the languages $L$ and $L^R$ are regular, and the union or intersection will be also regular.

Am I understanding this right?

# Answer
> 3 votes
The notation $L\_1 = \\{ w \in L \mid w \in L^R \\}$ means "the collection of all $w \in L$ that satisfy the condition $w \in L^R$". In other words, $L\_1 = L \cap L^R$.

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


# Question
Title: Can we define the Functor Category in Haskell (or any other language with a more expressive type system)?
Here I am talking about the Functor category, which is defined as a category whose objects are functors and morphisms are natural transformations.

For reference: https://ncatlab.org/nlab/show/functor+category

I was wondering if it is possible to define this in Haskell.

If we define category like this:

```
class Category cat where
   id :: cat a a
   (.) :: cat b c -> cat a b -> cat a c

```

Now how do we define `Functor` as an instance of this, given that `Functor` is itself a typeclass?

## EDIT

I am not tied to the above definition of a Category. I see Edward Kmett represents a `Category` like this:

```
newtype Yoneda (p :: i -> i -> *) (a :: i) (b :: i) = Op { getOp :: p b a }

type family Op (p :: i -> i -> *) :: i -> i -> * where
  Op (Yoneda p) = p
  Op p = Yoneda p

class Vacuous (a :: i)
instance Vacuous a

class Category (p :: i -> i -> *) where
  type Ob p :: i -> Constraint
  type Ob p = Vacuous

  id :: Ob p a => p a a
  (.) :: p b c -> p a b -> p a c

```

I am not looking for Haskell specific implementation, but in any functional language in general.

# Answer
Ed Kmett has actually defined this in his Hask library. The trick is to define a natural transformation as a data type and encoding the functors that this natural transformations map, in the type level like this:

```
class (Functor f, Dom f ~ p, Cod f ~ q) => FunctorOf p q f
instance (Functor f, Dom f ~ p, Cod f ~ q) => FunctorOf p q f

data Nat (p :: i -> i -> *) (q :: j -> j -> *) (f :: i -> j) (g :: i -> j) where
  Nat :: ( FunctorOf p q f
         , FunctorOf p q g
         ) => {
           runNat :: forall a. Ob p a => q (f a) (g a)
         } -> Nat p q f g

```

Now he defines the Natural transformation as instances of a Category like this:

```
instance (Category' p, Category' q) => Category' (Nat p q) where
   type Ob (Nat p q) = FunctorOf p q
   id = Nat id1 where
     id1 :: forall f x. (Functor f, Dom f ~ p, Cod f ~ q, Ob p x) => q (f x) (f x)
     id1 = id \\ (ob :: Ob p x :- Ob q (f x))
   observe Nat{} = Dict
   Nat f . Nat g = Nat (f . g)
   unop = getOp

```

All of this can be found here: https://github.com/ekmett/hask/blob/master/src/Hask/Category.hs
> 0 votes

---
Tags: functional-programming, category-theory, haskell
---


# Question
Title: Is there a formal difference between $f:X \to X$ and $f\in X \to X$?
We can denote by $X\to X$ the set of all functions from $X$ to $X$. Therefore, we can use the following statement to say that $f$ is a function from $X$ to $X$: $$f\in X\to X$$

But we usually state instead

$$f:X \to X$$

In fact, we could say that $X\to X$ is defined as $\\{f| f:X\to X\\}$. If I'm not mistaken, $:$ is a notation that belongs to type theory, rather than set theory as $\in$ does.

**So is there a fundamental difference between these two notations? Does it make sense to say that one of the two is more "fundamental" than the other?**

# Answer
No, they're mostly notational variations. There are different connotations to the different notations, and different notations are common in different fields where they can mean quite different things. Also, sometimes they are used in a particular context for different (but usually related) things. You'll, of course, have to see how it has been defined in that context.

Any use of $\in$ usually strongly suggests a set-theoretic context (though you occasionally see it in a type-theoretic context). The $f:X\to Y$ notation was, I believe, popularized in mathematics by category theory. In this case, it means $f\in\mathsf{Hom}(X,Y)$. This is compatible with $f\in Y^X$ in the case that the category is the category of sets and functions. In a general categorical context, $Y^X$ is usually reserved for exponential objects for which it makes no sense to ask if $f\in Y^X$, though you (usually) can ask if there is an arrow $1 \to Y^X$.

In logic, when $X$ and $Y$ are sorts, usually $f:X\to Y$ means that $f$ is a function symbol. In this case, $X$ and $Y$ aren't sets and neither is $X \to Y$. It makes no sense to say $f\in X\to Y$ unless $\in$ isn't being thought of as set membership or we want to say $X\to Y$ means the set of function symbols from $X$ to $Y$. This latter view starts to get rather similar to the categorical view.

In type theory, usually $f:X\to Y$ means something like $f$ has type $X\to Y$ and $X\to Y$ is the type of functions from $X$ to $Y$. Types are not sets and part of the purpose of this notation is to remind one of that fact. Indeed, types are more like sorts and this notation is similar to how it is used in logic. Sometimes $Y^X$ is also used where $Y^X$ is used in a more first-class sense in a way that is compatible with the similar distinction I mentioned for category theory, so we might write $X\to Z^Y$ rather than $X\to(Y\to Z)$. Sometimes no distinction is being made and the notation is completely synonymous and the choice is made purely for typographical reasons. For computer programming, the choice is mostly typographical, `f : X -> Y` is easier to write and easier to read, though programming languages are also closely related to type theories.

It doesn't really make sense to talk about which of these notations is "more fundamental" than the others in general. That said, the $f:X\to Y$ notation is usually making the least commitments if multiple notations are in use. Often $f:X\to Y$ isn't a proposition with a truth value, so it wouldn't make much sense to write $\\{f\mid f:X\to Y\\}$. Admittedly, in the context where it isn't a proposition, you usually aren't using set theory. If you really wanted to, you could meta-theoretically write $\\{t\mid \cdot\vdash t:X\to Y\\}$ to mean the set of closed terms of type $X\to Y$, say. This would have nothing to do with a set of functions though.
> 8 votes

---
Tags: type-theory, sets, notation
---


# Question
Title: Perturbing a Markov chain to be closer to a target stationary distribution
Suppose we are a given a Markov chain $A\_0 \in \mathbb{R}^{n \times n}$ and a desired stationary probability vector $\pi\_0 \in \mathbb{R}^n$. I would like to find a Markov chain that is as close as possible to $A\_0$ and whose stationary probability is as close as possible to $\pi\_0$. For example, I would like to solve

$$ \min\_{{\rm stochastic}~ A} ||A-A\_0||\_F + ||\pi(A)-\pi\_0||\_2$$

Is this doable in polynomial time? For example, for any fixed $\epsilon \> 0$, can I find something $\epsilon$-close to the optimal solution in time polynomial in $n$? If not, what sort of approximation guarantees can we obtain for this?

I am pretty flexible on the problem statement; ultimately, the solution will be validated based on performance on a particular application. So if the problem is solvable by replacing the $2$- and Frobenius norms with something else, or via formalizing the problem in some other way, that would also be perfect.

# Answer
> 2 votes
You could use gradient descent. It is possible to compute the gradient of the objective function $\varphi(A)$ in terms of $A$, i.e., the derivative of the objective function with respect to each entry of the matrix $A$. Then you could apply gradient descent.

In particular, let $\varphi(A) = \\|A-A\_0\\|\_F + \\|\pi(A) - \pi\_0\\|\_2$ denote your objective function. Applying gradient descent to this objective function requires us to be able to compute $\nabla \varphi(A)$, i.e., the derivative ${\partial \over \partial A\_{ij}} \varphi(A)$ of the objective function with respect to each individual entry $A\_{ij}$ of the matrix $A$. Let me explain how to do that.

One approach is to approximate the gradient numerically, i.e., to compute the gradient $\nabla \varphi(A)$, perturb each element of $A$ by a small amount of measure how much $\varphi(A)$ changes. This might be fast enough if the matrix dimensions are sufficiently small, and it has the benefit of being easy to code. However, it will scale poorly in practice for large matrices, as we need to compute $n^2$ perturbations for each gradient, and each perturbation requires computing the stationary distribution of a perturbed matrix, which naively takes $O(n^3)$ time, for a total of $O(n^5)$ time per gradient. Thus each iteration of gradient descent will take $O(n^5)$ time, and you need to do many iterations of gradient descent, so this might take a while. (You can speed this up by computing the stationary distribution of the perturbed matrix using a few iterations of the power method, initialized with the stationary distribution of $A$; this takes $O(n^2)$ time; but it's still $O(n^4)$ time per iteration of gradient descent.)

A better way is to find an explicit, symbolic formula for the gradient $\nabla \varphi(A)$, and then use that with gradient descent. That is possible but it gets messy, so I'll explain the details below.

It remains to handle the constraint that $A$ must be stochastic. There are multiple ways to do that:

* One way is to use projected gradient descent: in each iteration you update $A$ in the direction indicated by the gradient, then project the resulting matrix to the nearest stochastic matrix ($A' = A - \gamma \nabla \varphi(A)$, then let $A''$ be the stochastic matrix nearest to $A'$ and replace $A$ with $A''$).
* Another way is to adjust the objective function, letting $\varphi'(A) = \varphi(A) + c \cdot p(A)$ where $p(A)$ is a penalty term that measures how badly $A$ fails to be stochastic (a simple choice might be $p(A) = \sum\_i |(\sum\_j A\_{ij}) - 1|^2 + \sum\_{i,j} \min(a,0)^2$), then choose $c$ sufficiently large and apply gradient descent to minimize $\varphi'(A)$. For instance, you could perform several rounds of gradient descent, where the solution from the previous round is the initial value for next round, and where you double $c$ after each round.

There may be other ways as well.

OK. That's an overview of the approach that I am proposing. On to explaining how to compute the gradient symbolically, as promised.

# An explicit formula for the gradient

We can write the objective function in the form $\varphi(A) = \varphi\_1(A) + \varphi\_2(A)$ where $\varphi\_1(A) = \\|A-A\_0\\|\_F$ and $\varphi\_2(A) = \\|\pi(A) - \pi\_0\\|\_2$. It's easy to compute $\nabla \varphi\_1(A)$; it is simply

$$\nabla \varphi\_1(A) = {1 \over \\|A-A\_0\\|\_F} (A - A\_0).$$

Computing $\nabla \varphi\_2(A)$ is more difficult, as this requires us to compute the gradient of the stationary distribution $\pi(A)$ as a function of $A$. Since the stationary distribution $\pi(A)$ is the principal eigenvector of $A$ (when it is unique), this reduces to computing the gradient of the principal eigenvector of $A$ as a function of $A$, for which there are techniques available. In particular, we have

$$\nabla \varphi\_2(A) = {1 \over \\|\pi(A) - \pi\_0|\_2} \sum\_k (\pi\_k(A) - {\pi\_0}\_k) \\; \nabla \pi\_k(A),$$

and we need to find an expression for $\nabla \pi\_k(A)$, where $\pi\_k(A) = \pi(A)\_k$ is the $k$th element of $\pi(A)$, and $\nabla \pi\_k(A)$ is the gradient of that with respect to the entries of $A$.

Fortunately, there are nice formulas for how to compute the gradient of the eigenvector of a matrix. In particular,

$$\nabla \pi\_k(A) = (\text{Id} - A^\top)^\dagger b\_k \pi(A)^\top,$$

where $b\_k$ is the $k$th basis vector (1 in the $k$th entry and 0 elsewhere), and $\dagger$ indicates the Moore-Penrose pseudo inverse. (Here I have used that the stationary distribution $\pi(A)$ is the eigenvector that corresponds to eigenvalue 1.) Plugging in, we find that

$$\nabla \varphi\_2(A) = {1 \over \\|\pi(A) - \pi\_0|\_2} (\pi(A) - \pi\_0)^\top (\text{Id} - A^\top)^\dagger \pi(A)^\top.$$

This then gives a symbolic expression for $\nabla \varphi(A) = \nabla \varphi\_1(A) + \nabla \varphi\_2(A)$.

---
Tags: algorithms, markov-chains
---


title: Why use a CFG instead of a DFG

text:
# Question
Title: Why use a CFG instead of a DFG
I just realized a Control-Flow Graph (CFG) is composed of *basic blocks*, which is a *set* of instructions. It is mentioned that you can still do stuff like dead code elimination and whatnot, with the CFG, but that seems like you'd be reaching into the basic block to figure that out. At that point you are dealing with *individual instructions*. But that's the domain of Data-Flow Graphs (DFG). Data-Flow Graphs are made of connections between individual instructions.

My question is, why not just always deal with individual instructions instead of the basic blocks. It seems like in the end you are using individual instructions anyways. Wondering the advantages a CFG has over a DFG, and vice versa.

# Answer
> 4 votes
A control-flow graph serves a different purpose than a data-flow graph. They aren't alternatives. A control-flow graph represents the flow of control: which instruction can follow another. A data-flow graph represents the flow of data: which instruction can read data that was created by another.

Perhaps you mean to ask why each vertex in a control-flow graph represents a basic block (a group of instructions) rather than a single instruction. That's an optimization. You *could* have each vertex represent a single instruction, but often you'll have a long sequence of consecutive instructions with no control-flow transfer, and they all have the same properties, so it is natural to collapse them into a single vertex. Also subsequent program analyses may be faster with this optimization; see Why is it better to do the data flow analysis in the basic blocks.

---
Tags: compilers, data-flow-analysis
---


# Question
Title: How to Construct a Lattice from Program Statements
In order to optimize a program, I am trying to figure out how the idea of a *lattice* applies to data-flow graphs, as introduced by this presentation (first diagram below). The lattice seems to take a program, order its inputs and outputs, and allow for easily determining flow of variables and state, so you can perform verification and optimization. But I am not sure how to construct the lattice from the program statements.

In this question I would like to know how to construct the lattice from the program.

Specifically, given a program such as this:

```
var x = 10
var y = 20
var z = 0
var i = z
while (i < x) {
  y = y + x * i
  i = i + 1
  z = y + i
}

```

We can construct a Control-Flow Graph (CFG) where each node is a program statement such as `var x = 10`. From that we can construct a Data-Flow Graph (DFG) where we are keeping track of how a variable is used. This creates an *def-use ordering*, along the lines of:

```
x, y, i at the same time
z comes after i
...

```

That's where I start getting lost. But once we have a partial ordering, somehow a *lattice* is created. Finally from the lattice, we can do things such as doing *pointer analysis* (Figure 2) and *computing fix-points* (Figure 3). That will help in optimization and verification of the program.

I'm wondering only the first part, **how to construct the lattice from the example program above**. Wondering what is needed to construct the lattice at a high-level. I understand the upper and lower bounds of a lattice, which seems to correspond to CFG inputs and outputs being joined, but I don't quite see how to actually do the join (meet), what the nodes/vertices are in the lattice (not sure if it's a single program statement, a variable, or what), and what the edges are in the lattice. Once that is defined, then doing the rest of the stuff should be straightforward. Thank you for your help.

---

^- Figure (1).

---

^- Figure (2).

---

^- Figure (3).

# Answer
> 1 votes
There is no such thing as a "DataFlow Graph lattice". Those are two separate things. A data flow graph is a graph that represents how data flows in a program, which can be helpful in data flow analysis. A lattice is a mathematical object that can be helpful for data flow analysis.

Data flow analysis is a broad subject. There are many techniques for data flow analysis (many use lattices, but it's not a hard requirement). They don't all use lattices in the same way. So, there's no one way to do the conversion you are referring to.

To learn more about the subject, I suggest reading a good textbook on program analysis.

---
Tags: lattices, data-flow-analysis
---


title: Maximal Win Score Distribution

text:
# Question
Title: Maximal Win Score Distribution
For the problem I'm considering, I'm looking at a sport (it's baseball) where:

* Two teams play a game against each other, head to head.
* Each team has a finite, integer score (called "Runs") at the end of the game; this value is \>= 0.
* Games **cannot** end in a tie. We can assume the algorithm will not have to handle input with tie games.

Given as input, a list of Games with the following data:

* Game ID (usually a number, or date on which game was played)
* Final number of runs scored by "our" team - hereafter RS (Runs Scored)
* Final number of runs scored by "opponent" team - hereafter RA (Runs Allowed)

And given these terms:

* A "Win" is defined as RS \> RA.
* A "Loss" is defined as RA \> RS.
* Note: Due to the impossibility of tie games, every game will either be a Win or a Loss for "our" team.

My goal is to design an algorithm that will redistribute whole RS values from one game to another until a maximum number of possible Wins is found for our team. A single game's RS value can be substituted for another game's RS value, but the algorithm **cannot** take "partial" amounts of RS from one game and distribute them among multiple games.

In the process of "donating" game **A**'s RS (in its entirety) to another game **B**, you must then decide:

* Which *other* game **C** should donate its RS to game **A**?
* Which *other* game **D** should receive the *original* RS from game **B**?

In intuitive terms, the goal is to distribute the scores so that games are won by the narrrowest of margins, and lost by the widest of margins.

The algorithm **cannot stop** until every game meets one of the following conditions:

* The game has neither *donated* nor *received* another game's RS (the game's original score stands *as-is*.)
* The game has *received* an RS value from another game; it is the *only* game that has received that game's RS value; it has *donated* its RS value to another game; and that recipient is the *only* game to have received this game's original RS.
    + In other words, every original RS value must be used for exactly one game.

Additional descriptions of how the algorithm should work:

* **Input bounds:** The algorithm should run in a reasonable amount of real time on modern computers for data sets up to 162 games. There's no need to be able to handle more games than that with any sort of reasonable performance. Basically, it needs to run in a human scale of time. An hour is fine; a week is stretching it. Anything longer is just too long.
* "Equivalent" or "redundant" donations should be detected and avoided. In other words, if a given exchange of RS does not improve the overall number of wins of the team, then the exchange should not have occurred. Examples: Avoid exchanging RS when the "from" and "to" RS values are equal. Also avoid exchanging RS when it just makes one game go from a loss to a win, but another game to go from a win to a loss.
* If there are multiple equivalent solutions to the problem (e.g., due to duplicate RA/RS pairs across several games) that have the same number of substitutions and wins, we'll just choose one arbitrarily. There's no value to the *order* of the wins or losses in the list.
* An algorithm with analogous rules but shuffling around RA would probably work too, but I arbitrarily chose shuffling RS.

Here is some sample data:

* Game 1: RS 3, RA 4 (L)
* Game 2: RS 9, RA 1 (W)
* Game 3: RS 6, RA 7 (L)
* Game 4: RS 2, RA 1 (W)
* Game 5: RS 0, RA 2 (L)
* Game 6: RS 8, RA 10 (L)
* Game 7: RS 3, RA 8 (L)

Wins: 2. Losses: 5.

One way to use the available RS values to maximize wins is:

* Game 1 \<- Game 3. RS 6, RA 4 (W)
* Game 2 \<- Game 7. RS 3, RA 1 (W)
* Game 3 \<- Game 6. RS 8, RA 7 (W)
* Game 4 unchanged. RS 2, RA 1 (W)
* Game 5 \<- Game 1. RS 3, RA 2 (W)
* Game 6 \<- Game 5. RS 0, RA 10 (L)
* Game 7 \<- Game 2. RS 9, RA 8 (W)

Wins: 6. Losses: 1.

**What I think is the hard part:** There may be several solutions that have the same win/loss record, but we want the one that involves **the greatest number of "unchanged" games** out of all possible solutions with the same (maximal) win/loss record. This is basically what I mean by avoiding needless juggling around of RS.

A few observations about the dynamic of the scores that may or may not need to be in the algorithm's logic:

* Sometimes you *do* want to donate a score from a winning game. In the example, we sent the 9 RS from Game 2 to Game 7, causing us to win Game 7, 9 to 8. Then the 3 RS from Game 7 were enough to win Game 2, 3 to 1.
* If you do not even *have* an RS value large enough to exceed a given RA, you probably want to take the *lowest* available RS and tack it to that game, because you can't win no matter what. In our example, we took the 0 RS from Game 5 game and put them in Game 6, then sent Game 6's original 8 RS to Game 3 to convert Game 3 from a loss to a win.
* There is no requirement that the RS have to be **swapped**. In the example, Game 3 gets its new RS from Game 6, but Game 6 gets its new RS from Game 5. Then Game 5 gets from Game 1, and Game 1 gets from Game 3. This completes the "cycle" in a sense: now we have a *cyclic* digraph. That's the "end state". If it's acyclic (excepting nodes that are unchanged from their original score), our algorithm is wrong.

I've been hacking on this for a few hours here. I'm leaving the code up in a static, usable state with correct input data and string parsing, but the algorithm that builds the results is most certainly deficient in a number of ways, not the least of which is the unnecessary substitutions.

**Questions**

* I'm looking for a way to analyze/frame this problem more clearly so that it's easy to understand how to implement it.
* Is this just an analogue of another mathematically-equivalent problem with a textbook solution? If so, elaborate.
* What are the best data structures to set up the problem and organize the data? I've looked at lists, stacks, and digraphs so far, but I haven't found any clear winner yet. I even thought about recursion and using *two* lists (one for "donors" and one for "orphaned games" needing an RS) at one point, but I wasn't able to figure out what to do in all situations.
* When looking for the "best" (fewest number of substitutions) solution, is it possible to *efficiently* find this solution, or do you have to compute every possible solution set with the maximum wins and then calculate which one has the minimum substitutions?

# Answer
> 1 votes
The usual rule here is to ask one question per post. I'll explain how to formalize this problem and suggest an efficient algorithm for solving the problem. Here is a formalization of the problem:

Given: arrays $A\[1..n\]$, $B\[1..n\]$
Goal: find a permutation of $A$, call it $A'$, that maximizes the number of indices $i$ such that $A'\[i\] \> B\[i\]$.

This can be viewed as an instance of bipartite matching, a problem which has efficient algorithms. In particular, draw a bipartite graph with an edge from vertex $i$ to vertex $j$ if $A\[i\] \> B\[j\]$. Now the maximum matching in this graph corresponds to a permutation of $A$ that yields the maximum number of wins. Thus you can use standard algorithms for bipartite matching, e.g., Hopcroft-Karp.

Alternatively, I think you can use a greedy algorithm. Sort the arrays $A$ and $B$ into decreasing order. Look at the first element of $A$, namely $A\[1\]$. If $A\[1\] \> B\[1\]$, then match up $A\[1\]$ and $B\[1\]$ and discard both $A\[1\]$ and $B\[1\]$, and continue (next comparing $A\[2\]$ to $B\[2\]$). Otherwise, discard $B\[1\]$ and continue (next comparing $A\[1\]$ to $B\[2\]$). This involves an iterative scan through the sorted arrays. I think this should yield an optimal solution, and it is much easier to implement and more efficient too.

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


# Question
Title: Has the problem of finding the most profitable transactions given a set of discrete time series been well-studied?
# Overview and Problem Description

Suppose I have a set of *N* discrete time-series (represented as a map from time-interval-index to value/utility), and I would like to identify a sequence of actions in a particular time interval that would yield the highest profit at the end of the interval (assuming there is a transaction cost *T* associated with selling your holdings in a given time series). Problem Inputs include (i) transaction cost (volume-independent fixed cost) , (ii) price tables of alternatives (indexed by time step), and the (iii) time interval in question. Problem Output is a sequence of tuples `(timestep, decision type)` that maximizes returns at the end of the interval. Valid decisions include buying and selling ones funds from one alternative to another at discrete time steps.

# Trivial Example

You have USD 1 in year 1 **\[Problem Input\]**. Given Stocks A and B prices in years 1, 2, and 3, determine the sequence of actions that will maximize your profit at the end of the interval \[1, 3\]. The transaction cost, independently of volume, is USD1 **\[Problem Input\]**. You can sell and buy into any time series by paying the transaction cost for the trade at any discrete time step.

Stock A **\[Problem Input\]**:
Year 1: USD 1
Year 2: USD 1.1
Year 3: USD 1.2

Stock B **\[Problem Input\]**:
Year 1: USD 1
Year 2: USD 1.2
Year 3: USD 0.9

Answer **\[Problem Output\]**: Buy Stock A in year 1.

Buying Stock B for the first year would result in a higher return from the stock itself. However, given the USD 1 transaction cost, it's better to hold Stock A.

# Question

I have a feeling this problem is well-studied. I can see how it would have a lot of applications, even though one usually does not have perfect information.

If I'm correct about my hunch, what is this problem called?

Of course you could just formulate this as an integer program, but I'm looking for a solution approach that's less 'naive' (if that even exists).

# Answer
This can be solved using dynamic programming. Note that the optimal solution never requires holding more than one type of stock at a time; if you sell a stock, then you might as well sell all of it, and before buying a stock you should sell all existing stock. This enables a nice solution using dynamic programming.

Here are the details. Let $A\[i,s\]$ denote the maximum value of your assets that can be achieved by the end of year $i$, denominated in dollars, if you are holding stock $s$ at the end of year. Then there is a simple recursive expression for $A\[i,s\]$ in terms of the values of the form $A\[i-1,t\]$, based on the idea that either you sell or buy at the start of year $i$:

$$\begin{align\*} A\[i,s\] = \max(&A\[i-1,s\] V\[i,s\]/V\[i-1,s\],\\ &\max \\{(A\[i-1,t\]/V\[i-1,t\] - C) V\[i,s\] : t \ne s\\}), \end{align\*}$$

where $V\[i,s\]$ denotes the price/value of stock $s$ at the end of year $i$ and $C$ denotes the fixed transaction cost. Now you can compute these values iteratively, by first computing $A\[1,\cdot\]$, then $A\[2,\cdot\]$, and so on. You can also keep track of which choice was optimal at each step and thereby reconstruct the sequence of transactions as well if you like.
> 0 votes

---
Tags: algorithms, optimization, hash-tables
---


# Question
Title: Why are CFLs not closed under intersection?
I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that CFLs are not closed under intersection.

# Answer
> 24 votes
Let us assume $2$ CFLs $L\_1$ and $L\_2$ and their corresponding grammars be $S\_1$ and $S\_2$ respectively. It is very straightforward to see that the union of the two, represented by the new grammar as

$$S \to S\_1 \mid S\_2$$

is also a CFG, as the rule of being context-free is still not violated. Context-free grammar

But to prove that they are not closed under intersection, I'll provide an example.

Let $L\_1$ and $L\_2$ respectively be:

$$L\_1 = \\{ a^nb^nc^m \mid n, m \ge 0 \\}$$

$$L\_2 = \\{ a^mb^nc^n \mid n, m \ge 0 \\}.$$

It is not hard to see that $L\_1 \cap L\_2$ is

$$L = \\{ a^nb^nc^n \mid n, m \ge 0 \\},$$

which is not CFL (No PDA cannot accept that language).

Hope this explains.

# Answer
> 9 votes
Complementing the counterexample in the other answer, let me also what mentions when you try to construct a machine accepting the intersection of two context-free languages. Recall that a context-free language can be accepted by a pushdown automaton. Hence we can try to simulate two pushdown automata operating simultaneously. Since each PDA requires a stack, altogether we need to use two stacks. However, using two stacks we can simulate a Turing machine (exercise), so in general two stacks cannot be implemented in a single stack. Now it might be the case that in this particular case this reduction in the number of stacks is possible, but this hope is shattered by the example given by Akash Mahapatra.

Similar considerations apply for the *quotient* of two context-free languages $L\_1/L\_2 = \\{ x \in \Sigma^\* : \exists y \in L\_2 \\, xy \in L\_1 \\}$. In this case one can show that *every r.e. language can be represented as the quotient of two context-free languages*. Hence this particular way of using two stacks is as general as possible. The same doesn’t hold for intersection, since the intersection of any (finite) number of context-free languages is always recursive, indeed belongs to the much smaller class LOGCFL.

---
Tags: formal-languages, computability, context-free
---