# Question
Title: Given a set of points, find the one closest to a given point
So, I'm given an arbitrary set of points $(p\_1, p\_2, p\_3,\ldots)$ with an $x$ and $y$ coordinate. I have no information about the order they're given to me.

I need to write code that will take in a point, $p\_0$, and will find the point $(p\_1, p\_2, p\_3\ldots)$ closet to $p\_0$. This will of course be found my minimizing $R$ in $R^2 = (x - x\_0)^2 + (y - y\_0)^2$.

I could implement this easily if I linearly search the list of points each time (always $O(n)$ complexity). However, I would prefer something that could be an average of $\log(n)$ complexity. Does anyone have a suggestion on a search algorithm?

# Answer
> 2 votes
If we make no assumptions on input and want an exact answer to the question what the minimum distance is to $p\_0$, any algorithm must take at least $\Omega(n)$ time in the worst case. To see this, suppose $p\_0$ is in your input points. In the worst case, the final point we see in our list is this point! So we must inspect all our input points and hence take $\Omega(n)$ time.

For the same reason, an approximation algorithm must also use $\Omega(n)$ time, as the difference in distance to $p\_0$ between the inspected points in the list and the points we haven't inspected yet may be arbitrarily large.

The only way I see to be faster than linear is to take a random sample from your list to get the right answer with a certain probability. However, I think the running time would heavily depend on the probability you would want in the list.

---
Tags: computational-geometry, search-algorithms
---


title: How to show potential pipeline hazards

text:
# Question
Title: How to show potential pipeline hazards
Based on following table, I have to show if there is any potential pipeline hazard in the following code segments:

1. `X = R2 + Y
R4 = R2 + X`
2. `R1 = R2 + X
X = R3 + Y
Z = R1 + X`

I've been a bit stuck in the problem involving instruction pipelining.

Any strategy about where to start according to the table?

# Answer
> 1 votes
A data hazard occurs whenever you access a register after updating it. Due to the pipeline structure updating the register happens **after** it is being accessed by the successive instruction. That is, when accessed, the register holds the old value rather than the updated value.

For instance:

```
1. R2 = R1 + 1    // update R2
2. R3 = R2 + X    // access R2

```

Instruction 1 updates R2 at S4 (see the table). Instruction 2 reads R2 at S2. But at this time the new value of R2 is not stored yet -- it will be stored only on the next clock. This problem is the hazard.

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


# Question
Title: Traveling salesman problem with disconnected cities / infinite length edge
I am looking to solve a variant of the traveling salesman problem with a certain set of constraints:

* the graph is not complete, i.e. some nodes are not connected to each other
* the weight of an edge between any pair of connected nodes is always 1

What is the best way to model and solve this problem?

AFAIK the Concorde TSP solver, for example, requires real numbers for edge weights. And it seems like because all the edges have the same weight, there could be more than one valid solution.

# Answer
You're just trying to find Hamiltonian cycles in unweighted graphs. That's still **NP**-complete.

If you want to do it with a TSP solver, do it as follows. Suppose you have a graph on $n$ vertices. These are your $n$ cities. If there's an edge between two vertices, set the distance between the corresponding cities to $1$. If there's no edge, set the distance to $2$. If a minimum-weight TSP solution has total weight $n$, it's a Hamiltonian cycle of the original graph; if it has weight $n+1$ or more, then every cycle that visits all cities must include at least one non-edge of the graph, so the graph has no Hamiltonian cycle.
> 3 votes

---
Tags: traveling-salesman
---


# Question
Title: Can we find size of total interval in O(N)
Let's say we have given $N$ intervals in the form $\[x, y\]$, both $x,y$ are integers , we want to find the number of integers covered by at least one interval of all $N$ intervals, (look in the example for better understand).

The intervals may or may not intersect.

Example: Let N = 3, and the intervals: $a\_1 = \[1, 5\], a\_2 = \[3, 7\], a\_3=\[5,7\]$ The count of the integers is 7, because they cover the numbers: $1,2,3,4,5,6,7$

Is it possible to get such size in $O(N)$ time complexity

I tried to come up with solution but I think that we should sort the intervals in some way and then to search them in linear time, but I cannot think how should we make the search and how to sort them.

# Answer
There is a simple $O(n\log n)$ algorithm based on sorting all the endpoints of the intervals. I will describe a more sophisticated algorithm, which outputs the union of the input intervals as a union of *internally disjoint* intervals (they may have overlapping endpoints). Denote the input intervals by $\[s\_i,t\_i\]$.

* Initialize a variable $a$ to 0. This variable counts the number of active intervals.
* Let $x$ go over the sorted order of the $s\_i,t\_i$:
* + If $x = s\_i$ and $a = 0$, record $s\_i$ as the starting point $s$ of the current interval.
* + If $x = s\_i$ (regardless of $a$), increase $a$ by one.
* + If $x = t\_i$, decrease $a$ by one. If now $a = 0$, output $\[s,x\]$.

It is not hard to modify this algorithm to output a union of truly disjoint intervals.

This algorithm runs in $O(n\log n)$, the running time being dominated by the cost of sorting the endpoints of the intervals. If the endpoints are integers and we can only access them using comparisons, then there is a simple $\Omega(n\log n)$ lower bound obtained by reduction from element uniqueness. Given a list of integers $x\_1,\ldots,x\_n$, form intervals $\[3x\_i,3x\_i+1\]$; I'll let you take it from here. This might look like cheating (since we assume that the endpoints are integers, and use arithmetic operations in the reduction), but it does rule out certain kinds of algorithms from achieving $o(n\log n)$ performance.
> 4 votes

---
Tags: intervals
---


# Question
Title: Inequality over the entropy of an integer-valued random variable
I stumbled upon this inequality over a course on Information Theory :

> If $Z\in\mathbb{N}$ with finite mean, then $H(Z) \leq E(Z)\times h(\frac 1 {E(Z)})$ where $h$ is the binary entropy function

I have been trying to prove it using the log-sum inequality :

> $ \sum\_i a\_i \log \frac {a\_i}{b\_i} \geq (\sum\_i a\_i) \log \frac {\sum\_i a\_i}{\sum\_i b\_i} $ for $a\_i, b\_i$ non-negative numbers

Using, for example, $a\_i = P(Z=i)$ and $b\_i = iP(Z=i)$. But I couldn't really get throught it.

Part of my problem with this inequality is that I don't understand it : where does this use of the binary entropy function come from ? Even the relation between entropy and the mean seems unnatural to me.

# Answer
> 2 votes
Man, that's a nasty inequality.

Anyways, given a certain expectation $E\[Z\]=\mu$, it is known that the distribution that maximizes $H(Z)$ while keeping $E\[Z\]=\mu$ is the the Geometric Distribution with parameter $p=1/\mu$.

Then, it is easy to check that the inequality is satisfied (in fact the equality holds). Indeed, if $Z\sim Geo(p)$ then $E\[Z\]=1/p$ and $H(Z)=-\log p -\frac{1-p}{p}\log(1-p)$. Since this distribution maximizes $H(Z)$, any other distribution with the same expectation will have a lower left-hand side, while the right-hand side won't change (since $E\[Z\]=\mu$ didn't change). This proves the claim.

---
Tags: discrete-mathematics, information-theory, statistics
---


title: DAG Hamiltonian Path NP-complete

text:
# Question
Title: DAG Hamiltonian Path NP-complete
The book computers and Intractability mentions that Hamiltonian Path problem is not NP-complete in DAG. But if Hamiltonian Cycle is NP-complete in digraph then I can split a vertex and create two vertices ${s,t}$ which will make the graph acyclic and then ask for $s\rightarrow t$ hamiltonian path in that DAG. These two problems are equivalent. Then why is one NP-complete and other is not ?

# Answer
> 1 votes
Your proposed approach doesn't work. For some directed graphs there is no single vertex you can split to turn it into a DAG. An algorithm only qualifies as a solution to the Hamiltonian Cycle problem if it solves the problem for all graphs. It's not enough to solve the problem for a subset of "easy" graphs.

---
Tags: np-complete, hamiltonian-path, dag
---


# Question
Title: Conceptual overview: Self-information, Mutual information, uncertainty, entropy
I would like to have a compact conceptual explanation that allows me to gain some feeling with the concepts. The following list uses $x\_i, y\_i$ as events of experiments $X, Y$.

* Self-information, denoted as $I(x\_i)$
* Mutual information, denoted as $I(x\_i; y\_i)$
* Uncertainty (which is closely related to self-information and/or mutual information, I believe).
* Average mutual information, denoted as $I(X, Y)$.
* Entropy, denoted as $H(X)$, which is average self-information, I believe.

Next, there are a couple of "conditional ..." defined.

Can you sketch a compact overview of these concepts and how they relate, all intuitively?

# Answer
Trying to answer the question myself, with my textbook at hand. So far, I am here:

* **Self-information of an event**: uncertainty of an event.
$$I(x\_i) = \log \frac{1}{P(x\_i)} = -\log P(x\_i)$$ Self information of a vector event: $$I(x\_i y\_i) = -\log P(x\_i,~y\_i)$$
* **Mutual information between two events**: the information one event (experiment outcome) gives us about the other event: $$I(x\_i;y\_i) = \log \frac{P(x\_i,~y\_i)}{P(x\_i) P(y\_i)}$$ $$I(x\_i y\_i) = I(x\_i) + I(y\_i) - I(x\_i; y\_i)$$
* **Uncertainty**: the formula of it is the same as self-information of an event. So I'll assume they are the same.
* **Average mutual information**: The information one gives about the other when observer the former. Clumsy notation: $$I(X; Y) = E\[I(x\_i; y\_i)\]$$
* **Entropy**: the average amount of information that is revealed by observing an event. (I know the relationship to Huffman coding here.) Clumsy notation:
$$H(X) = E\[I(x\_i)\]$$
* **Conditional entropy**: the amount of information (about $X$) that is left to be discovered after observing the given ($Y$). $$H(X|Y) = H(X) - I(Y;Y)$$

\begin{align} I(X; Y) &= H(X) - H(X | Y) \\ \text{mutual} &= \text{a priori} - \text{a posteriori} \end{align}

* **Conditional self-information**: the information that is contained within the outcome of a certain event ($x\_i$), after already knowing the outcome of another event ($y\_i$). $$I(x\_i | y\_i) = -\log P(x\_i | y\_i)$$ Relations: $$I(x\_i | y\_i) = I(x\_i) - I(x\_i; y\_i)$$ \begin{align} I(x\_i; y\_i) &= I(x\_i) - I(x\_i | y\_i) \\ \text{mutual} &= \text{a priori} - \text{a posteriori} \end{align}
> 3 votes

# Answer
conditional self information is the modified version of self information in which we see the amount of information carried out by X(i) in the presence of Y(i)

```
                      I[x(i)|y(i)]=  -log[x(i)|y(i)]

```
> -1 votes

---
Tags: information-theory
---


# Question
Title: Is integer factorization reducible to subset sum?
Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm?

We assume that we know the algorithm solving the problem of Subset Sum with complexity: $n ^ 4 \cdot m ^ 4$ (for example), where $n$ is the number of elements in the set, and $m$ is the size of the largest element (absolute value).

Theoretically, we can perform a reduction from FACT to 3SAT and from 3SAT to Subset Sum.

However, the reduction from 3SAT to Subset Sum has a problem.

After such a reduction (from 3SAT), the numbers in Subset Sum are very large.

For example, let's see page number four in this **document**.

The search number is: $11133$ for a logic function composed of only three variables and two clauses.

The number we are looking for is always around $ 10 ^ {v + c} $ where $v$ is number of variables and $c$ is number of clauses.

We can solve the Subset Sum in time $n ^ 4 \cdot m ^ 4$ but if $m$ grows exponentially, then the whole grows exponentially.

Is there any way to solve this?

---- Update:

I found this **answer**. It directs me to the conclusion that there is no classic decimal notation. Maybe this is some unary notation? Do I presume well? I am concerned, however, about the value of "3" in $k$ (the last row in the table on the fourth page in document). How can we encode it in decimal / binary form?

# Answer
> 6 votes
Yes, such a reduction exists. Subset Sum is NP-complete. FACT is in NP. Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum.

To find such a reduction explicitly, work through the proof of NP-completeness for Subset Sum; it will describe such a reduction. (Implicitly, we get a reduction from FACT to SAT by Cook's theorem, and from the proof of NP-completeness for Subset Sum you will be able to extract a reduction from SAT to Subset Sum. Now compose those two reductions.)

---
Tags: np-complete, reductions, 3-sat, factoring, subset-sum
---


# Question
Title: developing a Turing Machine that checks for powers of 2
I want to write a Turing machine which checks for unary powers of 2 but without the use 0s, only accepting as input a series of 1s and dashes. I do not know of a sequence of states which would allow me to demonstrate this. I worked out 1 of the 2 I started with, which is make a palindrome checker but as for this I'm clueless, any help would be appreciated, even just a description how to begin to develop such algorithm.

Basically it works like this: you insert a sequence of 1s such as 1111 and the algorithm checks whether the number is divisible by 2, by checking the length of the input - hope I'm being more descriptive here, sorry if I'm not.

# Answer
When your input in unary system starts on the tape you have for example $11111111$
Now put terminator after input: $11111111#$

Now you have to put $2$ every second digit: $12121212$.
If the last digit is not $2$ after this operation - number was odd so you stop execution and reject, with one distinction: if length of number is 1 you are done ($2^0 = 1$).

After this phase you encode merging: replace last $2$ with $0$ and last $1$ with $0$ and first $2$ with $1$. It goes like this:
$11121200#$
$11110000#$
now shift guardian to the left:
$1111#$

Repeat steps. If during replacing phase you are about to change second $1$ with $2$ but you have guardian - you are done, number was power of two.
> 1 votes

# Answer
My approach to this problem was to use a two-tape Turing machine, using one read-only input tape and one working tape.

We will be using the working tape as a binary counter (with the least significant bit being the left-most one), so at the beginning we initialize it to $ 0 $ (or we can let it stay empty, but that adds a few special cases to our transition function). Then we start reading the characters from the input tape, one by one. After reading each character, we increment the binary counter by $ 1 $. This is done by the following process:

* Replace all leading $ 1 $s with $ 0 $s
* Replace the first $ 0 $ (or end of string) you encounter with a $ 1 $
* Return to the beginning of the counter

After reading all of the characters on the input tape, we check the number on the input tape. We need it to exactly match the regular expression $ 0^\*1 $, which means "an arbitrary (can be zero) number of leading zeroes, then a single one, then end of string", since all powers of two look like this when expressed as a binary string. Since a deterministic finite automaton would suffice for this last part of the task, checking the pattern with a Turing machine shouldn't be a problem.
> 0 votes

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


title: Weak bisimulation up-to $\approx$

text:
# Question
Title: Weak bisimulation up-to $\approx$
Given this definition of weak bisimilarity:

A configuration relation $\mathcal{R}$ is a weak bisimulation provided that whenever $P\ \mathcal{R}\ Q$ and $\alpha$ is $\mu$ or $\tau$ action then:

1. $P \to^\alpha P'$ then $Q \Rightarrow^\widehat{\alpha} Q'$ for some $Q'$ s.t. $P'\ \mathcal{R}\ Q'$
2. $Q \to^\alpha Q'$ then $P \Rightarrow^\widehat{\alpha} P'$ for some $P'$ s.t. $P'\ \mathcal{R}\ Q'$

P and Q are weakly bisimilar, written $P \ \approx \ Q$, if $P \ \mathcal{R} \ Q$ for some configuration relation $\mathcal{R}$.

My questions are:

1. For the relation $\mathcal{R} = \\{(\tau.a, 0)\\}$, $\mathcal{R} \nsubseteq \approx$ but $\mathcal{R} \subseteq \\, \approx \\! \mathcal{R} \approx$. Why is $\mathcal{R} \subseteq \\, \approx \\! \mathcal{R} \approx$?
2. According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...
3. Could you please provide an detailed explanation of why weak bisimilarity up-to $\approx$ is unsound? (You can use the example above but I would appreciate a detailed explanation

Thanks.

# Answer
> 2 votes
(partial answer)

> 1. For the relation $\mathcal{R} = \\{(\tau.a, 0)\\}$, $\mathcal{R} \nsubseteq \approx$ but $\mathcal{R} \subseteq \\, \approx \\! \mathcal{R} \approx$. Why is $\mathcal{R} \subseteq \\, \approx \\! \mathcal{R} \approx$?

Actually, the inclusion $\mathcal{R} \subseteq \\, \approx \\! \mathcal{R} \approx$ holds for any relation $\mathcal{R}$, and not just the one mentioned. Indeed, if we have $P \mathcal{R} Q$, then we also have $P \approx P \mathcal{R} Q \approx Q$, by reflexivity of weak bisimulation.

> 2. According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...

You have to check that $0\xrightarrow{{\hat\tau}} 0$, which (if I remember correctly) is defined as $0\xrightarrow{{\tau}}^\* 0$ which holds since the Kleene's star includes "zero steps".

I seem to remember that the "$\hat\alpha$" move definition made a special case for $\hat\tau$, specifically to allow for zero steps.

---
Tags: automata, formal-methods, process-algebras
---


# Question
Title: Solving Recurrence relation with master method?
I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that?

$$T(1) = c\>0 $$ $$T(n) = 9T(n/3) + f(n)$$ $$f(n) = n^2\cdot lg^3 (n) + n^3 \cdot lg(n)$$

I think that $f(n) = \Omega(n^{log\_ba})$ where $a=9, b=3$ so $n^{log\_ba}=n^2$.

Since $f(n) = n^3 lg(n)$, we can prove that $$a\cdot f(n/b) \leq c\cdot f(n)$$.

Is it a correct solution?

The only piece I am afraid could be tricky is proving $a\cdot f(n/b) \leq c\cdot f(n)$.

Thank you, Alan

# Answer
You are claiming that "we can prove that $af(n/b) \leq cf(n)$". There are two problems with this claim:

1. This is now what you actually need in order to apply the master theorem. The master theorem needs you to show that there exists $c \< 1$ for which $af(n/b) \leq c f(n)$ for all large enough $n$.
2. You haven't proved your claim.

Reiterating, to prove the claim you need to come up with a value of $c \< 1$ such that the following inequality holds for large enough $n$: $$ 9 (n/3)^3 \log(n/3) \leq cn^3 \log n. $$ This holds for $c = 1/3$, since $$ 9(n/3)^3 \log(n/3) \< 9(n/3)^3 \log n = \frac{1}{3} n^3 \log n. $$
> 1 votes

---
Tags: recurrence-relation, master-theorem, check-my-answer
---


# Question
Title: Would it be feasible to use a breadth first search algorithm for finding a solution to the 3x3x3 rubiks cube?
I am trying to implement a rubiks cube solving program,and I am trying to figure out which algorithm to use,so far I have only come up with using breadth first search to find a shortest path from the initial configuration node to the solution node. Each edge of the graph would be a 90 degree turn of a face of the rubiks cube(180 degree turns considered as 2 turns). As for representing each configuration of the rubiks cube in a node I am thinking of using a 3x3x3 array of integers.Each element of the array would be an int from 1 to 6 representing each of the colours. So if I used the Breadth First Search Algorithm for finding an optimal solution to the rubiks cube, would it run without taking up too much memory or too much time on an average computer?

# Answer
For given Rubik's cube, the maximal number of moves required to solve any permutation of valid configuration is 26 in quarter-turn metric, but only 20 as half-turn metric, it means that if you have the most distant configuration amongst all possibilities the height of the tree is 20 levels, using BFS you have to store the previous level, using only quarter-turn metric the number is 26, but using unconstrained BFS the algorithm will terminate after 20 steps. It would also be nice to keep the path from current configuration to solved state if you wish to use it later. With majority of solutions at 18 moves as high as about $29\*10^{18}$, the straightforward application of BFS is not really feasible for memory usage.

The worst case time required to solve puzzle from any configuration will traverse all solutions space, this is not feasible either. To put it in numbers, the empirical result to find the worst case number of moves took 35 cpu years, checking only solutions that require less than 20 moves, not aiming at the optimal state, reducing problem by symmetry and splitting to 55,882,296 sets that require checking shrinking actual number of states even further. These observations are not available using vanilla BFS. So the time usage is also not feasible.

As for the comments, using any algorithmic system of solving cube by human will not yield optimal solution, but will span at about 40 to 80 moves, but would be really straightforward to implement and both time and space would be negligible.

The Rubik's Pie (Domino) from the other answer is significantly easier, not only by removal of one layer, but some quarter turns are not possible to perform, but still it requires 18 moves in Half-turn metric and 19 in Quarter-turn metric, with solution space with only $406 425 600$ possible positions which is small when compared with $43 252 003 274 489 856 000$ ($10^{11}$ times smaller).
> 2 votes

# Answer
This depends on what you mean by too much time. I implemented a multi-threaded bidirectional BFS solver for the Rubik's Pie (2x3x3), and for a configuration that took 14 moves to get back to the solution node, it took about 10 hours to find the sequence, but ymmv.

Time was definitely the biggest factor. For a Rubik's cube of that size, there just aren't that many children of a given configuration, so you should be fine on memory.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Why is data fragmentation not possible on main memory (RAM)?
I am wondering why data fragmentation is a problem on main memory.

On a software level, virtual addresses are used anyway. So why can one address space not be split up into multiple segments, like a hard disk might do? I don't see how the performance would be affected, as the time needed to access memory addresses does not vary. Is this just a limit of the MMU?

In other words, my question is why does a process need continuous memory segments? For example:

Process D requests a memory block that could fit into the two free segments, if the block were split into two pieces. Why can't this be done?

It would be great if you could add a source so I could read more about this topic, if you have one.

# Answer
\[Disclaimer : I probably don't actually understand the question\]

-DRAM access time is not constant, as memory is physically arranged in rows, columns, banks. It is beneficial to limit fragmentation of actual memory.

-On multi-cpus hardware, memory can also have different access times ("NUMA"), so the OS needs to avoid putting programs at random.

-The physical address range can be not contiguous, it may be hidden by hardware mechanisms, or managed by the OS. For example a computer equipped with 8 slots for 4GB memory modules, can use a fixed 4GB address for each module, and if 1GB modules are installed, there are 3GB "holes" every 4GB.

MMUs can effectively hide to application software how memory is allocated. Each page (page size is often 4kB) can be mapped to actual memory, only on disk, or unitialised, several pages initialised to zero can be allocated to the same physical memory, several applications can share the same physical memory for code and nonmodified data...

---

So ? When a process does a malloc() for a 1MB array, the stdlib/OS will eventually return a pointer to a 1MB area of **virtual** memory. It is typically split into around 256 pages of 4kB. These 256 pages may be placed at random in the physical RAM, or maybe don't even exist until the process eventually accesses them. The OS maintains memory allocation structures for identifying which memory is used by what, and page tables for the MMU to perform virtual to physical translations.

(Note : Pages are not always 4kB on all architectures, some MMUs expect software management of virtual to physical translation instead of directly accessing tables, a.k.a. "tablewalking")
> 1 votes

# Answer
According to https://lwn.net/Articles/211505/, what you imagine should be done by the OS, is already done:

> Since Linux is a virtual memory system, fragmentation normally is not a problem; physically scattered memory can be made virtually contiguous by way of the page tables.

There are limits to this, as hardware devices may request contiguous hardware memory, and this creates memory holes (at least for hardware devices).

Another limitation is that doing all memory allocations and deallocations through page tables is inefficient. Setting up new page table entries takes longer than managing allocations through software and, if the page size is 4K, only works for allocations that are a multiple of 4K. Therefore the `malloc` and `free` glibc calls first allocate 4K blocks through `mmap` (using page tables) and manage this memory. They divide it into smaller contiguous memory areas and return them when a `malloc` call requests a small chunk of memory. Algorithms to reduce memory fragmentation of software-managed memory are for example the Buddy memory allocator.
> 4 votes

---
Tags: memory-hardware, virtual-memory, memory-allocation
---


# Question
Title: Necessity of convolution operations for product of two polynomials via brute force method
Reference: Page 4 of this document

Given two polynomials $p(x)$ and $q(x)$ each of degree $n$ represented in coefficient form, it takes $\mathcal{\Theta}(n)$ time to evaluate given some input $x$.

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c\_k = \sum\_{i=0}^k a\_i b\_{k-i} \right)$ which takes $\mathcal{\Theta}(n^2)$ time.

However, if we wanted to evaluate this product with some given input $x$, we can evaluate the two polynomials $p(x)$ and $q(x)$ separately and then multiply the two scalar results. Overall, this would take $\mathcal{\Theta}(n)$ time for two evaluations and a scalar multiplication. This lets us avoid having to do convolutions and would be faster than $\mathcal{\Theta}(n^2)$.

**Question**: When it comes to evaluation of the product of two polynomials, is it actually $\mathcal{\Theta}(n)$ using the method above or are we somehow still doomed to $\mathcal{\Theta}(n^2)$?

I'm aware there's a faster way to do this in $\mathcal{O}(n \log n)$ time via Fast Fourier Transform, but I'm more curious about the necessity of the convolution calculations. I suspect it's more if we care about getting the coefficients of the product than the actual evaluation, as in we more care about knowing $\\{c\_0, c\_1, c\_2, \dotsc\\}$ than $c(x) = p(x)q(x)$.

# Answer
> 3 votes
Given two polynomials $P\_n(x)$, $Q\_n(x)$, you can obviously calculate the value $P\_n(x) · Q\_n(x)$ in $O(n)$ for every x. The document asks about calculating the coefficients, which is a very different question. If all you want is to evaluate $P\_n(x) · Q\_n(x)$ for various values of x, then calculating the coefficients of the product polynomial isn't actually useful on current processors (due to latency, you can usually calculate two polynomials of degree n in parallel in practically the same time as one, and almost twice as fast as one polynomial of degree 2n). However, there are situations where the coefficients are *exactly* what you want.

As the document says, the coefficients can be calculated using FFT in $O (n log n)$. A straightforward divide-and-conquer method doesn't improve on the trivial $O(n^2)$. The document mentions a more clever divide-and-conquer method that multiplies polynomials of degree $2^k$ in $O (3^k)$. Knuth's "Art of Computer Programming" has an improvement on this which multiplies polynomials of degree $m^k$ in $O ((2m-1)^k)$, for every fixed m, but with constant factors growing quite quickly.

# Answer
> 3 votes
> In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c\_k = \sum\_{i=0}^k a\_i b\_{k-i} \right)$ which takes $\mathcal{\Theta}(n^2)$ time.

That's not what it says. It says firstly that **convolution is equivalent to polynomial multiplication** (i.e. an algorithm for convolution is also an algorithm for polynomial multiplication and vice versa); and secondly that

> The direct approach is to compute all $c\_k$ using the formula above

and that **this approach** has complexity $\Theta(n^2)$. The FFT approach calculates a convolution (and indeed, the continuous Fourier transform produces a convolution of two functions: the convolution of two coefficient sequences is a discrete analogue).

---
Tags: algorithms, algorithm-analysis, polynomials, multiplication
---


# Question
Title: Does no parents imply variable independence in a Bayesian network?
If A and B don't have parents on a Bayesian network, does that mean we can infer A and B are independent? Whatever the answer is, please explain how you get to it.

# Answer
> 4 votes
Yes, they would be **unconditionally independent**.

This is simply a consequence of the factorisation of a Bayesian network into conditional probabilities. For example, this network will factorise as $p(A,B,C)=p(C|A,B)p(A)p(B)$, implying that $p(A,B)=p(A)p(B)$, which is the very definition of unconditional independence for the parent-less nodes $A$ & $B$:

As for the factorisation $p(A,B,C)=p(C|A,B)p(A)p(B)$ that led us here, this is definitional for Bayesian networks. I recommend Section 3.3 of Barber for a fuller explanation.

On the other hand, they are **conditionally dependent if conditioned on a collider**. For example, nodes $x$ and $y$ are graphically conditionally dependent when conditioning on the collider $z$ in each of these 2 BNs:

Chapter 3 of the same source contains a fuller description of BNs and similar graphical networks, together with various possible tests for conditional independence.

---
Tags: bayesian-network
---


# Question
Title: Does a turing machine halt with input left on tape?
is the string aabb in the language of this Turing machine ?? as upon reading aa it goes to the final state but upon b there is no transition defined so won't it result in a dead configuration?

# Answer
When a Turing machine enters an accepting state, it immediately stops running and accepts whatever the original input string was (regardless of the state of the tape). So given the input `aabb`, the Turing machine will read the two `a`s and enter the accepting state $q\_2$, at which point it will halt and accept `aabb`.

In this case it doesn't matter that there's no transition for reading a `b` from $q\_2$ because we've already accepted (though you are correct in general that whenever we're running a Turing machine and we arrive at a state with no transition defined for the character we're reading, we implicitly go to a dead state and reject).
> 3 votes

---
Tags: turing-machines
---


title: Perfect natural number

text:
# Question
Title: Perfect natural number
A perfect natural number is that which is equal to the sum of it's divisors. For example 6 is perfect: 1+2+3=6 also 28 is perfect.

Prove the following language is NP hard:

L={\< n\> | n is a perfect natural number}.

You can use the fact that if

$$n=p\_{1}^{m\_{1}}p\_{2}^{m\_{2}} \cdot \cdot \cdot p\_{k}^{m\_{k}}$$

where $p\_{i}$ are n's prime divisors, then the sum of n's divisors including n would be:

$$(1+p\_{1}+p\_{1}^2+...+p\_{1}^{m\_{1}})(1+p\_{2}+p\_{2}^2+...+p\_{2}^{m\_{2}})\cdot \cdot \cdot (1+p\_{k}+p\_{k}^2+...+p\_{k}^{m\_{k}})$$ Now I know the proof should contain a polynomial time reduction from some NP problem to this language L, most likely from SAT, I only can't figure out how to go about it, any guidance would be appreciated.

# Answer
NP ≠ NP hard.

NP means: For every perfect number, there is a certificate that lets you prove in polynomial time that it is perfect.

And that is clearly the case. For every perfect number, I can give you the factorisation, plus for all large prime factors a proof that these large factors are primes, and then you can quite easily check that the number is perfect.

NP hard means: If you can solve this problem, then you can solve any problem in NP. I don't see this. Especially since perfect numbers are so rare. (Why does it make it unlikely that this is NP hard? Polynomial time reduction means: If you take a problem in NP, then for any instance with answer "Yes" there is a perfect number so that the fact that this number is perfect proves the answer to your problem is "Yes". For different instances I'd expect different perfect numbers to be needed. But there are so few known...)
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Expander Graph - Is the following graph family an expander graph?
> Consider the family of graphs of degree $6$ with vertex set $V\_n=(a, b, c)$ for all $0\leq a, b, c \leq n-1$ with $(a,b,c)$ being connected to $(a-1, b, c),(a+1, b,c), (a, b-1, c), (a, b+1, c), (a,b,c-1), (a,b, c+1)$, with all operations modulo $n$. Show that this is not a family of expander graphs.

I've been struggling with this question for over a week. I tried looking at from the algebraic perspective and show that the spectral gap is getting smaller as n(the number of vertexes) rise. But I got stuck a long the way and now I don't know if I'm on the right track at all.

# Answer
Given $n$, consider the set of vertices $S = \\{ (a,b,c) : c \< n/2 \\} \subseteq V\_n$. Assuming for simplicity that $n$ is even, this set contains exactly half the vertices. An edge connects $x \in S$ to $y \notin S$ iff $x = (a,b,n/2-1)$ and $y = (a,b,n/2)$, for a total of $n^2$ edges. Therefore the expansion of $S$ is $|E(S,\overline{S})|/|S| = n^2/(n^3/2) = 1/n$, which converges to zero.
> 1 votes

---
Tags: graphs, expanders
---


# Question
Title: Semantic natural language processing - from texts to logical expressions? Universal knowledge base?
My question is - **is there a semantic natural language processing that tries to understand the meaning of the texts and that tries to derive the consequences of the understood meaning? Is there a universal knowledge base that can be used for the "grounding" of the texts?**

I have heard a lot about statistical NLP and NLP with neural networks but those approaches are not scalable, are not exact and are not satisfying. Is there (and if not - then why) a semantic NLP and semantic natural language understanding that tries to translate the texts into logical formulas? Today we have a vast array of logical formals - both rigorous and both nonmontonic, adaptable, fuzzy, probabilistic and so on? So - if we have those logics why don't we translate texts into them?

And if texts are translated into logical formulas then the universal knowledge base (KB) can be built. This KB should be used as reference KB. I.e. if some text contains the phrase "logical continuum" then this KB should contain all the possible definitions (expressed as logical formulas) of this phrase (according to the different texts, authors) and one should be able to reason over those definitions, to use definitions for applying this phrase into the new text (possibly - computer generated texts), to use definitions for deriving more general or more special notions with relevant definitions, to form completely new concepts. There can be two types of terms in this KB: abstract ideas and concrete real world facts, like country Belgium and so on.

I am aware of existence of some KBs like ConceptNet and WordNet (not really useful) and Cyc/OpenCyc (formal KB with reasoning capabilities) and there is also very promising framework **OpenCog** which (fortunately) has interesting reasoning engine, but (unfortunately) lacks the public knowledge base for experiments. OpenCog is really interesting, because it unifies probabilitist and rigorous reasoning: each concept (Atom in their terms) have strength/probability value and if those values converge to 1, then proababilistic reasoning tends to rigorous classical logic style reasoning. But that's all.

So - **are there such notion as semantic NLP and are there endeavours to create universal knowledge base for semantic interpretation of any text**? Are there ongoing projects in this field?

# Answer
> 1 votes
There are several implementations of semantic parsers that convert natural-language texts into formal logical representations of their meanings. Natural language understanding systems can also be based on discourse representation theories that represent the meanings of English texts using first-order logical predicates.

I have found at least one system that is able to generate a knowlege base from statements that are given in a natural language. The ACE Wiki is based on Attempto Controlled English, which is a semantically unambiguous subset of the English language.

---
Tags: logic, artificial-intelligence, semantics, natural-language-processing
---


title: Prove EXP to be regular or non-regular

text:
# Question
Title: Prove EXP to be regular or non-regular
Given L is regular, Prove/Disprove that the following language is regular or not. $EXP = \\{w| w^{|w|} ∈L\\}$

# Answer
Suppose that $L$ is accepted by a DFA with states $Q$, initial state $q\_0$, accepting states $F$, and transition function $\delta$.

With every word $w$ we can associate the function $\delta\_w\colon Q \to Q$ given by $\delta\_w(q) = \delta(q,w)$. Note that there are finitely many such function. It is not hard to check that for any such function $\delta\_w$, the language $L\_{\delta\_w} = \\{ x : \delta\_x = \delta\_w \\}$ is regular.

We can also associate with $w$ a set $N\_w = \\{ n \in \mathbb{N} : \delta(q\_0,w^n) \in F \\}$. Note that $N\_w$ depends only on $\delta\_w$, and so there are finitely many such sets. Moreover, each of them is eventually periodic (why?), and so the language $L\_{N\_w} = \\{ x : |x| \in N\_w \\}$ is regular.

Combining the two observations, we see that $$ EXP = \bigcup\_{w \in \Sigma^\*} (L\_{\delta\_w} \cap L\_{N\_w}). $$ While the sum is infinite, there are only finitely many different summands, and we deduce that $EXP$ is regular.
> 1 votes

---
Tags: regular-languages
---


title: Sort by typical position?

text:
# Question
Title: Sort by typical position?
Lets say, we have a lot of lists (sequences of variable length) of some limited set of elements:

```
[A, B, D, E, Q], [A, D], [A, C, E, F, G, H, Y, Z], [B, A, E, D, Z, Y], ...

```

The problem is to get the single order, based on "how typical" some position is, eg, in our case it can be (coincidence with alphabetical order is just a coincidence):

```
[A, B, C, D, E, F, G, H, Q, Y, Z]

```

But lets say `[Z, Q, Y, C, B, A, D, E, F, G]` is "surprising" order, far from being "typical".

The questions are:

* are there any "official" CS terms for the situation (so I can do further searches)?
* what are practically popular definitions / metrics for "how typical" (or "surprising") in the above description?

My idea so far is to count "average position", normalized to the max length of the list. Then the order will be by increasing normalized average positions. I feel, maybe term *rank* and some statistics' techniques are also applicable to this, but I am more interested in some easily (one pass) computable metrics. Any pointers?

One more idea is to calculate probability of every pair where one element is before another, and sort based on whether probability is less than 0.5 or more. But this may need a triangular matrix and a lot of computations. (For the example above, `p(A before D|both occur) = 1`, but `p(A before B) = 0.5`).

One gotcha may be that is some element is usual for the beginnings and ends, but never the middle, the average result may still be in the middle... But I guess it may be too subtle to satisfy.

For now, using very rough method:

```
def approx_position(position, length, master_length):
    return int(position * master_length / float(length))

seqs = ['A', 'B', 'D', 'E', 'Q'], ['A', 'D'], \
    ['A', 'C', 'E', 'F', 'G', 'H', 'Y', 'Z'], ['B', 'A', 'E', 'D', 'Z', 'Y']

master = []
for s in seqs:
    total = len(s)
    est_len = len(set(master) | set(s))
    for i, item in enumerate(s):
        if item not in master:
            new_pos = approx_position(i, total, est_len)
            master.insert(new_pos, item)

print master
# ['A', 'C', 'B', 'D', 'F', 'G', 'H', 'E', 'Y', 'Z', 'Q']
# when seqs in reversed order:
# ['B', 'C', 'A', 'F', 'E', 'G', 'H', 'D', 'Q', 'Z', 'Y']

```

NB. Python insert works on intervals between list elements. So 0 corresponds to the place before first element.

Not ideal, but at least almost one pass (one hidden pass in set union).

Something similar is for example discussed here: https://stackoverflow.com/questions/4645874/merging-some-sorted-lists-with-unknown-order-sequence However, my problem is overdetermined, so the question is how to do relaxation, while the results are still near optimal (the criteria is part of the answer).

(trying to widen my horizons as it is usually hard to find a right term for something if one has never encountered that term before)

# Answer
As I understand your question, your problem statement is:

> Given a set of ordered lists $\\{L\_1,L\_2,\ldots,L\_n\\}$, learn the relation $r(a,b)$ for the partial order of each $L\_1,L\_2,\ldots,L\_n$. Then use this learned relation to sort a new list.

So, in your example, the relation would be the lexicographical order. But your data set has some noise because the last list breaks the order in several places.

This seems to be a case of preferrence learning, and more specifically, object ranking.
> 2 votes

# Answer
The problem of sorting elements given some approximately sorted samples is difficult. There is a similar problem called ranked voting (not a CS term, sorry). It is simpler in two important aspects - all of the lists given contain all of the elements each, and we are only interested in the top few slots rather than the entire list. Your proposed method is equivalent to the Borda count method.

However, if you are only interested in finding surprising orderings, you can do it by computing the average disagreement between each pair of lists. As for the disagreement between two lists, I propose counting the number of pairs of elements that exist in both lists and whose relative order differs. For example `ABCD` and `DCBA` have six conflicting pairs while `ABCD` and `FEDC` only have one.
> 0 votes

---
Tags: string-metrics, ordering
---


# Question
Title: How to show MULT={a#b#c| a,b,c binary natural numbers and a ✕ b = c} is in Log Space?
Let MULT$=\\{a\\#b\\#c| a,b,c \text{ binary natural numbers and } a\times b=c\\}$

Prove that MULT $\in L$

How do I show that this language, MULT, is computable in Logarithmic space?

Let us assume a#b#c is on the input tape, we now need away of multiplying a with b and checking if the product is c, while using only $log(n)$ space while n is the length of the input.

# Answer
> 1 votes
In high-school multiplication, you multiply $a$ by $b$ by summing shifted copies of $b$, some of them zeroed out (according to $a$). You can implement this algorithm in logspace by calculating the result from LSB to MSB, keeping track of the carry. The crucial point is that the carry is only $O(\log n)$ bits long.

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


title: Recursion call inside a for loop time

text:
# Question
Title: Recursion call inside a for loop time
I'm analyzing a piece of code that has a recursive call inside a for loop such as:

```
def fun(n):
    for i in range(0, 256):
         if ( n > 0):
             fun(n-8)

```

(I only included a general piece of code not the actual version)

It is my understanding that a recursive call gets assigned T(n) = T(n-8) but what happens when it is nested inside a for loop?

# Answer
> 2 votes
As there is a loop over $F(n-8)$, so we will have 256 times $F(n-8)$. Hence, time complexity would be: $$T(n) = 256\times T(n-8) = 256\times(256\times T(n-16)) = \Theta(256^\frac{n}{8})$$.

As mentioned in comment $256 = 2^8$, we will have $T(n) = \Theta(2^n)$.

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


# Question
Title: What is the time complexity of this Factorization program?
`input: n-bit integer X`

`output: list of prime factors and their multiplicity`

`acc = X`

`for i = 2 ... sqrt( X )`

`--count = 0`

`--while acc % i == 0`

`------acc = acc / i`

`------count = count + 1`

`--if count > 0`

`------print i (count)`

I know that for the worst case, a n-bit integer is 2^n maximum.

So the time complexity for `for i = 2 ... sqrt( X )` is `2^(n/2)-1`

Now I'm really confused with the time complexity of `while acc % i == 0`

For the worst case, let's say that the n-bit number X is a prime. Then the while loop will not be executed at all. How can I define its time-complexity?

How can I find the Big-O of this algorithm? Is iit O(2^n) or O(2^(n/2))

# Answer
> 0 votes
Your algorithm takes $O(X^{1/2})$ in the worst case, which isn't too bad, but it also takes $\Theta(X^{1/2})$ in the best case. That's because you *always* test divisibility by all numbers up to $X^{1/2}$ even when it is clear that you found all factors of X already.

The loop testing acc % i = 0 is negligible, because X has at most $\log X$ factors.

---
Tags: algorithms, algorithm-analysis, time-complexity, asymptotics, java
---


# Question
Title: Algorithm for packing various shapes inside of a rectangle
Say I am given a rectangle of width $W$ and length $L$. I now have to fit as many regular shapes of area $A$ into this rectangle as possible. For example, if the shape is a circle, I need to fit as many circles of area $A$ into the rectangle as possible. All the shapes trying to be packed in a given instance are identical, we also assume we are living in 2D.

What would be the general way to approach this problem? Can it be done with a program or is this a mathematical question?

# Answer
As pointed out by the other answer, this is an example of bin packing, a type of problem that is NP-complete.

Skiena Section 17.9 reports:

> Fortunately, relatively simple heuristics tend to work well on most bin-packing problems.

The same source provides the following heuristic recommendation:

> Analytical and empirical results suggest that *first-fit decreasing* is the best heuristic. Sort the objects in decreasing order of size, so that the biggest object is first and the smallest last. Insert each object one by one into the first bin that has room for it. If no bin has room, we must start another bin. In the case of one-dimensional bin packing, this can never require more than $22\\%$ more bins than necessary and usually does much better. First-fit decreasing has an intuitive appeal to it, for we pack the bulky objects first and hope that little objects can fill up the cracks.
>
> First-fit decreasing is easily implemented in $O(n \ \text{lg} n + bn)$ time, where $b \leq min(n,m)$ is the number of bins actually used. Simply do a linear sweep through the bins on each insertion. A faster $O(n \ \text{lg} n)$ implementation is possible by using a binary tree to keep track of the space remaining in each bin. We can fiddle with the insertion order in such a scheme to deal with problem-specific constraints.

I recommend reading the original material in its entirety.
> 3 votes

# Answer
The problem for shapes of general form is in the class of NP-Hard, so there is nos efficient algorithm to solve this problem. Bin packing is a well known class of problems.

The approach will depend on your intentions:

* Need a complete algorithm, i.e. an algorithm that compute the correct solution for the problem but can only compute small instances of your problem.
* Need a fast approximation algorithm, i.e an algorithm that compute a "good" solution for large instances but not necessarily the optimal. I have seen very nice results using meta heuristics to solve this.

Almost every code I have seen so far works with not any kind of shapes but small sub classes such as polygons and circles.
> 1 votes

---
Tags: algorithms, mathematical-programming, packing
---


# Question
Title: Recursive Algorithm Copying Array vs. Time Complexity
If I am implementing binary search using a recursive algorithm on an array it will be bounded by $O(\log(n))$. However, what will occur if the array is **NOT** passed by referenced and rather by value. This means that the recursive call will have to first copy the elements of the array (half the original items). Does this mean that the resulting time complexity for a pass-by-value binary search using an array is $O(\log(n)\cdot\log(n))$ or $O(\log(n)^2)$?

# Answer
The first point is that as in the most binary search implementations we are passing an array with their sub-indices each time, and in the common programming languages, arrays are passed by reference this problem cannot happen.

However, if this copy happened each time this would be $n+\frac{n}{2} + \frac{n}{2^2} + \cdots + \frac{n}{2^{\log(n)}} = \Theta(n)$. Hence, time complexity of this algorithm which copies half of the passed array would be $\Theta(n)$.

Moreover, if the implementation passed the whole of the array each time and control the search using sub-indices, the time complexity would be worse and it would be $\Theta(n\log(n))$, as each time ($\log(n)$) copy the whole of the array with size $n$.
> 0 votes

---
Tags: algorithm-analysis, time-complexity, recursion
---


# Question
Title: Complexity for find pairs with sum - BST
I have written an algorithm for find all the pairs in a BST which have a given sum.

```
def getPairsForSum(rootNode : Node, expectedSum : Int) : List[(Node,Node)] = {
    def check(node1 : Node, node2 : Node) : List[(Node,Node)] = {
      if (node1 == null || node2 == null) Nil
      else {
        val actualSum = node1.value + node2.value
        if (actualSum == expectedSum) {
          List((node1, node2))
        } else if (actualSum > expectedSum) {
          check(max(node1, node2).leftNode, min(node1, node2)):::
            check(min(node1, node2).leftNode, max(node1, node2))
        } else {
          check(max(node1, node2).rightNode, min(node1, node2)):::
            check(min(node1, node2).rightNode, max(node1, node2))
        }
      }
    }
    if(rootNode.value > expectedSum/2) check(rootNode, rootNode.leftNode)
    else check(rootNode,rootNode.rightNode)
  }

```

It works well (though gives nodes like (n1,n2) and (n2,n1) in the result). I would like to know the complexity of this algorithm. I am not sure how do I approach calculating time complexity. Is this algorithm better than `n square`??

**EDIT** Assuming that this bst does not allow duplicates.

# Answer
It would be $O(n^2)$ in the worst case. Suppose root of BST is $15$, all left nodes are $7$, and all right nodes are $21$. We want to find all pairs which their sum is $28$. Hence, you should report all $\frac{n}{2}\times \frac{n}{2}$ items (all left nodes with all right nodes). Hence, your algorithms should report $O(n^2)$ pairs in the worst case.
> 1 votes

---
Tags: data-structures, trees, binary-search-trees
---


# Question
Title: A plane-sweep algorithm for a points in triangles inclusion problem
I was given the following homework assignment:

Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle lies in the interior of another, and no edge/vertex is part of more than one triangle. The points are in general position with respect to the triangles, that is, no point lies on a vertex or an edge of a triangle. The triangles are given by the coordinates of their vertices, and also the points are given by their coordinates. All points and vertices have pairwise different coordinates. (See below for an example.)

The task is to determine for each of the $p$ points whether it lies inside a triangle, and if yes in which. Design an efficient algorithm for solving this task. Explain your solution in detail, show its correctness, and analyze its runtime and memory requirements.

I've coem up with the following algorithm, that closely resembles the Bentley–Ottmann algorithm for the intersection of line segments. The idea is to sweep the plane from left to right analogousely to it. The main point is the observation that a point p lies in a triangle iff $p$ lies $x$-wise between the triangle starting - and triangle endpoint as well as $y$-wise between the intersection points of the sweep line with the triangle sides. (For an illustration see below.)

SET-UP: Let $X$ be a priority in which we store the $x$-coordinates of the points of $P$ and $T$. Let further $Y$ be a Red-Black-Tree in which we store the $y$-coordinate-wise sorted list of triangle edges. At last let $T$ be the set of triangle points and $P$ be the set of the remaining points.

ALGORITHM:

1) $X := 0, Y := 0$

2) Insert the $x$-coordinates of all points of $P$ and $T$.

3) while $x \neq \emptyset$ do

* Find the minimum $m$ of $X$ and delete it from $X$.
* If $m$ is a triangle starting point then insert the incident edges into $Y$.
* If $m$ is a triangle middle point then delete the incident edge to the left of $m$ and insert the incident edge to the right of $m$ into $Y$.
* If $m$ is a triangle end point then delete both incident edges from $Y$.
* If $m$ is a point out of $P$ then do for all pairs of adjacent edges in $Y$:

Calculate the intersection points of the sweep line L with the current pair of adjacent edges. Check wether the $y$-coordinate of $m$ lies between the $y$- coordinates of said intersection points. If it does the point $m$ is in the respective triangle. Report $m$ and said triangle.

I think that this algorithm should have $\mathcal{O}((p+t)\*log(p+t))$ running time, but I don't know how to argue that in a more formal manner with the characteristic of Red-Black-Trees and so on. Could you help me with that?

Illustration 1 Illustration 2 Illustration 3

SOURCES:

http://www.ist.tugraz.at/\_attach/Publish/Eaa17/assignment\_06.pdf

# Answer
Generally, you can analyze each step of the algorithm. Step 2 for constructing the tree (as insert operation can take $O(\log(n))$) is $O((p+t)\log(p+t))$. All operations in if statements take $O(\log(n))$ (finding the minimum, deleting a member, inserting a member, and so on). Also, the main while loop takes $|X|= p + 3t$. Hence time complexity of the algorithm would be $O((p+t)\log(p+t))$ as you guess.

In sum, to analyzing time complexity of an algorihtm in a formal manner, it would be enough discussed on each step of the algorithm.

For correctness, you should show that this algorithm can find a general point inside its triangle correctly.
> 2 votes

---
Tags: asymptotics, runtime-analysis, computational-geometry
---


# Question
Title: Enumerate partitions of a set with blocks of equal size
Given a set $\\{1,\ldots,ck\\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$?

In *The art of computer programming (Fascicle 3B)* by Knuth, there's a mention of an algorithm by Ruskey that can list all partitions with $c$ blocks. I could just use this algorithm and discard all partitions that violate the constraint on the equal size of blocks, but I would visit many useless partitions.

Is there a better way?

# Answer
> 2 votes
I don't know if there is a known algorithm, but there is an obvious algorithm: a partition is given by a subset $S$ of $\\{1,...,ck\\}$ containing the number $1$ and having cardinality $k$, plus a partition of the remaining $(c-1)k$ elements in subsets of cardinality $k$.

This gives a recursive algorithm provided one lists efficiently all subsets of $\\{2, ..., ck\\}$ having cardinality $k-1$.

Suppose that we have a function $subsets(A, n)$ that lists all the subsets having cardinality n in a set A. We define a function $partitions(A, k)$ that lists all the partitions of $A$ in subsets having cardinality $k$, provided $|A|$ is a multiple of $k$:

```
function partitions(A, k):
    if A is empty:
        yield the empty partition
    else:
        let a be an arbitrary element of A
        for each S in subsets(A \ {a}, k-1):
            X = S union {a}
            for each P in partitions(A \ X, k):
                yield P union {X}
end

```

# Answer
> 3 votes
Section 5.10 of Ruskey's book *Combinatorial Generation* gives a combinatorial Grey code for linear extensions of posets and describes a bijection between set partitions of a chosen shape and linear extensions of a corresponding poset.

> ### Partitions of Given Type
>
> Let $P(n\_0, n\_1, \ldots, n\_t)$ be the set of partitions of the set $\\{1, 2, \ldots, n\\}$ into blocks of sizes $n\_0, n\_1, \ldots, n\_t$, where $n = n\_0 + n\_1 + \cdots + n\_t$. For example, the partition $\\{\\{2, 8\\}, \\{3, 5\\}, \\{6, 12\\}, \\{1, 10, 11\\}, \\{4, 7, 9\\}\\}$ is in $P(2, 2, 2, 3, 3)$. We have listed the elements in order and the blocks of equal size by the magnitude of their smallest element. The problem of generating the elements of $P$ can be reduced to that of generating the linear extensions of a certain forest poset. The cover relations of the poset consist of chains of sizes $n\_i$ together with chains of the maximal elements of the previous chains which have equal values of $n\_i$. The linear extension corresponding to our example is $7, 1, 3, 10, 4, 5, 11, 2, 12, 8, 9, 6$. The inverse of this permutation is $2, 8, 3, 5, 6, 12, 1, 10, 11, 4, 7, 9$, which is just our original partition but without the curly braces.
>
> To be a little more precise, assume that the $n\_i$ are listed such that $n\_0 \le n\_1 \le \cdots \le n\_t$, and let $s\_i = \sum\_{j=1}^{i-1} n\_i$. The cover relations of the poset are indicated by the $t + 1$ chains $C\_i = s\_i + 1, s\_i + 2, \ldots, s\_i + n\_i$ and $D\_i = s\_i + 1, s\_{i+1} + 1, \ldots, s\_j + 1$, where $n\_{i−1} \< n\_i = n\_{i+1} = \ldots = n\_j \< n\_{j+1}$.

The algorithm *per se* is described in Pruesse and Ruskey, *Generating linear extensions fast*, SIAM Journal on Computing 23.2 (1994): 373-386.

---
Tags: algorithms, combinatorics, enumeration, partitions
---


# Question
Title: Composition of handler types in algebraic effects and handlers
In the paper "An introduction to algebraic effects and handlers" (Pretnar, Matija. Electronic Notes in Theoretical Computer Science 319 (2015): 19-35), handlers get a handler type that looks like a function type: $\underline{C} \Rightarrow \underline{D}$. These can be "applied" with the `with h handle c` syntax.

What I've noticed is that the only way to get a handler type is with the handler syntax, which means there's no way to get composition of handler types: given $\underline{A} \Rightarrow \underline{B}$ and $\underline{B} \Rightarrow \underline{C}$ there is no way to get $\underline{A} \Rightarrow \underline{C}$.

I believe this is because there is no abstraction for computations like there is an abstraction for values ($\lambda x . c$). Is this left out because of simplicity of is there a problem with such abstractions which means you can never have composition of handler types in a consistent system?

# Answer
> 5 votes
You are correct that the reason lies in the lack of computation abstractions. They are left out because they are not a standard programming construct, especially in a call-by-value calculus. But even if you added them, I don't think they should be given a type of the form $\underline X \Rightarrow \underline Y$ because they are in general not homomorphisms, what the type would suggest.

You can get around in two ways:

1. you can apply the function `fun t -> with h' handle (with h handle t ())` of type $(\mathtt{unit} \to \underline A) \to \underline C$ on a thunked operation. For example, in Multicore OCaml the only way of making a general handler is through a function that takes a thunked computation.
2. you can precompose the handler similar to what @chi suggested. If `h` is of the form

```
handler {
    return x -> c_ret,
    op1(x, k) -> c1(x, k),
    ...
}

```

then the composed handler

```
handler {
    return x -> with h' handle c_ret,
    op1(x, k) -> with h' handle c1(x, k),
    ...
}

```

has the type $\underline A \Rightarrow \underline C$.

# Answer
> 1 votes
I only had a cursory look to the paper, but I think that, if $h: \underline A \Rightarrow \underline B$ and $h': \underline B \Rightarrow \underline C$, then

```
handler
{ return x -> with h' handle (with h handle (return x))
, op1(x,k) -> with h' handle (with h handle (op1(x,k)))
, ...
}

```

has the wanted type $\underline A \Rightarrow \underline C$.

---
Tags: lambda-calculus
---


# Question
Title: Time Complexity of reconstructing corrupted file
Suppose all the spaces between the words(only small letter alphabets and no punctuation) in a file has been deleted and we need to reconstruct the file. There is a dictionary available which answers whether a word is valid or not in O(1).

Brute force approach is to use backtracking i.e try out all the possibilities. Take for example: "donotsitonthefloor" I start from d, and check if "d" is in dictionary, if not i move ahead. then check for "do", it is a valid word, so i check whether "notsitonthefloor" can be split into valid words. And so on ..

Now coming to analyzing time complexity of this approach, the best i can come up with is:

$T(n) = \sum\_{i=1}^n T(n-i) + O(n)$

1) Is the above equation correct? If so, is it possible to simplify it? (i suppose master's theorem can't be applied to this kind of equation).

2) Suppose if dynamic programming is used to store results of repeated calls, i.e. using an array to store whether input\[i:n\] is valid or not and checking first in this array before making a repeated call. What would be the running time after applying this optimization?

# Answer
> 2 votes
Some remarks of general nature since I think you're operating based on flawed assumptions.

Removing spaces is not unambiguously reversible (unless your dictionary is prefix-free, or restricted in other suitable ways). I'm sure you can easily come up with example strings that can be split into valid English words in several ways.

If your dictionary *is* prefix-free, a linear scan (e.g. based on a finite automaton) is quite enough, after pre-processing the dictionary. That's basically how lexers work.

In case your dictionary is not restricted and you want to find any (or all) valid split, dynamic programming seems prudent. Before analysing it, write down the algorithm in suitable detail; then use the standard approach.

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


# Question
Title: structure of cache when CPU uses words smaller than the main memory
As the title says, i have the following excersice:

An associative mapping cache with four lines in each set, can store in each line two words of 16 bits each. It can store 4K words, that they have length 32bits from Main memory. The CPU is 16 bits and the address that he produces is 24 bits length. So the solution is shown below:

I can understand why set has 10 bits, or why tag is 12, but I can't figure out the **word select** and **byte select** signals. Also how can this cache store two words as the image shows (Word 0 and Word 1), when the line size is 16 bit, but the word size from Main Memory is 32 bits.

# Answer
So the question is a bit confusing because there are two types of words: CPU words that are 16 bits, and memory words that are 32 bits. This can happen when the CPU registers have 16 bits but the memory chip is organized in such a way that the minimum accessible unit (a word) is 32-bit. The cache will always read/write multiple of **memory words**, in this case one word per line. Since the CPU word is 16 bits, each memory word (32 bits) actually holds two CPU words, those are the Word 0 and Word 1 on the picture.

Now, when the CPU accesses memory, the cache will find which lines corresponds to the request. This line contains 32-bit, but maybe the CPU only wanted 8 bits, so we have to extract those 8 bits from the line. In this example, bit 1 will select between Word 0 and Word 1 (which are CPU words). The resulting word still has 16 bit, so we use bit 0 to select between the low or high 8 bits of that word.

If you still find confusing, forgot about Word 0 and Word 1 and just imagine that each cache line stores 4 bytes (=32 bits). Now to select one byte in 4, you need to discriminate based on the lower 2 bits of the address. If the cache had 8 bytes per line, then you would use 3 bits. And so on. In general, the format of an address is

```
| Tag | Index | Offset |

```

where Index selects the line (there are many way of doing so) and Offset selects the byte within the Line.
> 1 votes

# Answer
If the memory is byte addressable, each memory address represents a byte in the memory. If the CPU is operating at 2 byte granularity (16 bits), all the addresses you'll see are 0, 2, 4, 8 and so on. If you get the hex representation of these addresses, you'll see that the last bit is always zero. This last bit represents the byte within the 16 bit data, hence can be called **byte select**. Now the cache lines are of 2 word lengths, accommodating 4 bytes. Therefore all the cache line addresses you'll see are 0, 4, 8, 12, and so on. Again if you check the hex representation of these, you'll notice that last two bits are always zero. We have already established that the last bit gives us the byte within a word. And the next bit gives the word within a cache line, hence called **word select**.
> 0 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Sampling Multiple Times From a Markov Chain
In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. Lets fix some $\varepsilon\in (0,1\]$ as our closeness parameter.

Now suppose that we have a Markov Chain M with mixing time T, and suppose that we want to draw 10 independent samples from the stationary distribution of M. What is the correct way to do that?

1. Do we have to apply the Markov chain for $10\cdot T$ steps, and pick the resulting states at time $T, 2T, ...,10T$ as my samples, or...
2. is it enough to apply the Markov chain for T+10 steps, and pick the resulting states at time $T+1,T+2,...,T+10$ as my samples?

The justification for the first alternative is that once we have drawn a sample state $s$ at time $T$, then the immediate samples following $s$ will be correlated with $s$ according to the transition matrix of the chain.

On the other hand, maybe it is possible to use some property about Markov chains to show that alternative 2 is enough? For instance, by arguing that the distribution at time T+i is close to uniform with respect to the initial state anyways. This leads to question 3 below...

3) Is there some class of Markov chains for which alternative 2 is enough?

# Answer
One correct way is to repeat the following 10 times: pick a random starting state, and apply the Markov chain for $T$ steps.

I don't know whether your first proposal gives the correct distribution in all cases. You can consider the Markov chain $A \leftarrow B \rightarrow C$ with self-loops $A \to A$ and $C \to C$ and more complicated examples in that vein.

Your second proposal doesn't give the correct distribution. The $T$th and $T+1$th state are highly correlated: for instance, they will always be adjacent -- something that wouldn't be true of 10 independent samples from the steady state distribution.
> 1 votes

---
Tags: markov-chains
---


# Question
Title: Finding a solution to a satisfiable formula
I know that it is as hard to find a solution to a SAT formula, as it is to decide it has a solution at all. See the answer to: Is finding a solution of a satisfiability problem harder than deciding satisfiability?

Are there also families of formulas for which it is guaranteed that there is a solution, but it is hard to find one?

# Answer
> 1 votes
Absolutely, a hash function is a prime example of a function (which can be modelled by a very complex binary formula of its inputs) where it is easy to find the output given an input, but finding an input which matches an output is very hard.

But since we generated the original output we know that there must be a solution.

This construction requires the ability to forget information (the original input) however.

# Answer
> 1 votes
We don't know if any families of SAT formulas are hard since we don't yet know if P and NP are distinct complexity classes.

Schaefer's dichotomy theorem gives six families of formulas that are known to be *easy*.

SAT formulas based on reductions from hard cryptography problems are assumed to be hard for the same reason the source problem is hard. Since a crypto problem involves finding a key that's known to exist, the resulting SAT instances will have at least one satisfying assignment even though such instances are probably hard.

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


# Question
Title: weight constrained shortest path problem variants
Given a graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:E\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V\_{p},E\_{p})$ such that $\sum\_{e\in E\_{p}} w(e) \leq W$ and $\sum\_{e\in E\_{p}} \delta(e) \leq K$, where $W,K\in Z^{+}$.

This is Weight constrained Shortest Path Problem, and known to be NP-complete for undirected as well as directed even acyclic graphs. as long as $\delta$ and $w$ is not equal for all edges. Now if we move weight from edges to vertices and change $\leq$ of total weight constraint to $=$ then the new problem is:

Given a directed acyclic graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:V\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V\_{p},E\_{p})$ such that $\sum\_{v\in V\_{p}} w(v) = W$ and $\sum\_{e\in E\_{p}} \delta(e) \leq K$.

Is this problem known ? is this solvable in P time ? or this is NP-complete too ? I think even if we replace $\mathbb{Z}^{+}$ with $\mathbb{R}^{+}$ it will not change nature of the problem.

If we set $W=\vert V \vert$ then it tries to reach all the vertices which looks like hamiltonian path problem, but it is a DAG.

## Update

I was trying to reduce it from Subset Sum as suggested by @D.W.

Given $X=\\{1,2,3\\}$ of size $\vert X \vert = n$ I can convert that to a graph of $n^{2}+n+2$ vertices. We can make $n$ layers of $X$ and connect every vertex with all vertices of next layer except itself. Keep a vertex with 0 weight on each layer. As show below.

But this reduction has 2 restrictions.

1. Every Layer is not complete bipartite (e.g. $2\_{i}$ does not connect to $2\_{i+1}$).
2. Every layer must have a vertex with 0 weight.

Now this does not prove the second problem for General purpose DAG. I can not connect $x\_{i}\rightarrow x\_{i+1}$ because that will change the original problem. So if there is a DAG that looks very similar to this one but have $n^{2}$ edges between each layer and have no 0 weight vertex this reduction does not apply to that graph.

**Also in this formulation I can take the same element twice $1\_{1}\rightarrow 2\_{2}\rightarrow 1\_{3}$ which will add to $4$. Which I should not be allowed**

# Answer
Check the definition of reduction again. A reduction that works for general dags *is* a perfectly valid reduction. It meets all of the conditions in the definition. I suggest working through the definition -- that should help you see what is going on.

Or, to put it another way: The problem for "general DAG" is at least as hard as the problem for "a particular type of DAG", so if you've proved the problem is NP-hard for a particular type of DAG, you've also proven it is NP-hard for general DAGs, too.
> 1 votes

---
Tags: complexity-theory, graphs, np-complete, shortest-path
---


# Question
Title: Confused about XORing and addition modulo $2$
It's my understanding that when you XOR something, the result is the sum of the two numbers mod $2$.

Why then does $4 \oplus 2 = 6$ and not $0$? $4+2=6$, $6%2$ doesn't equal $6$. I must be missing something about what "addition modulo 2" means, but what?

> 100 // 4
>
> 010 // XOR against 2
>
> 110 = 6 // why not zero if xor = sum mod 2?

# Answer
The confusion here stems from a missing word. A correct statement is "The result of XORing two **bits** is the same as that of adding those two **bits** mod 2."

For example, $(0+1)\bmod 2 = 1\bmod 2 = 1=(0\text{ XOR }1)$

and

$(1+1) \bmod 2= 2\bmod 2 = 0 =(1\text{ XOR }1)$
> 26 votes

# Answer
The xor of two one-bit numbers is their sum modulo 2. But the xor of two $n$-bit numbers can't possibly be their sum modulo 2: any value modulo 2 is either zero or one but the xor of two $n$-bit numbers could be anything between 0 and $2^n-1$, inclusive.
> 4 votes

# Answer
You are confusing operations on a single bit with operations on a byte,or word.(Multiple bits) A single bit represents either 0 or 1 depending on its value. If you add two bits, and ignore the carry, you are adding "mod2". 0+0 = 0 0+1 = 1 1+0 = 1 1+1 overflows, or carries, and you have 0

this is exactly the same as XOR

However it is NOT true for words. Consider a nibble (4 bits) 0110 + 0111 = 6 + 7 = 13 = 1101 0110 xor 0111 = 0001 = 1
> 4 votes

# Answer
I think you're misunderstanding the property.

I believe that property is more concerned with the boolean result of the XOR function, not the numeric value. What I mean is that each "number" you're adding is actually just a boolean value of True (1) or False (0) and adding those together, mod 2, is the same as XOR of those values.

This page may clear that up further: The Magic of XOR
> 1 votes

---
Tags: arithmetic
---


title: relational algebra to get unique pairs

text:
# Question
Title: relational algebra to get unique pairs
Let's say we are given this table of the relation Person(name, hobby)

```
name   hobby
bob    hockey
alice  basketball
mary   cricket
mark   basketball
rick   snowboarding
andy   hockey

```

How would I use relational algebra to find the hobby that had only one person had.

It should give me

```
hobby
cricket
snowboarding

```

My ATTEMPT:

$R1 := \rho\_{P2}(Person)$

$R2 := R1 \bowtie\_{P2.hobby = P1.hobby \text{ } AND \text{ } P2.name \<\> P1.name} R2$

$R3 := \pi\_{hobby} (R2)$

# Answer
You need more carefully defined $\theta$-join and then set difference:

$$R1 := \rho\_{name1/name,hobby1/hobby}(Person)$$ $$R2 := Person \bowtie\_{(hobby=hobby1) \land (name \neq name1)} R1$$ $$R3 := \pi\_{hobby}(Person) \setminus \pi\_{hobby}(R2)$$
> 1 votes

---
Tags: relational-algebra
---


# Question
Title: what is the 'x :=' part mean in a hoare triple?
In Hoare logic, there's a thing called a *Hoare triple*, e.g.$$ \begin{array}{ccccc} \\{x = 2\\} & & x := x+1 & & \\{x = 3\\} \end{array}. $$ What does '$x :=$' mean?

# Answer
Short answer, it's an assignment, but it's not part of Hoare logic.

It means whatever it means in the programming language you're using.

A Hoare triple in general looks like $\\{P\\}\\; C\\; \\{Q\\}$ (stolen from the all-knowing wiki), where:

* $P$ and $Q$ are assertions about the state of the system before and after $C$ is executed; and
* $C$ is some piece of code.

So the meaning of $x :=$ depends entirely on the semantics of the code.

Assuming someone hasn't written this as a trick, $:=$ is usually used as an assignment operator (to avoid confusion with $=$ as equality), so in this case the line should be read as $x := x + 1$, i.e., the line of code is incrementing the variable $x$.

If the triple were written in a C-like language, you could write it as $\\{x=2\\}\\; x=x+1;\\; \\{x=3\\}$, or similarly in your favourite language.
> 4 votes

---
Tags: notation, hoare-logic
---


# Question
Title: How to minimally extend a digraph such that all nodes are on a cycle?
Let's say we have a directed graph with $n$ nodes and $m$ edges. For each node we want to make path that will start from this node, possibly traverse some other nodes and finish in the same node, in other words we want to make a cycle through each node. It is allowed to add edges that start and finish in the same node.

We want to use minimum number of edges.

Let's for example consider the following graph. We can add edges: $(1,1),(2,2),(3,3),(4,4)$. But that will cost us to add 4 edges, and we can make the cycles with adding only one edge $(4,1)$.

I think that first we should find all the paths in the graph, and then link the last node with the first node, this will allow us to minimize the added edges, and surely will make all the nodes in the path linked in the cycle.

But the problem is find all the paths, I cannot think of the algorithm that will find us all pairs of paths, also the problem is if there is more than one path between the first and the last nodes, please give me some hints on how to solve this problem.

Also, I think that finding all paths in the graph is $NP-hard$ and it may be really slow, but the number of nodes is small, less than 20, so even solution of time complexity $O(2^N)$ are good.

# Answer
> 4 votes
* Find all the strongly connected components (SCC) of the original graph.
* Replace each SCC by a single node - the resulting graph $G'$ will be *acyclic*.
* Find all the *sources* and *sinks* in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
* Match sinks with sources using algorithm by Eswaran and Tarjan (see here), corrected by Raghavan (see here), then add $max(m,n)$ edges for all the matched (sink, source) pairs.
* Replace each node, representing SCC, by this SCC.

This approach will give you a strongly connected graph provided that the original graph is connected. Your requirement to have all the nodes belonged to some cycle is more weak - for example, a set of SCC's, not connected at all or connected by single edges, satisfies your goal definition.

However, it's unclear if this more weak requirement will allow you to decrease the number of additional edges compared to the number of additional edges, given by the algorithm, described here.

---
Tags: graphs, graph-traversal
---


# Question
Title: How can I solve a recursive equation with a summation notation?
Consider the following formula:

$T(n) = n + \sum\_{k=1}^{n-1} \[T(n-k) + T(k)\], T(1) = 1$

What is the order of T?

# Answer
I'm assuming that the recurrence is $$ T(n) = n + \sum\_{k=1}^{n-1} \[T(n-k) + T(k)\], $$ with base case $T(1) = 1$.

First, notice that $$ \begin{align\*} T(n) &= n + \[T(n-1) + \cdots + T(1)\] + \[T(1) + \cdots + T(n-1)\] \\ &= n + 2\[T(1) + \cdots + T(n-1)\]. \end{align\*} $$ Similarly, $$ T(n-1) = n-1 + 2\[T(1) + \cdots + T(n-2)\]. $$ Subtracting, we obtain $$ T(n) - T(n-1) = 1 + 2T(n-1), $$ and so $T(n) = 1 + 3T(n-1)$. Now let $S(n) = T(n) + 1/2$. Then $$ S(n) = T(n) + 1/2 = 1+3(S(n-1)-1/2)+1/2 = 3S(n-1). $$ Since $S(1) = T(1) + 1/2 = 3/2$, we conclude that $S(n) = 3^n/2$, and so $$ T(n) = \frac{3^n-1}{2}. $$
> 4 votes

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Big-O complexity of finding exception handler for zero-cost exceptions
I am wondering what the time complexity of finding the most appropriate exception handler for dispatching zero-cost exceptions is.

For zero-cost (this refers to execution under the assumption that no exceptoins occur) exception dispatching, the compiler stores a big table of all possible exceptions. An entry consists of Type, Handler, start+end of the try-block.

Then one can find the most appropriate handler by

1. taking those with a try-block enclosing the address where the exception occured
2. then of those, choosing the most specific type
3. if one is found: done, else: move up the callstack

Naively I would say: O(callstacksize * sizeoftable).

But we have to be able to do better. I looks to me the callstacksize factor wont go away, but what about the sizeoftable factor?

There should be more performing way to search through the handlers. What is the best we can do O-notation-wise?

# Answer
> 1 votes
The crucial data structure here is an *interval tree*, that can be pre-computed at compile time, which has a complexity of $O(\log n + k)$ to find all $k$ ranges that contain a certain point, assuming there are a total of $n$ ranges. Here your ranges are exception blocks in the compiled code and your point is the instruction address.

I will assume the C++ model of one try block followed by one or more catch blocks that may or may not match a thrown exception and I will assume that a compiled program has $n$ try blocks in total.

Then when an exception is thrown it takes $\log n$ time to find the $k$ relevant try blocks in the current call frame (which we order by specificity, which is done by minimizing range size). And for each relevant try block there may be one or more relevant catch block, which may or may not match. If none match we go to our caller and search again.

But at some point we find a matching exception (or halt). The total complexity then is $O(c\log n + k)$, where $c$ is the number of calling frames we had to go up, and $k$ is the total number of relevant catch blocks that we considered for matching.

This is assuming that you do exception type matching at runtime, instead of maintaining separate tables per exception type. Since $k$ is generally very small, this is a sensible approach. You can get better asymptotic runtimes in terms of $k$, but I described a practical approach.

---
Tags: algorithms, complexity-theory, data-structures, time-complexity, compilers
---


# Question
Title: How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$
I see many algorithmic problems that always reduce to something a long the lines of:

You have an **integer** array $h\[1..n\]\geq 0$, you need to find $i,j$ such that maximizes $(h\[j\]-h\[i\])(j-i)$ in $O(n)$ time.

Obviously the $O(n^2)$ time solution is to consider all pairs, however, is there any way we can maximize the expression in $O(n)$ without knowing something else about properties of $h$?

One idea I thought of is to fix $j$, then we need to find $i^\*$ from $1$ to $j-1$ that is equal to $\text{argmax}\_i\\{(h\[j\]-h\[i\])(j-i)\\}$ or $\text{argmax}\_i\\{h\[j\]j-h\[j\]i-h\[i\]j+h\[i\]i\\}$ and since $j$ is fixed, then we need $\text{argmax}\_i\\{-h\[j\]i-jh\[i\]+ih\[i\]\\}$.

However, I see no way of getting rid of the $j$ dependent terms inside. Any help?

# Answer
---

This is an $O(n\log n)$ solution. An $O(n)$ solution pointed out by Willard Zhan is appended at the last of this answer.

---

# $O(n\log n)$ solution

For convience, denote $f(i,j)=(h\[j\]-h\[i\])(j-i)$.

Define $l\_1=1$, and $l\_i$ be the smallest index such that $l\_i\>l\_{i-1}$ and $h\[l\_i\]\<h\[l\_{i-1}\]$. Similarly, define $r\_1=n$, and $r\_i$ be the largest index such that $r\_i\<r\_{i-1}$ and $h\[r\_i\]\>h\[r\_{i-1}\]$. The sequences $l\_1,l\_2,...$ and $r\_1,r\_2,\ldots$ are easy to compute in $O(n)$ time.

The case where there are no $i\<j$ such that $h\[i\]\< h\[j\]$ (i.e. $f(i,j)\>0$) is trivial. We now focus on non-trivial cases. In such cases, to find the solution, we only need to consider such pairs.

For each $i\<j$ such that $h\[i\]\<h\[j\]$, let $u$ be the largest index such that $l\_u\le i$, and $v$ be the smallest index such that $r\_v\ge j$, then $h\[l\_u\]\le h\[i\]$ (otherwise $l\_{u+1}\le i$ by definition of $l\_{u+1}$, thus contradicts to the definition of $u$), and similarly $h\[r\_v\]\ge h\[j\]$. Hence $$(h\[r\_v\]-h\[l\_u\])(r\_v-l\_u)\ge(h\[j\]-h\[i\])(r\_v-l\_u)\ge(h\[j\]-h\[i\])(j-i).$$ This means we only need to consider pairs $(l\_u,r\_v)$ where $l\_u\<r\_v$.

Denote $v(u)=\arg\max\_{v:\ l\_u\<r\_v}f(l\_u,r\_v)$, we have the following lemma.

> A pair $(l\_u,r\_v)$ where $l\_u\<r\_v$, and where there exists $u\_0$ such that $u\<u\_0$ and $v\<v(u\_0)$ or such that $u\>u\_0$ and $v\>v(u\_0)$, cannot be a final optimum solution.
>
> ***Proof.*** According to the definition of $v(u\_0)$, we have $$ (h\[r\_{v(u\_0)}\]-h\[l\_{u\_0}\])(r\_{v(u\_0)}-l\_{u\_0}) \ge (h\[r\_v\]-h\[l\_{u\_0}\])(r\_v-l\_{u\_0}), $$ or $$ (h\[r\_v\]-h\[r\_{v(u\_0)}\])l\_{u\_0}+h\[l\_{u\_0}\](r\_v-r\_{v(u\_0)})+h\[r\_{v(u\_0)}\]r\_{v(u\_0)}-h\[r\_v\]r\_{v(u\_0)} \ge 0. $$
>
> In the case where $u\<u\_0$ and $v\<v(u\_0)$, note $h\[r\_v\]-h\[r\_{v(u\_0)}\]\<0$ and $r\_v-r\_{v(u\_0)}\>0$, and also $l\_u\<l\_{u\_0}$ and $h\[l\_u\]\>h\[l\_{u\_0}\]$, we have $$ \begin{align\*} &(h\[r\_v\]-h\[r\_{v(u\_0)}\])l\_u+h\[l\_u\](r\_v-r\_{v(u\_0)})\\ \>\ &(h\[r\_v\]-h\[r\_{v(u\_0)}\])l\_{u\_0}+h\[l\_{u\_0}\](r\_v-r\_{v(u\_0)}). \end{align\*} $$
>
> This means $$ (h\[r\_v\]-h\[r\_{v(u\_0)}\])l\_u+h\[l\_u\](r\_v-r\_{v(u\_0)})+h\[r\_{v(u\_0)}\]r\_{v(u\_0)}-h\[r\_v\]r\_{v(u\_0)} \> 0, $$ or $$ (h\[r\_{v(u\_0)}\]-h\[l\_u\])(r\_{v(u\_0)}-l\_u) \> (h\[r\_v\]-h\[l\_u\])(r\_v-l\_u). $$
>
> So $(l\_u,r\_{v(u\_0)})$ is a strictly better solution than $(l\_u,r\_v)$. Proof for the other case is similar. $\blacksquare$

We can compute $v(\ell/2)$ firstly where $\ell$ is the length of the sequence $l\_1,l\_2,\ldots$, then **recursively** compute the optimal solution $o\_1$ among $(l\_u,r\_v)$'s for $u=1,\ldots,\ell/2-1$ and $v=v(\ell/2),v(\ell/2)+1,\ldots$, and the optimal solution $o\_2$ among $(l\_u,r\_v)$'s for $u=\ell/2+1,\ell/2+2,\ldots$ and $v=1,\dots,v(\ell/2)$. Due to the lemma, the global optimum solution must come from $\\{(l\_{\ell/2},r\_{v(\ell/2)}),o\_1,o\_2\\}$.

---

# $O(n)$ Solution

Let $f(l\_u,r\_v)=-\infty$ if $l\_u\ge r\_v$. The proof of the lemma also shows an important property: for $u\>u\_0$ and $v\>v\_0$, if $f(l\_{u\_0},r\_{v\_0})\ge f(l\_{u\_0},r\_v)$, then $f(l\_u,r\_{v\_0})\>f(l\_u,r\_v)$. This means the matrix $M\[x,y\]:=-f(l\_x,r\_{c-y+1})$ is a totally monotone matrix where $c$ is the length of the sequence $r\_1,r\_2,\ldots$ (so $r\_{c-y+1}$ means the $y$-th element from the end), then SMAWK algorithm can apply to find the minimum value of $M$, thus the maximum value of $f$.
> 5 votes

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


title: Number of ways to make $n$ cents

text:
# Question
Title: Number of ways to make $n$ cents
How to find a recurrence relation for $F(n)$ the number of ways to make n cents change using only pennies (4 cents), nickels(5cents), and dimes(10cents) and ordering matters.

There are three exclusive case here

1. Start with pennies then new subproblem is $F(n-4)$
2. Start with nickels then new subproblem is $F(n-5)$
3. Start with dimes then new subproblem is $F(n-10)$

$$F(n) = F(n-4)+ F(n-5) + F(n-10) $$

Is there any other way to solve this problem. The above method is ok but seems like magic to beginner. Is there any systematic approach to solve this problem?

Problem is also available on https://math.stackexchange.com/questions/248853/how-to-find-recurrence-relation-for-this-problem

# Answer
If we try to apply your recurrence to $n = 9$ and add the base case $F(0) = 1$, then we get $F(9) = 2$. Now this *might* be the answer you want, since there are indeed two possibilities: penny+nickel and nickel+penny, but usually we consider these the same.

There are two ways to proceed if we want to compute the number of ways without regard to order. The first way is to consider three different functions $F,G,H$ which correspond to using all coins ($F$), only nickels and dimes ($G$), and only dimes ($H$). The recurrences are $$ F(n) = F(n-4) + G(n-5) + H(n-10), \\ G(n) = G(n-5) + H(n-10), \\ H(n) = H(n-10), $$ with initial conditions $F(0) = G(0) = H(0) = 1$ and $F(m) = G(m) = H(m) = 0$ for negative $m$. This gives a joint linear recurrence for the triplet $F(n),G(n),H(n)$.

The other approach is to use generating functions, which give us the following expression: $$ \sum\_{n=0}^\infty F(n) x^n = \frac{1}{(1-x^4)(1-x^5)(1-x^{10})} = \frac{1}{1-x^4-x^5+x^9-x^{10}+x^{14}+x^{15}-x^{19}}. $$ This shows that the sequence $F(n)$ satisfies the recurrence $$ F(n) = F(n-4) + F(n-5) + F(n-10) \\\- F(n-9) - F(n-14) - F(n-15) + F(n-19) $$ with initial conditions $F(0) = 1$ and $F(m) = 0$ for negative $m$.

This can be seen as a kind of inclusion/exclusion principle — I'll let you work out the details.
> 4 votes

# Answer
That **is** the systematic way of solving this kind of question. Generally trying to find a recurrence is one of the possible first steps of solving combinatoric problems.

Note that in order for the recurrence to be efficient you have to use memoization, remembering previous $F$ that you calculated, this is (somewhat poorly) called dynamic programming.
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: Can quick sort time complexity be $\Theta(n\sqrt n)$ for some inputs?
I know that the time complexity of quick sort in the worst case is $\Theta(n^2)$ and in the average case is $\Theta(n \log n)$. Can it be $\Theta(n\sqrt n)$ for certain inputs?

# Answer
Assume the array is sorted. If you always pick the element at n/2 as pivot then the time is O(n log n). If you always pick the first or last element it’s $O(n^2)$.

So which pivot gives you $O(n^{1.5})$?
> 3 votes

---
Tags: time-complexity, quicksort
---


# Question
Title: Some points about type checking of simply typed $\lambda$-calculus?
# type checking

I was preparing examples of type checking in simply typed $\lambda$-calculus. I wanted to explain it to my audience in the way of implementation. And I found a bit tricky point in the typing rule of application, which is as follows.

$$ \frac {\Gamma \vdash t\_1:T\_{11}\rightarrow T\_{12} \quad \Gamma \vdash t\_2:T\_{11}} {\Gamma \vdash t\_1 \\, t\_2 :T\_{12} } $$

$$ \frac {\Gamma, x:T\_1 \vdash t\_2 :T\_2} {\Gamma \vdash \lambda x:T\_1.t\_2 : T\_1 \rightarrow T\_2} $$

Typing rules for booleans are:

$$ \frac {} {\Gamma \vdash \texttt{true}: bool } $$

$$ \frac {} {\Gamma \vdash \texttt{false}: bool } $$

## My question

As far as I know, we do not need unification for type checking in the typed $\lambda$-calculus, we need unification in type inference. However, the following type checking example seems that we need something like unification, also it seems that type checking is leading to type construction.

$$ \frac { \vdash \lambda x:bool.x: T \rightarrow bool \quad \vdash \text{true}: T} { \vdash (\lambda x:bool.x) \text{ true}: bool } $$ Here, $T$ is unknown type variable. It is easy to saying that $T$ is $bool$ because of the boolean typing rules, so we can continue the left branch of the above type checking as follows.

$$ \frac {x:bool \vdash x:bool} { \vdash \lambda x:bool.x: bool \rightarrow bool } $$

The premise is true, so the type checking is successful.

But how do we know the value of $T$ in an implementation? It should take matching $ true:bool$ to $true: \text{T}$ to know $T$ is $bool$. But this seems unification to me.

Also, finding $T$ for $\Gamma \vdash t: T$ is a type inference problem. So, the above type checking is leading to type inference. Am I correct?

Does type checking of the simply typed $\lambda$-calculus need unification?

Does type inference appear when doing type checking?

Please correct me if I am wrong at any point and explain.

# Other info

Type checking of ${ \vdash (\lambda x:bool.x) \text{ true}: bool }$ is given as an example in the book "types and programming languages", page 103. However, it did not specify how $T$ is obtained. Its derivation concluded $T$ is $bool$ when using the typing rule of application, as shown below.

$$ \frac { \vdash \lambda x:bool.x: bool \rightarrow bool \quad \vdash \text{true}: bool} { \vdash (\lambda x:bool.x) \text{ true}: bool } $$

I believe these details are ignored in the book.

# Answer
> 6 votes
Your example is poorly chosen. In $(\lambda x : \mathsf{bool} . x) \\, \mathsf{true}$ you can obviously read off the type from the $\lambda$-abstraction because it tells you that $x$ should have type $\mathsf{bool}$. A more relevant example is $$ ((\lambda f : \mathsf{bool} \to \mathsf{bool} . f) (\lambda x : \mathsf{bool} . x)) \\, \mathsf{true} : \mathsf{bool} $$ Now we are faced with determining $T$ by looking at $(\lambda f : \mathsf{bool} \to \mathsf{bool} . f) (\lambda x : \mathsf{bool} . x)$.

The usual algorithm to be used for this sort of thing is bidirectional typechecking: some terms have their types checked but others have their types inferred. No unification is required, because all types are inferred immediately. (Unification happens when we postpone decisions until a later time.)

---
Tags: lambda-calculus, type-theory, types-and-programming-languages
---


# Question
Title: What is the complexity of calling a trivial hash function $n$ times?
The cost of computing a trivial hash function is effectively zero, so the time complexity is $\mathcal{O}(1)$; however, if I assign $n$ variables using the hash function, is the complexity $\mathcal{O}(n)$.

For example, the pseudo code would look like this:

```
for i=1 to n
   var[i] = hash[data[i]];
end

```

The only operation that is being performed is the assignment operation, but in complexity theory, it seems that the assignment operation is not usually included in defining the complexity.

# Answer
> 2 votes
Your question is ill-defined, and it's precisely that that I believe to be your misunderstanding.

There isn't an inherent cost in Landau notation, or any complexity analysis measure for that matter. You first need to define a *model*, by defining exactly what consists of an operation.

For example you could model only assignments, in which case the complexity is $n$. You could also model only hash function calls, in which case the complexity is also $n$. Or you could consider both to be one unit of time, in which case the complexity is $2n$.

Or perhaps your hash function is $100$ times slower than an assignment, which we assign cost $1$. Then your complexity would be $101n$.

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


title: 2-way set associative cache exercise

text:
# Question
Title: 2-way set associative cache exercise
In the exercise I have a 32 bit processor with a 2-way set associative cache. I have 32 bit addresses: 31-14 tag, 13-5 index, 4-0 offset.
Calculate:
1) Cache line size in number of words (1 word = 4 bytes)
2) Total cache size in bits

In the presence of the following sequence of accesses in memory, considering the initially empty cache, indicate for each access if it is hit, miss, or replace:
17920 17948 149024 83488 17952 148998 149012 17964 148648 17848

I think answer at the first part should be:
1) 2^5 = 32byte --\> 32/4 = 8words
2) 32byte = 256bit --\> size = 256 * (4096 + 18 + 1)

Is it correct? And I'm not sure on how to complete the second part of the exercise

# Answer
You have 5 bits for the offset. Assuming byte addressed memory, you'll need four memory addresses to construct a word. So take two bits from the offset. Now you are left with 3 bits in the offset, hence a cache line would have 8 words.

9 bits for have been used for the index, therefore 2^9 cache blocks are present. Since its a two way assoc, each block contains 2 cache lines.

```
data storage =
(2^9 cache blocks
* 2 cache lines in a block
* 8 words per cache line
* 32 bits in a word) bits
= 262,144 bits

```

Now the rest is bit tricky as the question does not provide what other bits are available. Assuming there is a valid bit present,

```
per cache line we need 1 bit for valid bit + 18 bits of tag data = 19 bits of "meta" data

512 cache blocks * 2 lines per block * 19 bits = 19,456
So the total size in bits = 262,144+ 19,456 = 281,600

```

If there is also a dirty bit present, equations changes to

```
 per cacheline,
 1 bit for valid bit + 1 bit for dirty bit + 18 bits of tag data = 20 bits of "meta"data

```

For the second part, get the binary representation of the address. Break it into tag, index and the offset. Fill up the cache based on the tag and the index. See what happens.
> 1 votes

---
Tags: computer-architecture, cpu-cache
---


title: how to solve Hoare logic problems

text:
# Question
Title: how to solve Hoare logic problems
I'm having trouble proving Hoare logic questions as I'm not sure of the process that is taken to prove them. I understand that they're rules such as assignment axiom, pre-condition strengthening, post-condition weakening etc... but how you actually apply these rules to the question is a little out of my understanding.

Cheers

# Answer
Here is the *idea* behind proving this triple. Let us denote by $s\_0,i\_0$ the values before the block, and by $s\_1,i\_1$ the values after the block. We are given that $s\_0 = 2^{i\_0}$, and furthermore it is clear that $i\_1 = i\_0 + 1$ and $s\_1 = 2s\_0$. But then $$ s\_1 = 2s\_0 = 2\cdot 2^{i\_0} = 2^{i\_0+1} = 2^{i\_1}. $$ Whether this constitutes a proof of not depends on your normative environment.
> 1 votes

# Answer
Usually one starts from the postcondition ($s=2^i$ in your example) and tries to compute a (weakest) precondition, walking the code *backwards*. At the very last step, after having computed a precondition for the whole code, one tries to strengthen it to obtain precisely the given precondition, completing the task.

For instance, starting from $s=2^i$, we can find a precondition for `s:=s*2`, which according to the assignment rule is $(s=2^i)\\{s\*2/s\\} = (s\*2=2^i)$. This must, in turn, be the postcondition to `i:=i+1`, so we repeat the process, using the assignment rule once again.

You should now get the idea, at least for chains of assignments.

For conditional it is a bit more complex. For loops, it is far more complex, and requires finding a suitable invariant. There is no general automatic procedure to infer a loop invariant, similarly to how there is no general automatic procedure to find a mathematical proof. Still, in many cases, it is possible to guess a working invariant -- how to do so, at least in common cases, is a skill that (arguably) each computer scientist should learn, especially when focusing on program verification or algorithms.
> 1 votes

---
Tags: logic, propositional-logic, hoare-logic
---