# Question
Title: Internal tangent intersection of two point sets in linear time
I need to find the intersection of the internal tangents of two point sets $V\_a, V\_b$ in $\mathbb{R}^2$, defined via their convex hulls. We can assume that the sets are disjoint and linearly separable, so I think the internal tangents are uniquely defined as the two lines which are tangent to each of the convex hulls of the sets, such that each set is on a different side. This is the point marked green here:

This paper ("Computing Plurality Points and Condorcet Points in Euclidean Space") I'm currently reading (paywalled, unfortunately...) says in a sort of side note that this problem can be solved using linear programming, in linear time in the number of points, but doesn't describe how.

For constructing a linear program, I thought about describing lines by $F(x, y) = ax + by + c= 0$, and optimizing a function of $a, b, c$. Then the obvious constraints would be $\forall v \in V\_a: av\_x + bv\_y + c \geq 0$ and the according thing for $V\_b$, to force the lines to go between the two sets.

But now I am stuck. For one, we need to constrain the space of lines somewhat; $\lVert (a, b) \rVert = 1$ would be natural to require, but that's not linear. Also, I'm not sure about the cost function; I thought about using

$$\min\_{a,b,c} \sum\_{v\in V\_a} F(v\_x, v\_y) - \sum\_{v\in V\_b} F(v\_x, v\_y),$$

since $F$ is somehow a distance from the line (although not in the strict sense, I guess). But that is just guessing and also doesn't work -- I tried some things like I described in JuMP, but it always returned "infeasible".

How can this be formluated as a linear program? Alternatively, I can accept an algorithmic solution with linear time. Or a disproof, of course.

# Answer
I found a way to solve the problem in my case -- maybe that only applies to the special conditions found in the paper. There, the two point sets can be assumed to be non-collinear and always separable by a line parallel to one of the coordinate axes, and we always know that $A$ is "left of" (or "above") $B$.

In this case, we can represent a line simply by $y = kx + d$, and get one internal tangent by minimizing the function $F(k, d) = k$ subject to $$ \forall v \in A: v\_y \leq k v\_x + d\\ \forall v \in B: v\_y \geq k v\_x + d. $$ The other one can be found by swapping $A$ and $B$ (or the relations) and maximizing.
> 2 votes

---
Tags: computational-geometry, linear-programming, convex-hull
---


# Question
Title: What is the most recent comparison of signature files and inverted indices?
Modern papers on search indices often contain a statement that inverted indexes (posting lists) are categorically superior to signature files (bloom filters). Here are some examples from papers published in 2016:

> While this \[signature file\] technique provides a relatively low computation overhead, studies by Zobel et al. \[1998\] have shown that inverted files significantly outperform signature files.
>
> Inverted indexes have been benchmarked as the most generalisable, and well performing structure (Zobel et al., 1998)

Every paper seems to cite Zobel et al., Inverted files versus signature files for text indexing.

However, if I'm reading Zobel et al. correctly, the argument they make isn't fundamental (e.g., an asymptotic bound or an information theoretic limit). Rather, the argument seems to be, given signature files implemented with techniques X, Y, and Z compared to inverted indices implemented with techniques A, B, and C, and the current technology of the day (disks with very high seek/access overhead), inverted indices are superior because they require fewer seeks and there are faster.

Is there a more recent comparison that compares these techniques on SSD, NVMe, or RAM, or is there a more recent comparison that looks at "new" techniques that have been invented since 1998?

# Answer
Don't know any fresh references.

Off the top of my head:

Signature files require candidate verification via forward files. This requires lots of random accesses, basically one per potential match. One random memory access is 100+ CPU cycles. You can do a lot of work in 100 CPU cycles (e.g., you can decompress more than 100 IDs single core http://boytsov.info/pubs/simdcompressionarxiv.pdf).

Random access speed is even worse in the case of HDD or even SSD. There is in fact a growing gap between random and sequential access speed.

Before making this random access you cannot do pruning, early-termination, etc... BTW, for the most fancy recent data structure, you should probably check partitioned Elias-Fano indices: http://pages.di.unipi.it/rossano/wp-content/uploads/sites/7/2015/11/sigir14.pdf
> 1 votes

---
Tags: reference-request, information-retrieval, search
---


# Question
Title: What is 'real time' in a Computer Vision context?
Suppose you have a program which works on a stream of images. It gets an image, makes edits and stores the image. What is the maximum latency with which one can still speak of a "real time application"? (Please give a source in your answer)

# Answer
> 3 votes
There is no one answer to this question. "Real time" can mean very different things, depending on what kind of sensor or sensors you are using, and what you are trying to do. By the way, editing and storing images may not even qualify as computer vision. Computer vision is about extracting information from images or video, and the meaning of real time depends on the kind of information you are trying to extract.

A typical video camera acquires images at 30 frames per second (fps). So that can be your definition of "real-time", i.e. being able to process images at the rate at which you acquire them.

On the other hand, if your goal is to detect and track objects in videos, then "real-time" is a function of how fast those objects move. For example, 10fps is often sufficient for tracking people walking on the street, but probably not for tracking cars going 70 miles per hour on a highway.

# Answer
> 3 votes
In computer science, a real-time computing (RTC) system is one that guarantees a response before a previously set deadline. For a stream of images, that implies that a real-time system is one that guarantees it has finished processing each image before some previously set timing constraint on latency.

There is no 'maximum latency with which one can still speak of a "real time application"'. Each real-time system has its own fixed maximum latency, that generally differs from the maximum latency of other real-time systems.

> RealTime is simply about meeting timing constraints. Those timing constraints might be microseconds, or might be hours. -- http://wiki.c2.com/?NearRealTime

and

> EmbeddedSystems engineers use exactly one definition of real time, and that is this: A real time system employs tasks which execute to completion in a guaranteed amount of time. -- http://wiki.c2.com/?RealTime

and

> real-time systems... have to provide results which are not only correct, but also delivered in time. Instead of average behavior as for standard computing, real-time systems have to allow for guarantees that the temporal requirements will be met. -- http://www.ecrts.org/

and

> Real-Time System: is a computing system whose correct behavior depends not only on the value of the computation but also on the time at which outputs are produced. -- http://sites.ieee.org/tcrts/education/terminology-and-notation/

and

> "In soft real time applications, system can miss the dead line without causing failure of the overall system. As an example ... losing a video frame will not fail ..." -- p. 356 "Computer-Based Industrial Control"

and

> "Common miconceptions: ... Real-time computing is equivalent to fast computing? ... Rather than being fast ... the most important property of a real-time system should be predictability. ... Predictability, not speed, is the foremost goal in real-time-system design." -- John Stankovic. "Misconceptions about Real-Time Computing: A Serious Problem for Next-Generation Systems". 1988.

If you have a subsystem that can only handle one frame of video at a time, and video is streaming in at 30 frames per second and cannot be buffered, then to meet real-time constraints that subsystem must handle each frame in 1/30 of a second or less to qualify as a real-time system.

However, often there is a pipeline of such subsystems, each one doing its job in 1/30 of a second or less, but the total end-to-end latency from a frame of video introduced into one end to the results at the other end is a full second or more, and yet such a pipeline still qualifies as real-time when it is guaranteed to meet all its timing constraints.

# Answer
> 0 votes
The definition of Real-Time is usually dependent on some requirement for your system. Some systems might deem Real-Time as 10Hz, some might think 1Hz, etc. However, the rate at which your system needs to operate is often the upper bound of how fast some algorithms, Computer Vision or something else, need to run. So if your system needs to operate at 15Hz, you should expect your Computer Vision (or other) algorithms need to be faster than 15 Hz.

---
Tags: computer-vision, real-time
---


title: How to evaluate relations in a DAG?

text:
# Question
Title: How to evaluate relations in a DAG?
To begin with: what I know of computer science is what friends have told me and what I've read on Wikipedia. Please correct me if I'm using some term wrongly, or if there is something I can clarify.

Let's say I have a directed graph. I want my computer to look at it, and see whether x \> y, y \> x, or if the relationship between x and y is unknown.

**Linear graph**

If the graph looks kind of like this it's an easy task:

Just let a = 4, b = 3, c = 2, and d = 1. I can evaluate if a \> c by comparing 4 and 2, and the result will be correct.

**Tree graph**

Now it gets interesting.

Here we have a tree graph. This kind of hierarchical data is discussed by Bill Karwin in these slides, which outlines four different ways of storing hierarchical data in a relational database. You can see a summary table on slide 69. Of these, the "nested sets" model looks like the one I'd prefer.

**Directed acyclic graph (DAG)**

Now, what if we have a directed acyclic graph?

All of the models described by Bill Karwin above work only if each node has at most one parent. In this graph, and more complex variants of it, any given node can have any number of parents (and any number of children).

My question is: how can I store a DAG in a normal relational database (such as MySQL) so that I can query the database for the relationship between two given nodes?

# Answer
> 3 votes
Excellent question. This is known as the problem of answering reachability queries in a graph, and in particular, in a directed acyclic graph (dag). Basically, you want to know whether y is reachable from x by following edges in the graph -- that's known as a reachability query. (And symmetrically, you also want to know whether x is reachable from y -- that's a second reachability query.) Answering reachability queries efficiently is challenging: there are good algorithms for trees, but dags are harder.

One approach is to do a depth-first search from x and see if y is reachable. However, in the worst case you might end up traversing the entire graph; the worst-case running time is $O(V+E)$. That's fine if the graph is small, but might take an uncomfortably long time if the graph is large. So there's been a lot of work on determining whether or not you can do some preprocessing or precomputation on the graph to make it easier to later answer reachability queries more efficiently than that. If the graph is static (doesn't change), this is known as the reachability problem in dags; if the graph is also changing, then this is known as the dynamic reachability problem for dags. These problems have been studied in both the CS theory and the databases communities.

Here are some resources to get you started in learning about the state of the art on this problem:

---

Finally, note that MySQL is a relational database, which is intended for relational data -- i.e., data in a tabular structure. I believe there are also graph-based databases, intended for data with a graph structure. I don't know much about that subject, but it's possible they might have built-in support that eases some kinds of queries and computations on graphs.

---
Tags: graphs, data-structures, graph-traversal, database-theory, databases
---


# Question
Title: Are Regular Languages (as we represent by Finite State Machines) Fields?
I am aware that we can do set operations on them, and sets are fields. Are regular languages also mathematical fields?

# Answer
No, the set of regular languages is not a field, but it is a boolean algebra. It also qualifies as a field of sets -- but note that the term "field of sets" has nothing to do with the notion of a "field"; it's an unfortunate name collision. See also https://en.wikipedia.org/wiki/Boolean\_algebra\_(structure).
> 1 votes

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


# Question
Title: Best way to schedule jobs so as to get minimum average turnaround time
The question is right there above.

# Answer
This is an open question, there's no universal one-size-fits all solution (yet?). The goal of **all** scheduling algorithms is to try to minimize turnaround time of all jobs.

The best scheduling algorithm (i.e. the one that minimized turnaround time) is dependant on the statistics of the jobs. Their start times, their durations, how accurately a heuristic can preempt them, etc. *If there was a universally optimal algorithm that guarantees minimized turnaround time, why would we ever use anything else?*

Consider the case of SJF, and it's minimum average waiting time. We don't really care about the waiting time of jobs, so much as how the waiting time is a *heuristic* for turnaround time. Other algorithms use other heuristics to try to try to minimize turnaround time.
> 1 votes

---
Tags: optimization, scheduling
---


# Question
Title: Approximation algorithm for the partition problem
In the partition problem we want to partition a set $S$ of positive integers into two sets $S\_{1}$ and $S\_{2}$ such that the sum of the integers in the two sets is the same.

The optimization version of the problem is NP-Hard, in the following wikipedia page an 7/6 approximation algorithm is described. In that algorithm, we sort the original set $S$, traverse the new sorted set in descending order and send each element to the set $S\_{i}, i\in\\{1,2\\}$ that has the minimum total sum at the given moment.

My question is, does the traversal have to be in descending order? If we do it in ascending, does anything change in the final approximation ratio?

# Answer
Consider what happens if you have 1000 items of size 1, and 1 of size 1000. Optimally, you would have 2 sets of size 1000, but if you followed the heuristic with items in ascending order, you will have one set of 500, and one of 1500, for a 3/2 approximation, worse than 7/6.
> 1 votes

---
Tags: approximation, partitions
---


# Question
Title: Solving recurrence relations using substitution followed by tree method/masters theorem
$T(n) = 4T(\sqrt n) + n$

First I substitute n = $2^k$:

$T(2^k) = 4T(2^{k/2}) + 2^k$

Now I rename the above as follows:

$S(k)=4S(k/2) + 2^k$

Now if I try to use tree method on this in the following way:

Work done at Level 1 = $2^k$

Work done at Level 2 = $2^{k/2} * 4$

Work done at Level 3 = $2^{k/4} * 16$ and so on. We have a total of $log\ k$ levels. The final term is dominant. So we should get $2^{k/{2^{log\ k}}} * (log\ k)^2$

That gives me the answer as $T(n)=(log\ k)^2$ = $(log\ log\ n)^2$

---

Second method:

$T(2^k) = 4T(2^{k/2}) + 2^k$

Divide each term by $2^k$:

$T(2^k)/2^k = 2T(2^{k/2})/2^{k/2} + 1$

Now rename it as follows:

$S(k)=2S(k/2) + 1$

Now using masters theorem on the above gets us $T(n) = k = log\ n$

The actual answer seems to be $n$. So, where am I making the mistake? Please let me know the the mistake in both the methods.

(Note: I actually mean asymptotic notation as the final answer).

# Answer
For your first method, it is dominated by the first term, not the last. (The second term is $2^{k/2} * 4 = 2^{(k/2)+2} \< 2^k$ for $k$ large.)

In your second method, when you divide each term by $2^k$, you didn't. You divided the second term by $2^{(k/2)+1}$ instead.
> 1 votes

---
Tags: asymptotics, recurrence-relation, discrete-mathematics, master-theorem
---


title: Understanding of hash tables

text:
# Question
Title: Understanding of hash tables
I am currently studying hash tables in an introductory course to computer science. I was taught that hash table is a data structure that associates a key to an index (a hash table) and then to the value associated to the key.

I don't understand why the hash function doesn't directly associate the key to the value

# Answer
> 3 votes
You cannot associate the key to a value directly, since you don't know in advance the set of keys. Hash tables implement an *associative array*, which is indexed by arbitrary objects. A naive implementation would have a huge array, indexed by all possible values of all possible types of objects. But this is clearly not realistic. Hash tables instead use a hash function to map a key to a numeric index, which is then used to address a conventional array.

If you knew the set of keys in advance, you could implement associative arrays as arrays indexed by the keys (like your suggestion). But it is not clear how to implement this. Suppose, for example, that the keys are all 3-regular graphs on 10 vertices. Given a 3-regular graph on 10 vertices, how do you associate it to a position in your array? It's not clear how to do this efficiently. Using a hash function, however, this becomes very easy.

# Answer
> 2 votes
The main use for a hash table is to structure data in such a way that when given a known (int, string, etc) one is able to easily find that specific object in memory.

---

An example would be a hash table which holds integers. Lets say the hash function of our hash table is (n modulo 10) or (n % 10).

Our dummy data will be: 1, 10, 15, 24, 51.

Passing each element through our hash function produces this hash table in memory:

\[0\] 1,10

\[1\] 51

\[2\]

\[3\]

\[4\] 24

\[5\] 15

\[6\]

\[7\]

\[8\]

\[9\]

---

Now lets say we want to find element: (15)

Passing 15 through our hash function leaves us with 5, when we look at memory address 5 we see our element 15!

You can think of how helpful hash tables can be when working with large amounts of data (think of a bank and how many customers they have, an employee cant afford to wait 10 minutes for the system to find 1 person).

These are some of the basic features of a hash table, but proper implementation of hash tables can drastically improve your programs speed.

---
Tags: hash
---


title: Grammar of a non-regular language

text:
# Question
Title: Grammar of a non-regular language
Given the alphabet $Λ = \\{a, b\\}$ and this non-regular language:

$$L=\\{aba^nb^ma^n|n,m\>0\\}$$

what's the best way to generate the grammar? Every string has to start with $ab$, then we have $aba$ and this part has to have the same number of $a$. In words that is clear, but I'm stuck; should I first consider the fixed part $ab$, or is better to produce the $a^nb^ma^n$ part and then add the $ab$? I need a method basically.

# Answer
You should think of this language as all words of the form $$ xa^nya^n, $$ where $x=ab$ and $y \in b^\*$. You can now modify a grammar for $a^nb^n$ to generate your language.
> 2 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: How to write a grammar for this language?
Given the alphabet $Λ = \\{a, b, c\\}$, i need to write a grammar for this language:

$$L=\\{α \mid α∈Λ^+ ∧ aaa \notin α\\}$$

I know that in my language the sequence of three consecutive $a$ cannot occur in any string, but how do I make a grammar of it? I'd need the thinking behind the construction of the grammar (like what's the first thing you should consider?), because so far I only manage to go by instinct and this doesn't always work.

# Answer
> 0 votes
Your language is regular, and so one way to construct a context-free grammar for it is to first consider a finite state automaton, and then convert it to a grammar. Of course, this methodology only works for regular languages, and is not necessarily the easiest way in every case.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Formulating a recursion using mathematical notation
So I'm assigned a task that involves formulating a quite complex recursion of several variables using 'mathematical notation'. The assignment is quite sparse when it comes to additional information, but below is the code anyway;

```
int partDist(String w1, String w2, int w1len, int w2len) {
if (w1len == 0)
  return w2len;
if (w2len == 0)
  return w1len;
int res = partDist(w1, w2, w1len - 1, w2len - 1) +
(w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);
int addLetter = partDist(w1, w2, w1len - 1, w2len) + 1;
if (addLetter < res)
  res = addLetter;
int deleteLetter = partDist(w1, w2, w1len, w2len - 1) + 1;
if (deleteLetter < res)
  res = deleteLetter;
return res;

```

}

The method calculates the amount of the following operations it takes to get from String w1 to w2 and vice-versa;

* Adding a letter
* Removing a letter
* Change an already exisiting letter

I'm not really sure where to proceed from there. I've managed to write something along the lines of a mathematic formula with conditionals but it just looks really messy and with a lot of hand-written conditions.

# Answer
> 0 votes
Abbreviating `partDist` to $D$, you are looking for a formula for $D(w\_1,w\_2)$. Given the form of the recursion, it will be easier to state a formula for $D(x\_1\sigma\_1,x\_2\sigma\_2)$, where $\sigma\_1,\sigma\_2$ are symbols (i.e., characters) and $x\_1,x\_2$ are strings; additional base cases will cover the cases in which $w\_i$ cannot be decomposed as $x\_i\sigma\_i$. The formula will be a minimum of two or three terms, depending on whether $\sigma\_1 = \sigma\_2$ or not.

Alternatively, you can write a recursion for $$ D(x\_1x\_2\ldots x\_n,y\_1y\_2\ldots y\_m). $$ Here the base cases would be $n=0$ and $m=0$, and in the recursive case you will have to distinguish between $x\_n = y\_m$ and $x\_n \leq y\_m$. Here all the $x\_i$ and $y\_j$ are symbols.

---
Tags: computability, recursion, mathematical-programming
---


# Question
Title: Size of intersection of two acyclic DFAs A and B is O(|A|+|B|)?
Acyclic DFAs recognize finite languages. For more info, see this Wikipedia page : https://en.wikipedia.org/wiki/Deterministic\_acyclic\_finite\_state\_automaton

To explain that the product of two DFAs $A$ and $B$ could lead to a result of size $O(|A|.|B|)$ in the worst case, most examples make use of DFAs containing cycles (those cycles are responsible in creating |A| copies of B in the result) like in this example :

As they are much more simpler than standard DFAs, I am wondering if the product operation (and more specifically union/intersection operations) of two acyclic DFAs $A$ and $B$ could result in a DFA of size $O(|A| + |B|)$ in the worst case ?

According to the article "State Complexity of Union and Intersection of Finite Languages" here : http://toc.yonsei.ac.kr/~emmous/papers/dlt07.pdf the authors say that the size of the DFA resulting from the product of two acyclic DFAs $A$ and $B$ remains in $O(|A|.|B|)$ only if the alphabet used is of variable size that depends on the size of the input DFAs. Thus, they conclude that this upper bound is $unreachable$ if the alphabet is of fixed size.

Does it mean that given a fixed size alphabet (e.g. $\sum=\\{a,b\\}$) and two DFAs $A$ and $B$ defined on $\sum$ , there is still the possibility that the intersection of $A$ and $B$ could result in a DFA of size $O(|A| + |B|)$ in the worst case ?

I would appreciate any counter-example, proof or reference to a paper dealing with this problem.

Many thanks, Luz.

# Answer
Lemma 4 and Lemma 8 in your paper show that even for a fixed size alphabet, there are infinitely many finite languages with minimal DFAs $A,B$ of sizes tending to infinity such that the minimal DFAs for the intersection and union languages has $\Omega(\min(|A|,|B|)^2)$ states.
> 2 votes

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


# Question
Title: Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?
I'm looking for a problem that allows me to generate random instances which:

1. Take arbitrary time to compute (i.e., I can generate an instance that I know would take at least 10 days to solve in an Intel I7);
2. Is inherently sequential (no matter how many processors you throw at it, it won't be solved faster than 10 days);
3. Can produce N (say, 2^256) equiprobable outputs;
4. Given an output, it is easy to verify it is correct.

Example:

1. Find the smallest N such that `sha256^N(seed) < K`. You can configure `K` so that it would take no less than X days given current hardware. The final hash can be any one of `2^256` possible values. But verifying is hard: the only way to prove an `N` is correct is re-doing the whole computation, so it doesn't really fit.
2. Find an N such that `sha256(seed+N) < K`. You can configure `K` so that it would take no less than X days given current hardware. The final hash can be any one of `2^256` possible values. It is easy to verify the output is correct. But it is embarrassingly parallel.

# Answer
Requirements 1-3 describe a timelock puzzle, also known as timed-release cryptography or time capsule cryptography. For instance, https://crypto.stackexchange.com/q/606/351.

Requirement 4 says it also has to be easy to verify a correct solution. I don't know of any standard scheme for timelock puzzles that happens to satisfy all four requirements, but you can invent one.

For instance, here is one simple approach that works, if you trust the creator of the puzzle to not try to play games with you. The creator picks a random AES key $k$, encrypts $k$ using the timed-release cryptography / timelock puzzle, and publishes the ciphertext as well as a SHA256 hash of $k$. Now requirements 1-3 are satisfied (it'll take a precisely-controllable amount of time for anyone else to recover $k$), and once you've found $k$, it is easy to verify that you found it correctly by hashing it and comparing the result to the publicly known hash.

For more on timelock puzzles, see also:

and papers in the cryptographic research literature.
> 2 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis
---


title: Numerically validate CRC performance

text:
# Question
Title: Numerically validate CRC performance
Koopman, P., & Chakravarty, T. (2004, June). Cyclic redundancy code (CRC) polynomial selection for embedded networks. In Dependable Systems and Networks, 2004 International Conference on (pp. 145-154). IEEE.

In this paper authors compare performance of different CRC polynomials in terms of minimum Hamming distance of two codes with the same checksum.

The naive method of doing this would require enumerating all codes that have the same checksum. This is computationally intractable for 2048 bit long data words that authors consider - so they must have used some more more efficient technique.

I did not find a mention in the paper on how the authors computed it. But it would be interesting to know the method as it would allow to numerically verify optimality of used CRC polynomials on given data word size.

What algorithm authors used to compute minimum HD for given CRC polynomial on long data words?

# Answer
> 2 votes
There are multiple techniques to compute the minimum Hamming distance for a given CRC polynomial. I don't know what technique they used, but here are three techniques that seem suitable.

I will assume the problem is as follows:

Given a CRC polynomial $p(x)$, determine whether there exists a $d$-bit error pattern of length $n$ that isn't detected.

This is equivalent to asking whether there exists a word of length $n$ with Hamming weight $d$ whose CRC is zero; or whether there exists a polynomial $q(x)$ of degree $n$ and weight $d$ such that $p(x)$ divides $q(x)$.

## Method #1: Exhaustive enumeration

One can enumerate all words of length $n$ and Hamming weight $d$, and check each one to see if that error pattern would be detected. This involves checking ${n \choose d}$ possibilities, which is feasible if $d$ is small and $n$ is not too large, but rapidly becomes infeasible for larger parameters.

For instance, their Table 1 lists results for $n=48$ and $d=1,2,3,4,5,6$. These are feasible to compute by exhaustive enumeration. For instance, for $n=48$ and $d=6$, we have ${48 \choose 6} \approx 2^{37.3}$, and it's feasible to do $2^{37.3}$ computations on a computer in a reasonable amount of time.

As another example, for $n=2048$, it's feasible to compute results for $d=1,2,3$. We have ${2048 \choose 3} \approx 2^{32.4}$, which isn't too large. However, ${2048 \choose 4} \approx 2^{44.6}$ which is feasible but uncomfortably large.

## Method #2: Meet-in-the-middle

We can speed up method #1 using a trick. The trick reduces the amount of computation time to something like $\sqrt{{n \choose d}}$, at the cost of requiring much more space (memory).

Note that the CRC is linear. Suppose there exists a data word $x$ of weight $d$ whose CRC is zero. We can express $x$ as $x=y \oplus z$ (where $\oplus$ denotes the xor), where $y,z$ each have weight $d/2$. Then by the linearity of the CRC, the CRC of $x$ is the xor of the CRC of $y$ and the CRC of $z$. So, if we want to search for an $x$ whose CRC is zero, it suffices to search for $y,z$ whose CRC xors to zero -- i.e., to search for $y,z$ that have the same CRC.

Now the method becomes this. We enumerate all data words $y$ of length $n$ and weight $d/2$, compute their CRC, and store them in a hashtable (or sorted list) keyed on the CRC. Next, we enumerate all data words $z$ of length $n$ and weight $d/2$, compute each one's CRC, and look up that CRC in the hashtable to look for matches. This will require $2 {n \choose d/2}$ CRC computations and ${n \choose d/2}$ space. Note that ${n \choose d/2}$ is roughly $\sqrt{{n \choose d}}$, so this is a big reduction in the running time.

If $d$ is not even, then we split into $y$ of weight $(d-1)/2$ and $z$ of weight $(d+1)/2$, so the running time is ${n \choose (d+1)/2}$ and ${n \choose (d-1)/2}$ space.

Of course, we can trade off memory for space, so we can find an algorithm with running time ${n \choose d\_1}$ and space ${n \choose d\_2}$ for any $d\_1,d\_2$ such that $d\_1+d\_2=d$.

As an example, for $n=48$ and $d=6$, there is an algorithm with ${48 \choose 3} \approx 2^{16.1}$ running time and ${48 \choose 3} \approx 2^{16.1}$ space -- easily computable on a computer. As another example, for $n=2048$ and $d=4$, the running time is $2^{21}$ and the space is $2^{21}$ -- again, easily feasible. For $n=2048$ and $d=5$, the running time is $2^{32.4}$ and $2^{21}$ space, which is again easily feasible. So this readily explains how one could compute the results in Figures 1-2.

(In fact, it turns out you can speed up this method by a small additional factor, at the price of an exponentially small probability of error. There are many ways to split $x=y \oplus z$, so in some sense the above method is doing more work than necessary. An optimization is to require that $y$ be zero in the last $n/2$ bits and $z$ be zero in the first $n/2$ bits, and search for such a split. This reduces the running time and space to ${n/2 \choose d/2}$ time and space. However, there is no guarantee that $x$ can be split in this way. So, instead, we pick a random subset $S \subseteq \\{1,2,\dots,n\\}$ of $n/2$ positions, and we require $y$ to be zero in all bit positions of $S$ and $z$ to be zero in all bit positions of $\overline{S}$, and we search for any solution. Then, we repeat this again multiple times with multiple different random choices of $S$. If there is a solution, then we have about a $1/\sqrt{\pi d/2}$ chance of finding it, so after $O(\sqrt{d})$ repetitions, there is an overwhelming chance that we find it. This provides a speedup by about a factor of $\Theta(2^{d/2}/\sqrt{d})$, at the cost of some implementation complexity.)

## Method #3: Discrete logs in finite fields

Finally, there is one more method, which involves a lot more implementation complexity and requires knowledge of finite fields. Given $p(x)$, we'll try to determine whether there exists a polynomial $q(x)$ of degree $n$ and weight $d$ such that

$$q(x) \equiv 0 \pmod{p(x)}.$$

We can think of this as working in the finite field $\mathbb{F}\_{2^m}$ where $m$ is the degree of $p(x)$. Note that there are fairly efficient algorithms for computing the discrete log in $\mathbb{F}\_{2^m}$ when $m$ is not too large (as is the case for CRC polynomials, where typically $m \le 32$). We can think of any polynomial as an element in this finite field. For example, we can think of the degree-1 polynomial $x$ as an element in the finite field.

We'll use a subroutine for computing the discrete log of an arbitrary polynomial $s(x)$, to the base $x$. In other words, given $s(x),p(x)$, this subroutine returns us a number $k$ such that

$$s(x) \equiv x^k \pmod{p(x)}.$$

Now we'll split $q(x)=r(x)+s(x)$ where $r(x)$ has weight $d-1$ and $s(x)$ has weight $1$. If $q(x) \equiv 0 \pmod{p(x)}$, it follows that

$$r(x) \equiv s(x) \pmod{p(x)}.$$

Thus we'll enumerate all possible polynomials $r(x)$ of degree $\< n$ and weight $d-1$, and for each, we will compute the discrete logarithm of $r(x)$ to the base $x$. If the resulting discrete log, call it $k$, is less than $n$, we have found a valid $s(x)$ of weight $1$ and thus $q(x) = r(x) + x^k$ is a multiple of $p(x)$ with degree $\<n$ and weight $d$, so we have found a valid solution. If the resulting discrete log is $\ge n$, we discard this possibility $r(x)$ and continue enumerating other values of $r(x)$.

The running time is ${n \choose d-1}$ computations of a discrete log and $O(1)$ space. This is unlikely to be better than Method #2 except for very large values of $n$ and small values of $d$, but there are some parameter settings where it might be probably faster than Method #2.

---
Tags: crc
---


# Question
Title: Is a String with no parantheses considered having balanced parantheses?
Say I have a language over the alphabet {x,y,(,)} . The language's rules are: any string over that alphabet with balanced parentheses.

Clearly x(), (xy) , ()()xxx, ((xx)) are accepted. BUT

My question is, is a string with **no** parentheses considered as having balanced parentheses? For example are: y, xxyy, xyxyxxx accepted?

And then also what about an empty String?

# Answer
> 2 votes
This is what formal definitions are for...

That said, it makes the most sense to allow no parentheses. Roughly speaking, a string has balanced parentheses if every left parenthesis is "matched" by a right parenthesis (of course this is far from being a formal definition). If there is no left parenthesis, then everything is OK.

Once you accept that, there is absolutely nothing wrong about the empty string – it is a string like any other. In particular, it is a string over your alphabet with balanced parentheses.

One way to formally define your language is using a context-free grammar. While there are many possible grammars, here is one that tried to capture the "matching" aspect when scanning the string from left to right:

$$ \begin{align\*} &S \to \epsilon \\ &S \to xS \\ &S \to yS \\ &S \to (S)S \end{align\*} $$

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


# Question
Title: Set of all rational numbers less than given computable real number is decidable
> Prove that set of rational numbers less than given computable real number is decidable

This problem was in my exam yesterday, but I was not able to solve it. However I still want to give it another try.
Same problem can be stated in this way:
Construct an algorithm, which answers the question: Is our given rational number less or greater than their(fixed) computable number?

Here's my poor try so far.

Since it's analysis related problem, I used the $\epsilon - \delta$ definition of computable number, which is:
$\exists f$ computable function, such that $\forall \epsilon \> 0, \epsilon \in \mathbb{Q}, f$ gives us $\delta \> 0, \delta \in \mathbb{Q}$ such that$|a - \delta| \leq \epsilon$ holds for given computable number $a$

Let $p \in \mathbb{Q}$ be our input, and let $f$ compute for us 2 rationals $q\_1$ and $q\_2$. It is well known that $|q\_1 - q\_2| \< 2\epsilon$

Now let's choose $\epsilon = \frac{1}{2^{i}}, i = 0,1,2,...$
For each $i$-th step I compute $f$ twice and get $q\_{i\_{1}},q\_{i\_{2}}$. I think that our given rational $p$ should hold some condition with both $q\_{i\_1},q\_{i\_2}$ which will help me to finish the algorithm, but I couldn't figure this out. I believe there are finitely many checks for each step which will let me know that for example $p \< a$ just like in picture below.

What do you think about this problem? Maybe there's more straightforward way to prove this. Thank you.

# Answer
> 3 votes
I would approach this problem as follows. Let $a$ be the computable real, and $A = \\{x\in\mathbb{Q}\ |\ x\<a\\}$.

If $a \in \mathbb{Q}$, then $A$ is decidable since $x\<a$ is a comparison between rationals, which is decidable.

Otherwise, we can assume $a$ is irrational. Our algorithm performs the following. First, we take the candidate $x\in\mathbb{Q}$ as input. We then query $f$ (the function which approximates $a$ as requested) repeatedly with $q=2^{-n}$ for every $n\>0$. Eventually, for some $n$ we will obtain one of

$$ f(2^{-n}) + 2^{-n} \< x \qquad \lor\qquad x \< f(2^{-n}) - 2^{-n} $$ Indeed, this will happen as soon as $2^{-n} \< |x-a| / 2$, which is a possibility because we know $x \neq a$.

In the first case, we return $x \> a$ ($x \notin A$), in the second we return $x\<a$ ($x \in A$).

The correctness comes from $$ a \leq f(2^{-n}) + 2^{-n} \qquad \land\qquad f(2^{-n}) - 2^{-n} \leq a $$ being true for all $n$.

---

Note that this solution is not uniform in $a$. That is, we only prove that there is an algorithm for any computable $a$, taking a candidate rational $x$ as input. We do *not* show that there is a single algorithm that, given both $a$ and $x$ as input is able to decide $\<$ (indeed, that would be undecidable).

---
Tags: computability, mathematical-analysis
---


title: Finding a language for a NFSA

text:
# Question
Title: Finding a language for a NFSA
I'm having a bit of trouble determining what language the following non-deterministic finite state automaton accepts.

Assuming the alphabet of this machine is ${a, b}$, I deduced that this automaton would accept words of the following characteristic: a word $w$ would be accepted if $w$ had zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s or $b$'s followed by a single $a$ followed by zero or more $a$'s and $b$'s.

Is there a more clear and concise explanation of what sorts of words are accepted by this automaton or would my explanation be suffice? Any suggestions would be appreciated!

# Answer
You have correctly identified your alphabet, but your verbal description is, indeed,complex. Your NSA would accept any string with at least 2 `a`s.

There are many ways to describe NSAs. A regular expression or a regular grammar could be appropriate here. If this is for class, I would ask your professor what format he or she prefers.
> 1 votes

# Answer
Let's trace it together:

* On `q1` state, you are looping on `a` or `b`, or you can proceed. That means `(a|b|E)*`, which can be simplified to `a*b*`.
* Then you move to `q2` on an `a`, which means `a*b*a`.
* Then on `q2`, it is the same as `q1`. Creating the expression `a*b*aa*b*`.
* Then transition on `a`: `a*b*aa*b*a`
* And looping on `a` or `b`: `a*b*aa*b*aa*b*`.

If your alphabet only contains `a` and `b`, then `a*b*` covers all combinations. The above expression can be comprehended as "`<anything>a<anything>a<anything>`", which can be verbally summarized as "strings that contain at least 2 occurrences of `a`".
> -1 votes

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


# Question
Title: Order of argument application in lambda calculus
I encountered the following exercise in a textbook about logic:

$\lambda x \lambda Y(Y(x))(j)(M)$

It seems that the expected result from the textbook should be $M(j)$, since there were some type specifications on the variables. However, if I substitute $M$ for $x$, and $j$ for $Y$, then the result would become $j(M)$, which would be erroneous in terms of type.

I've seen elsewhere expressions such as:

```
(λa.λb.λs.λz. a s (b s z)) x y →
(λb.λs.λz. x s (b s z)) y →
λs.λz. x s (y s z)

```

which seems to have the same application order of arguments as the one desired by this exercise.

It actually seems to make sense if I think of function application in Haskell, but I still find it weird since I expect the rightmost argument to be substituted first for the leftmost lambda term.

Therefore, does the notation $\lambda x \lambda Y(Y(x))(j)(M)$ implicitly entail $\lambda x (\lambda Y(Y(x))(j)(M))$, which would yield the desired result? Is such implicit omission of brackets a normal convention in lambda calculus, and thus every such expression should be treated as such? Or did I misunderstand the order of argument application in lambda calculus after all?

# Answer
> 3 votes
It seems that your book uses the notation $$ \lambda x\_1 \ldots \lambda x\_n (M\_1 \ldots M\_k) $$ instead of the more commonly found (in my experience) $$ (\lambda x\_1 \ldots \lambda x\_n. M\_1 \ldots M\_k) $$ Both notations are used for logical quantifiers by different authors, so it's not completely surprising. E.g., compare $$ \exists x (P(x) \land Q(x)) \qquad {\rm vs} \qquad (\exists x. P(x) \land Q(x)) $$

In the second style, the scope of binders ($\lambda x$, $\exists x$) extends as far to the right as possible.

---

About application order: the notation of your book $$ \lambda x\_1 \lambda x\_2 \lambda x\_3 (M) N\_1 N\_2 N\_3 $$ stands for $$ (((\lambda x\_1 (\lambda x\_2 (\lambda x\_3 (M)))) N\_1) N\_2) N\_3 $$ It is correct that the outermost application is of $N\_3$ but this does not get bound to $x\_1$. To see where $M\_3$ goes, one first needs to reduce the function $$ ((\lambda x\_1 (\lambda x\_2 (\lambda x\_3 (M)))) N\_1) N\_2 $$ to a lambda, and this involves applying $N\_2$ first. That will require applying $M\_1$ first, in turn.

The net effect is that $N\_i$ gets bound to $x\_i$.

Since you mentioned the Haskell notation, it is basically the same thing, even if Haskell uses the other notation (binders extend to the right as possible).

---
Tags: lambda-calculus
---


title: Data structure for adjacent rectangles

text:
# Question
Title: Data structure for adjacent rectangles
I have a file with a list of non-overlapping rectangles covering the entire space (they are adjacent). I would like to plot efficiently the graph edges that connect each rectangle center point with the adjacents rectangle center points. Which is the best data structure to use to load the rectangle list? Which is the best algorithm to find all the adjacent rectangles in x and y directions?

Thank you.

**More details:** In the picture below a visual example with 12 axis-aligned rectangles. The red paths are the desired output.

The numbering is from the random order in the input file:

```
rect1   (19,0)  (23,19)
rect2   (0,3)   (4,16)
rect3   (8,17)  (11,19)
rect4   (8,6)   (19,17)
rect5   (0,0)   (11,3)
rect6   (4,3)   (15,6)
rect7   (4,6)   (8,8)
rect8   (15,3)  (19,6)
rect9   (11,0)  (19,3)
rect10  (0,16)  (4,19)
rect11  (4,8)   (8,19)
rect12  (11,17) (19,19)

```

The desired output is the adjacent combinations of rectangles and their length:

```
(1,4) (1,12) (1,8) (1,9) (2,5) (2,10) (2,11) (2,7)
(2,6) (3,4) (3,12) (3,11) (4,6) (4,7) (4,8) (4,11)
(4,12) (5,6) (5,9) (6,7) (6,8) (6,9) (7,11) (8,9) (10,11)

```

# Answer
> 5 votes
The sweeping algorithm, suggested by @adrianN, can be elaborated this way.

**Step 1**. Put all your rectangles in a *map of sets* in such way, that:

* the map *key* is **left** boundary of rectangle
* the map *value* is ordered by **lower** boundary set of rectangles, having this left boundary

For your example, this map will be:

```
0 => (2, 5, 10)
4 => (6, 7, 11)
8 => (3, 4)
11 => (9, 12)
15 => (8)
19 => (1)

```

**Step 2**. Create a similar map of rectangle sets, having the same **right** boundary.

**Step 3**. Define *active* rectangle set, which will "sweep" the data structure above, from left to right, generating pairs of adjacent rectangles.

At first assign to the active set the rectangle set with minimal left boundary $x\_0$. You can immediately generate a number of pairs of adjacent rectangles from the active set (because it's ordered and there are no "holes" in it).

Then move the active set to the next position of the left boundary, let's say $x\_1$. You will need to update the active set, removing rectangles with right boundary $x\_1$, and adding rectangles with left boundary $x\_1$. You already have these rectangle sets in data structures, created earlier. The active set will be ordered after this update - generate pairs from it.

And so on...

For your example - active sets A0, A1 etc. will be:

```
A0 = (2, 5, 10)
A1 = (5, 6, 7, 11)
A2 = (5, 6, 4, 3)
A3 = (9, 6, 4, 12)
A4 = (9, 8, 4, 12)
A5 = (1)

```

This algorithm will generate all pairs of rectangles, adjacent in vertical direction only. Some of pairs will be generated more than once - you'll need to filter repetitions out.

In order to get all pairs of rectangles, adjacent in horizontal direction, you'll need to "rotate the picture" by 90 grades and repeat the algorithm. Another option - much more complex processing of rectangles during the active set update.

Time complexity of this algorithm depends on complexity of set operations *union* and *minus*.

# Answer
> 1 votes
I assume your rectangles are axis-parallel.

You can use a sweep-line approach. Sweep over the rectangles once in (say) x-direction. Add a path for all rectangles that intersect your sweep-line to your graph. The interesting points for the sweep line are the ends of your rectangles. If you sort them by their left border you can sweep easily. To construct the path to add to your graph you need to know the y-order of the rectangles that are currently intersecting the sweep-line. Here you can use a list sorted by y-coordinates.

---
Tags: data-structures, computational-geometry
---


title: Dancing links algorithm solutions

text:
# Question
Title: Dancing links algorithm solutions
Right now I am working on my implementation of Knuth's DLX algorithm.

I did understand the exact cover problem. But I didn't fully understand how Dancing links works. Here is Knuth's paper. The question is about the solutions presented in the paper. I don't understand how these solutions make sense taking into account the matrix that he uses.

Matrix for the exact cover problem

```
     A B C D E F G
  1  0 0 1 0 1 1 0
  2  1 0 0 1 0 0 1
  3  0 1 1 0 0 1 0
  4  1 0 0 1 0 0 0
  5  0 1 0 0 0 0 1
  6  0 0 0 1 1 0 1

```

And solutions are:

```
A D
B G
C E F

```

But how come these solutions are valid? Isn't it supposed to be answered like A B E? Where in each row there is only one 1.

# Answer
Knuth is trying to cover the *columns* using *rows*. The solution you describe consists of rows 4, 5, 1, in this order (counting from 1). Each row is represented by its 1-columns. For example, row 4 is 1001000, and its 1-columns are AD.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Representation of 8-Puzzle for (A*) Search Algorithm in C
I am trying to complete CS50's hacker edition pset3, where you have to make a program that will solve the game of eight or fifteen from its current state, this must be written in C. https://en.wikipedia.org/wiki/15\_puzzle

I first tried an approach of straight going for the step that get's you closest to the goal, but found it got caught in a loop. So I added a condition of not repeating the last move which just led to a longer loop!

I am going to need a search algorithm, and have researched and now understand some of the main ones. I think breadth or depth first would be too computationally expensive on larger boards and so, as the specification recommends I am going to try A\* search. Manhattan distance works easily for the heuristic as it is admissible and no. of moves from initial state for g(state).

However I am struggling mainly with the open and closed sets. So these must have the cost amount, but what representation of the game moves for that state? The whole board? But then how do you keep track of moves to get to that board for the final solution? I thought about having a massive array of like 200 to store the moves list, but for so many nodes this would be crazy. So how is the best way to represent the system and process of the game in a way that I can implement the search algorithm?

Many thanks

# Answer
> 2 votes
First of all, the $N$-puzzle is hard to solve with A$^\*$ using the Manhattan distance. Instead, we use IDA$^\*$. To see the technical details involved in the design of IDA$^\*$ specifically for solving the 15-Puzzle see Korf, Richard E. *Depth-First Iterative-Deepening: An Optimal Admissible Tree Search*, 27 (1985), 97-109. Artificial Intelligence. As a matter of fact, Richard Korf provided a wonderful implementation of his algorithm where he used various tricks to make his solver really fast: a pre-computed table stores the results of all operators to all states; another table stores the variation in the value of the Manhattan distance for each operator, and such. His implementation is publicly available here and you are very welcome to use it provided that you preserve the name of its author, Richard Korf, along with the copyright notice.

If you insist in using A$^\*$ for solving the $N$-puzzle then see Matthew Hatem, Ethan Burns, and Wheeler Ruml, *Problem Solving with Heuristic Search and Java*, IBM developerWorks, July, 2013. The source code is publicly available here. True, their implementation is in Java and their solution considers various issues which are not straight forward in C such as templates. However, most of the ideas are generically discussed (and, indeed, various issues regarding the open and closed lists are considered to a large extent) so that an implementation in C should not be hard.

Finally, let me stress that Manhattan distance is a rather poor heuristic for this domain. On one hand, it can be significantly enhanced with the so called *conflict-based* heuristic. On the other hand, *Pattern Databases* are a wonderful means for efficiently solving even the 25-Puzzle (even if some instances can take hours to be optimally solved).

Hope this helps,

---
Tags: artificial-intelligence, game-theory, board-games
---


title: Gale–Shapley algorithm is man-optimal

text:
# Question
Title: Gale–Shapley algorithm is man-optimal
I am trying to understand the proof why Gale–Shapley algorithm is optimal, however i am unable to do so. Could you please expand the proof, since the proof on this page https://sites.google.com/site/stablemarriageproblem/intro and here http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f10/Site/Materials/Lectures/Lecture21/lecture21.pdf relies crucially on the fact that the disagreement happens for the 1st time when a man M approaches a woman W and we are trying to prove that in no matching matching M can be paired up with W.

If possible could you also give alternative proofs.

# Answer
We use the following notation:

1. $M$ is the set of men, $W$ the set of women.
2. For a man $m$ and a set $W'$ of women, $\max\_m W'$ is the woman which $m$ prefers the most among those in $W'$, or $\bot$ if $W'$ is empty. We similarly define $\max\_w M'$ for a woman $w$ and a set $M'$ of men.

One way to view the Gale–Shapley algorithm is as maintaining a graph $G$ of possible matches. Here is pseudo-code for the Gale–Shapley algorithm from this point of view:

1. Create a complete bipartite graph $G$ with the men on one side and the women on the other side. The initial set of edges is thus $\\{(m,w) : m \in M, w \in W\\}$.
2. For each man $m \in M$, let $\operatorname{top}(m) = \max \\{w : (m,w) \in G\\}$ be the woman $m$ most prefers among his possible matches at this point; $m$ proposes to $\operatorname{top}(m)$.
3. For each woman $w \in W$, let $\operatorname{best}(w) = \max \\{m : \operatorname{top}(m) = w\\}$ be the man $w$ most prefers among those who propose to her; $w$ chooses $\operatorname{best}(w)$ (if different from $\bot$).
4. Remove $(m,\operatorname{top}(m))$ from $G$ whenever $\operatorname{best}(\operatorname{top}(m)) \neq m$, that is, remove $m$'s top choice as a possibility if she rejects him.
5. If any edge was removed from $G$ in Step 4, go back to Step 2.
6. Return the matching in which each man $m \in M$ is married to $\operatorname{top}(m)$, and each woman $w \in W$ is married to $\operatorname{best}(w)$.

The idea of the algorithm is that at each point, in every stable marriage, every match $(m,w)$ is an edge in $G$. The reason is as follows. Suppose that in Step 4, $\operatorname{best}(\operatorname{top}(m)) \neq m$ for some man $m \in M$, and consider any marriage in which $m$ is married to $w = \mathrm{top}(m)$. Let $m' = \mathrm{best}(w)$, so that $w = \mathrm{top}(m')$. Obviously $w$ by definition prefers $m'$ to $m$. Since $w$ was $m'$'s top possible choice, $m'$ must be married to someone he prefers $w$ over. Therefore $(m',w)$ is an unstable pair. This shows that no stable marriage can contain $(m,w)$, and so we can safely remove it from $G$ in Step 4.

Throughout the algorithm, no man $m \in M$ is ever left alone, i.e. there is always some $w \in W$ such that $(m,w) \in G$; this is important, since otherwise the algorithm isn't well-defined. This property holds due to the following list of observations:

1. Once $\operatorname{best}(w) = m \neq \bot$ at some stage for some woman $w \in W$, $\operatorname{best}(w) \neq \bot$ from that point on, and never becomes less desirable than $m$ from the point of view of $w$. This is because at the next iteration, $\operatorname{top}(m) = w$, so $\operatorname{best}(w)$ is at least as good as $m$.
2. If $\operatorname{best}(w\_1),\operatorname{best}(w\_2) \neq \bot$ at some iteration for $w\_1 \neq w\_2 \in W$, then $\operatorname{best}(w\_1) \neq \operatorname{best}(w\_2)$ at that iteration. This is since $\operatorname{top}(\operatorname{best}(w\_1)) = w\_1 \neq w\_2$.
3. Every time an edge $(m,w)$ is removed, $\operatorname{best}(w) \neq \bot$. This is because $w = \operatorname{top}(m)$.

Suppose now that all edges adjacent to some man $m \in M$ are removed, and consider the iteration in which the last edge adjacent to $m$ is removed. At this point, all edges $(m,w)$ were removed, so by (3) and (1), $\operatorname{best}(w) \neq \bot$ for all women $w \in W$. By (2), the mapping $\operatorname{best}\colon W\to M$ is one-to-one and so in bijection. In particular, $m = \operatorname{best}(w)$ for some woman $w \in W$. But this means that $w = \operatorname{top}(m)$ and so $(m,w)$ would not be removed in Step 4. We conclude that no man $m \in M$ is ever left isolated.

Since we only remove edges, eventually Step 6 will be reached. At this point, $\operatorname{best}(\operatorname{top}(m)) = m$ for all men $m \in M$, and so $\operatorname{top}$ and $\operatorname{best}$ are inverses. This shows that the output is well-defined and a matching.

Moreover, the matching is stable. Indeed, suppose that $(m,w)$ was an unstable pair, $m$ preferring $w$ over $\operatorname{top}(m)$, and $w$ preferring $m$ over $\operatorname{best}(w)$. Since $m$ prefers $w$ over $\operatorname{top}(m)$, necessarily $(m,w) \notin G$. When this edge was removed, $w$ preferred $\operatorname{best}(w)$ over $m$, and by (1), at the end $w$ still prefers $\operatorname{best}(w)$ over $m$, leading to a contradiction.

Finally, the matching is man-optimal. This is because in any stable marriage, a man $m \in M$ is matched to one of its neighbors in the final graph $G$. The marriage output by the algorithm matches $m$ to his top choice $\operatorname{top}(m)$, so it is optimal from the point of view of $m$.

Moreover, the matching is woman-pessimal. For suppose there were some stable matching in which some woman $w \in W$ is matched to a man which she prefers less than her match $m = \operatorname{best}(w)$ returned by the algorithm. Since $G$ represents the only possible matches in stable marriages, $m$ must be matched to some woman he prefers less than $w = \operatorname{top}(m)$. Thus $(m,w)$ is an unstable pair, and we reach a contradiction.

This exposition is taken from Section 6.3 of this paper, where other algorithms are described and analyzed, culminating in Subramanian's fixed point algorithm.
> 4 votes

# Answer
Let $E$ be an execution of the algorithm. Let $H$ be a stable marriage and $H\_E$ the output of $E$. For every $(m,w)$ in $H$ so that $m$ prefers his wife in $H$ over his wife in $H\_E$, record the time that $w$ refused or broke-up with $m$ during $E$.

Assume that the set of such pairs is non-empty (towards a contradiction).

Let $(m\_0,w\_0)$ be such a pair with minimum time.

Let $w'$ be the wife of $m\_0$ in $H\_E$.

Since $m\_0$ asked $w\_0$ before $w'$ during $E$, but ended up marrying $w'$, we know that $w\_0$ is not married to $m\_0$ due to some specific $m\_1$. And that $w\_0$ prefers $m\_1$ over $m\_0$. ($m\_1$ is not necessarily married to $m\_0$; they were just engaged.)

Let $w\_1$ be the wife of $m\_1$ in $H$.

There are two cases:

1. If $m\_1$ prefers $w\_1$ over $w\_0$: This means that prior to the engagement of $m\_1$ and $w\_0$, man $m\_1$ asked $w\_1$. This happened before $m\_0$ was rejected by $w\_0$, by the choice of $m\_1$. Since $m\_1,w\_1$ are not married in $H\_E$, this means that $w\_1$ rejected $m\_1$ before $w\_0$ rejected $m\_0$. A contradiction to the minimality.
2. If $m\_1$ prefers $w\_0$ over $w\_1$: This is a contradiction to the stability of $H$, since $w\_0$ also prefers $m\_1$ over $m\_0$.
> 2 votes

---
Tags: algorithm-analysis, matching
---


# Question
Title: An infinite subsequence of random numbers in Kolmogorov sense
Is it possible to construct an infinite increasing sequence of random naturals (in Kolmogorov sense) that is a subsequence of another sequence? Ok, in general I suppose not, e.g. for prime numbers. But:

I want to prove that sequence $\\{ax+b\\}\_{x\in\mathbb{N}}$ contains an infinite subsequence of random numbers. (This is, more-or-less, a statement in an exercise).

EDIT: The actual statement is to show that $\limsup\limits\_{x\to\infty}\frac{C\_U(ax+b)}{\log (ax+b)}=1$.

I believe the existance of infinitely many random numbers in general, stems from the fact that for a given $k$ we have $|\\{x\in\\{0,1\\}^k: C\_U(x)\< k\\}|\< 2^k$ because there are less binary strings of length $\leq k-1$ which may represent input to $U$. So no matter how large a binary representation, we can always find a random number with such a representation (in terms of its length). So, assuming longer $x$ means larger number it represents, we have infinitely many random numbers.

But what about here? We'd want those numbers to be of very specific form. Is there a way to do that? Could you give me a hint?

# Answer
If $x$ is Kolmogorov random then $C\_U(ax+b) \geq \log x - O(\log a + \log b + 1)$ (why?), and so $$ \frac{C\_U(ax+b)}{\log (ax+b)} \geq \frac{\log x - O(\log a + \log b + 1)}{\log x + O(\log a + \log b + 1)} = 1 - O\left(\frac{\log a + \log b + 1}{\log x}\right). $$ Since there are infinitely many Kolmogorov random numbers $x$, your result follows.
> 2 votes

---
Tags: kolmogorov-complexity
---


# Question
Title: Pumping Lemma for irregular language, how to choose and divide the string
The language on the alphabet $\\{a,b\\}$ is $$L=\\{ab^nab^{n+1} |n\>0\\}$$

so i have to take a string w = xyz:

what's the best string to choose such that $|w| \> n$? and then what about the division?

like $ w=ab^nab^{n+1}$ is a correct option? Then how can I divide this into three pieces? My attempt:

$ x = ab^s $ with $ 0 ≤ s ≤ n -1 $

$ y= b^ta $ with $ 0 \< t ≤ n - t $

$ z = b^k $ with $ 0 ≤ k \< n - t - s $

# Answer
w = abn-1abn.

We have to consider all the division xyz = w with |y| \>= 1 and |xy| \<= n. So

x = apbr

y = aqbs

z = btabn

where:

* p + q = 1
* r \> 0 implies p = 1
* q + s \> 0
* r + s + t = n - 1

Let's now consider w' = xy0z=apbr+tabn. If x is the empty string, then w' is missing the initial 'a' (and maybe some b), so w' is not in L. Else if x is not empty, we know that y contains at least one occurrence of 'b', so w' can't be in the form abnabn+1 and w' is not in L.
> 0 votes

---
Tags: formal-languages, pumping-lemma
---


# Question
Title: Two addresses point to the same data - is the data then stored 2 times in the cache?
Let's say a program reads the addresses `0x00 cd 10 54`and`0x00 cd 10 50`. The tag size and and index size added are just 4 bits, the cache has 8 blocks to 8 Bytes and thus 4 together make a set. The CPU is 32 bit.

Then above addresses would point to:

```
0x00 cd 10 50: ca 01 6b 7f ff 00 10 ee ff 41 45 e8 00 a7 56 00

```

and would want to write `ca 01 6b 7f ff 00 10 ee` into set `0` with tag `0x00 cd 10 5`

Let's say further say, the cache were empty beforehand. Is the data now written once or two times?

# Answer
> 1 votes
To answer the question: The read addresses are always rounded down to the next cache line address, then it will be looked up, whether an cache entry already matches this address.

In case yes: Then the address will just be ignored. Nothing further happens.

In case no: Then the data corresponding to the address will be load into the cache.

---
Tags: cpu-cache
---


# Question
Title: Dijkstra's algorithm runtime for dense graphs
The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is $O((E+V)\log V)$. For a dense graph such as a complete graph, there can be $V(V-1)/2$ edges.

Since $E \sim V^2$, is the runtime $O((V+V^2)\log V)$?

# Answer
> 5 votes
The runtime of Dijkstra's algorithm (with Fibonacci Heaps) is $O(|E|+|V|\log|V|)$, which is different from what you were posting.

If $|E|\in \Theta(|V|^2)$, that is your graph is very dense, then this gives you runtime of $O(|V|^2+|V|\log|V|)=O(|V|^2)$. A better runtime would be "surprising", since you have to look at every edge at least once.

When using binary heaps, you get a runtime of $O((|E|+|V|)\log|V|)$ which for $|E|\in \Theta(|V|^2)$ gives $O(|V|^2\log |V|)$.

# Answer
> -1 votes
You can also get rid of the log factor in dense graphs, and do it in $O(V^2)$. See here.

They might give you around $V=5000$ nodes but $O(V^2) = O(2.5 \cdot 10^7)$ edges which will give the leading edge over normal $O(E\log V)$ Dijkstra.

---
Tags: graphs, algorithm-analysis, asymptotics, landau-notation
---


# Question
Title: A good introductory book on cryptography
Can anyone suggest me some good books on cryptography? I have just starting studying cryptography but I know elementary number theory, abstract algebra and algorithms. Also please mention the difficulty level of the book.

# Answer
"Introduction to Modern Cryptography", Jonathan Katz and Yehuda Lindell. This is a great book for learning about provable security.

And for actual crypto protocols and algorithms, there's always the classic: "Handbook of Applied Crypto" by Paul van Oorschot, A. J. Menezes, and Scott Vanstone. This is more a reference book than a textbook. And its available free of cost on one of the authors web-pages.
> 6 votes

# Answer
It depends on what the purpose is, I personally read the A very short introduction to Cryptography which was a perfect guide to someone knowing nothing about this subject. If your purpose is to begin applying readily available algorithms this is a good book. If you want to get in deap and look at the functioning of algorithms you will need something more thorough
> 3 votes

# Answer
I'd recommend "Understanding Cryptography", Christof Paar & Jan Pelzl, if you are self teaching some cryptography. Why? Since it can be really hard to just follow a textbook by yourself, professor Christof Paar uploaded his lectures on youtube (Introduction to Cryptography by Christof Paar) so you can have a more complete experience.
> 2 votes

# Answer
I would have to say that **Applied Cryptography** by Bruce Schneier is the best I have come across. It's a good introduction, but at the same time have a detailed level.
> 1 votes

# Answer
IMHO a very good book for you may be: J. Hoffstein, J.Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography. ISBN 976-1-4419-2674-6. It is published 2010 in the Springer series Undergraduate Texts in Mathematics.
> 0 votes

---
Tags: reference-request, cryptography, books
---


# Question
Title: how to understand the occurrences of free variables?
I am thinking that many example only takes free variable with one occurrence, such as $(\lambda x.x )y$ where $y$ is free.

can we say $y y $ is a $\lambda$-term and two $y$ are same free variable? I did not see such examples so far, just wondering.

# Answer
> 4 votes
A possible definition (From Lambda-Calculus and Combinators):

> Definition 1.11 (Free and bound variables) An occurrence of a variable $x$ in a term $P$ is called:
>
> * bound if it is in the scope of a $\lambda x$ in $P$
> * bound and binding, iff it is the $x$ in $\lambda x$
> * free otherwise

Let's define the set of free variables $FV$:

* The free variables of $x$ are just $x$, that is $FV(x) = \\{x\\}$
* $FV(\lambda x. P) = FV(P) \setminus \\{x\\}$ (since $x$ is bound)
* $FV(st) = FV(s) \cup FV(t) $

And maybe you just need some examples:

* $y$ is free in $y$
* $x$ is free in $(\lambda x.x)x$ (Try to work out why)
* $y$ is free in $(yy)$.

---
Tags: lambda-calculus
---


# Question
Title: What would be acceptable size of list for O(n!) algorithm
I was wondering what the limitations to an algorithm that runs in O(n!). For example lets take an algorithm that generates all permutations of a list. Now what i am wondering is what the upper bound would roughly be for size of list. I understand that this can vary based on ram/memory. Let's say that this would be ran client side and be expected to work on basically any machine a user would have at his/her home.

Thanks in advance for any insight.

# Answer
It depends a bit on the constants hidden in the $O$, so no general answer is possible. In my experience you can aim for the low teens. 13! is about six billion. A computer can do about a billion things in a second, so a runtime of a couple of minutes seems reasonable if you only want to enumerate permutations. 15! is already more than a thousand times bigger, so most likely whatever you want to do will take too long.

On my machine counting to 11! in Python takes 14 seconds and counting to 12! takes two and a half minutes. Counting to 13! would hence take about half an hour. Counting to 15! would take about a week.
> 2 votes

# Answer
Lets do an example.

Lets say you have some operation that takes 1/100th of a second to complete.

Lets say your algorithm needs to use this operation exactly n! times.

Let n = 20

20! operations / 100 seconds per op / 60 seconds per min / 60 min per hour / 24 hours per day / 365 days per year ~= **771468165.962 years**.

Personally I don't have that kind of time to wait.

Note: Big O can't be used to calculate execution time like this in general because constants are dropped and operation time isn't the only factor. This is just a rough estimate so give or take a few millennia.

So the size of an acceptable list really depends on how much time you have.
> 2 votes

---
Tags: time-complexity
---


title: Trying to understand simple bit states

text:
# Question
Title: Trying to understand simple bit states
I am trying to understand bits, operations and masking. I have a hard time to get this thing into my head. I have tried to read at many different websites without luck.

I have 8 states, going from 1 to 8:

```
state 1 = 0001
state 2 = 0010
state 3 = 0011
state 4 = 0100
state 5 = 0101
state 6 = 0110
state 7 = 0111
state 8 = 1000

```

Now I want to get state 1, 3, 6 and 8. I am unsure how to set this state in the bits. Either I can do this:

```
state 1 = 0001
state 3 = 0011
state 6 = 0110
state 8 = 1000

```

Which would turn out like this:

```
combinedStates = 1111

```

The problem is, if I send in this, state 5 will get triggered as well as:

```
state 1 = 0001
state 3 = 0011
state 5 = 0101
state 6 = 0110
state 8 = 1000

```

Because both state 5 and 6 has a 1 in the same place. The second thing would be to add all the state numbers together (1, 3, 6 and 8, which is 18):

```
combinedStates = 0001 0010 (18)

```

But then looking at state 6 would not work as:

```
state 6 = 0110
combinedStates = 0001 0010

```

There will be a missing 1.

How would I proceed if I want to get states 1, 3, 6 and 8: combine their bits, or add them all together and use that one's bit value? Any other approach? Any operand I should use?

# Answer
> 2 votes
The easiest solution is to use one bit per state for a total of 8 bits:

state1 = 0000 0001
state2 = 0000 0010
...
state8 = 1000 0000

Then you can just `bitwise or` (or add) them together. Many programming languages have a datastructure for "bitsets" that can help with this, especially if you have more bits than fit in a simple integer. Your example with just 8 states fits in a typical int, so you don't really need such a data structure.

---
Tags: computer-architecture
---


# Question
Title: Optimizing cheap functions on mixed search space
Assume we have a really cheap function $f$ that is defined on a mixed parameter space and we want to find a minimum. For example

$\operatorname{arg\\,min}\limits\_{x\_1,x\_2,x\_3} f(x\_1,x\_2,x\_3)$

with

$x\_1 \in \mathbb{R}, \ x\_2 \in \\{1, \ldots, 10\\}$ and $x\_3 \in \\{\text{'a'}, \text{'b'} \\}$.

and we have no assumptions on monotony in any dimension or likely local optima. How can I find the values that minimize the function without much computational overhead?

# Answer
In general you can't. Optimization is a tricky business and proper solutions are only known if your $f$ and/or your search space belong to some restricted class.

You can try various heuristics. Things to google for include "genetic algorithms", "evolutionary algorithms", and "simulated annealing".
> 3 votes

---
Tags: optimization
---


# Question
Title: Can the output value be solved and/or written as Taylor expansion?
> imho this is not at all a duplicate, because the other question does not address the "recursive" case $T(d,n) = ....T(d-1,T(d-1,n))....$, which appears to be part of the Taylor expansion of this function. Also I don't know how to write this as a Taylor expansion. If I would, I would still not know how to solve this specific instance.

Consider the following function. Maybe it could be more efficient, but I'm only interested in the output value, not the runtime complexity. All variables are whole numbers.

```
function branch(currentDepth, maxDepth, n, k) {
    if (currentDepth == maxDepth) {
        return n;
    }
    sum = 0;
    for (i=0; i<=k; i++) {
        tmpN = branch(currentDepth+1, maxDepth, n, i);
        sum += branch(currentDepth+1, maxDepth, tmpN, k-i);
    }
    return sum;
}

```

For $2 \< k \<\< n$ and $2 \< d = O(\log n)$, is there a formula in terms of $d$, $k$ and $n$ (either exact, big-O or Theta), that predicts the output for

```
branch(0, d, n, k);

```

Will it be exponential in $n$? Can we maybe solve this for small $k$? ($k\le7$).

Application: the output value is a factor of the runtime complexity of a Fixed Parameter algorithm I made up, but I don't think it will beat existing algorithms. However I still wanted this solved.

# Answer
It is better to use as parameters `maxDepth-currentDepth`, `n`, `k`. Call the resulting function $f\_k(d,n)$.

When $k = 0$, $$ f\_0(d,n) = \begin{cases} n & d = 0, \\ f\_0(d-1,f\_0(d-1,n)) & d \> 0. \end{cases} $$ You can prove by induction that the solution is $f\_0(d,n) = n$.

When $k=1$, $$ f\_1(d,n) = \begin{cases} n & d = 0, \\ f\_1(d-1,f\_0(d-1,n)) + f\_0(d-1,f\_1(d-1,n)) & d \> 0, \end{cases} $$ which reduces to $$ f\_1(d,n) = \begin{cases} n & d = 0, \\ 2f\_1(d-1,n) & d \> 0. \end{cases} $$ The solution is $$ f\_1(d,n) = 2^d n. $$ When $k = 2$, using the preceding formulas we get $$ f\_2(d,n) = \begin{cases} n & d=0, \\ 2f\_2(d-1,n) + 4^{d-1} n & d \> 0. \end{cases} $$ Unrolling the recursion gives $$ \begin{align\*} f\_2(d,n) &= 4^{d-1} n + 2\cdot 4^{d-2} n + 2^2 \cdot 4^{d-3} n + \cdots + 2^{d-1} n + 2^d n \\ &= (2^{2d-2} + 2^{2d-3} + \cdots + 2^{d-1}+2^d) n \\ &= (2^d+1)2^{d-1} n. \end{align\*} $$ Let us approximate this by $2^{2d-1}n$.

When $k = 3$, the preceding formulas show that $$ f\_3(d,n) \approx \begin{cases} n & d = 0, \\ 2f\_3(d-1,n) + 2^{3d} n & d \> 0. \end{cases} $$ Unrolling the recursion gives $$ f\_3(d,n) \approx (2^{3d} + 2^{3(d-1)+1} + 2^{3(d-2)+2} + \cdots + 2^{3(1)+d-1} + 2^d)n \approx \frac{4}{3} 2^{3d}n. $$ Continuing in this way, we find that up to constants, if $f\_k(d,n) = \Theta(2^{r\_kd}n)$ then $r\_{k+1} = \max\_{1 \leq \ell \leq k} (r\_\ell + r\_{k+1-\ell})$ (except for the base cases $k \leq 1$). For example, we have $$ \begin{align\*} &r\_0 = 0 \\ &r\_1 = 1 \\ &r\_2 = 2 \\ &r\_3 = 3 \\ &r\_4 = 4 \end{align\*} $$ and so on. Indeed, induction shows that $f\_k(d,n) = \Theta\_k(2^{kd}n)$. With more effort, we could estimate the hidden constant.
> 3 votes

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


title: Use of hypothesis to prove a tautology

text:
# Question
Title: Use of hypothesis to prove a tautology
> Given $$ (¬(P ∧¬Q)⇒S)∧¬P ∧(R⇒¬S) ⇒ ¬R $$ prove that this is a tautology.

One way is to use a hypothesis taken from the proposition itself.

As an example: If we want to prove this rule: $P ⇒ (P ∧ Q ≡ Q)$ , we can do as follows:

We prove the equation $P ∧ Q ≡ Q$ using the hypothesis $P$ as justification:

$$P ∧ Q$$ $$ ≡ \\{Hypothesis: P, P ≡ T \\} $$ $$T ∧ Q $$ $$ ≡ \\{Unity \\} $$ $$Q$$

How do I do the same thing, with the proposition i wrote at the beginning?

---

\]Proof system example:

\[

It's in italian but it should be clear, those in brackets are, for example, the Commutative or Associative property.

# Answer
(¬(P∧¬Q)⇒S)∧¬P∧(R⇒¬S)⇒¬R

I've added in an extra parens for clarity:

((¬(P∧¬Q)⇒S)∧¬P∧(R⇒¬S))⇒¬R

First, replace x⇒y with ¬x∨y. This is definitional.

¬ ((¬¬(P∧¬Q)∨ S)∧¬P∧(¬R∨¬S)) ∨ ¬R

Cancel out ¬¬

¬ (((P∧¬Q)∨ S)∧¬P∧(¬R∨¬S)) ∨ ¬R

Demorgan's in your first ¬

(¬((P∧¬Q)∨ S) ∨ ¬¬P ∨ ¬(¬R∨¬S)) ∨ ¬R

Cancel out ¬¬

(¬((P∧¬Q)∨ S) ∨ P ∨ ¬(¬R∨¬S)) ∨ ¬R

Demorgan's in your outer ¬s

((¬(P∧¬Q)∧ ¬S) ∨ P ∨ (¬¬R∧¬¬S)) ∨ ¬R

Cancel out ¬¬

((¬(P∧¬Q)∧ ¬S) ∨ P ∨ (R ∧ S)) ∨ ¬R

Demorgan's again:

(((¬P ∨ ¬¬Q) ∧ ¬S) ∨ P ∨ (R ∧ S)) ∨ ¬R

Cancel out ¬¬ one last time

(((¬P ∨ Q) ∧ ¬S) ∨ P ∨ (R ∧ S)) ∨ ¬R

Drop outer parens (using associativity)

((¬P ∨ Q) ∧ ¬S) ∨ P ∨ (R ∧ S) ∨ ¬R

Use the distributive property on the first term

((¬P∧ ¬S) ∨ (Q ∧ ¬S)) ∨ P ∨ (R ∧ S) ∨ ¬R

Drop parens (using associativity)

(¬P ∧ ¬S) ∨ (Q ∧ ¬S) ∨ P ∨ (R ∧ S) ∨ ¬R

At this point, we have a chain of or statements. Use the distributive property on the last 2 terms:

(¬P ∧ ¬S) ∨ (Q ∧ ¬S) ∨ P ∨ ((R ∨ ¬R) ∧ (S ∨ ¬R))

(R ∨ ¬R) is always true, and T ∧ x ≡ x, thus:

(¬P ∧ ¬S) ∨ (Q ∧ ¬S) ∨ P ∨ S ∨ ¬R

Commutative property:

(¬P ∧ ¬S) ∨ P ∨ (Q ∧ ¬S) ∨ S ∨ ¬R

We will repeat the procedure with the distributive property on `(¬P ∧ ¬S) ∨ P` and on `(Q ∧ ¬S) ∨ S`:

((¬P ∨ P) ∧ (¬S ∨ P)) ∨ ((Q ∨ S) ∧ (¬S ∨ S)) ∨ ¬R (T ∧ (¬S ∨ P)) ∨ ((Q ∨ S) ∧ T) ∨ ¬R ¬S ∨ P ∨ Q ∨ S ∨ ¬R

Commutative property:

¬S ∨ S ∨ P ∨ Q ∨ ¬R

`¬S ∨ S` is T, and True or'd with anything becomes True by domination.
> 1 votes

---
Tags: propositional-logic
---


title: Can we multiply approximation hardness?

text:
# Question
Title: Can we multiply approximation hardness?
Say we have two (NP-)optimization problems $A$, resp. $B$, such that it is NP-hard to approximate within a factor $\alpha$ resp. $\beta$.

Now define problem $C$ whose input consists of pair inputs from $A$ and $B$, and a solution as pair of solutions of $A$ and $B$, but the objective function as the *product* of objective functions of $A$ and $B$.

Can we conclude that $C$ is NP-hard to approximate within a factor $\alpha\beta$? If not, can we prove anything stronger than that there is no approximation within $\max\\{\alpha, \beta\\}$? If yes, does it matter if the hardness depends on, for example, the unique games conjecture?

Intuitively, I would think: unless $P=NP$, for any polytime approximation algorithm for $A$ there is an input such that it gives a solution of cost more than $\alpha OPT$, and likewise for $B$. Any algorithm for $C$ can be used almost directly as an algorithm for either $A$ or $B$, so we can find an input that produces a solution of cost more than $\alpha \beta OPT$ on that algorithm as well. I am not sure if you can reason like this though.

# Answer
> 3 votes
When we say that a minimization problem A is NP-hard to approximate up to a factor $\alpha \geq 1$, we mean that there is a polynomial time reduction $f$ from instances $\varphi$ of SAT to instances $x$ of A annotated by a target value $\theta$ such that:

* If $\varphi$ is satisfiable then $A(x) \leq \theta$ (where $A(x)$ is the optimal value of $x$).
* If $\varphi$ is not satisfiable then $A(x) \> \alpha \theta$.

Using this definition it is not hard to prove the multiplicative property.

---

You can also consider a more general notion of hardness: if there is a polynomial time $\alpha$-approximation algorithm for A, then P=NP. Even under this notion, a $\alpha$-hardness for A translates to a $\alpha^2$-hardness for "A2". Indeed, given an instance of A, duplicate it and pass it to the $\alpha^2$-approximation algorithm. One of the solutions is an $\alpha$-approximation. If only the objective value is given, then the smaller one is an $\alpha$-approximation.

---
Tags: complexity-theory, approximation, complexity-classes
---


# Question
Title: FInding number of ancestors at given depth
I have a rooted tree with $n$ vertices.

I want to be able to answer the given queries in logarithmic time after setting up some sort of data structure (preferably in time $n\log n$.

The query is given by $v$ and $k$.

I want to find the number of ancestors of $v$ of degree less than or equal to $k$.( I call ancestors of degree $1$ sons).

I don't know how to do it.

At first I thought that I should only store the number of ancestors of $v$ of degree less than $2^j$. But this doesn't seem to work.

# Answer
> 1 votes
We do a dfs starting from the root. we save the entry-time and exit time of each vertex. We build a list containing (height(v),entrytime(v)). Where entrytime is the time in the dfs where we first reached vertex v.

we now sort our list lexicographically (this takes time $\mathcal O(n\log(n))$ ) . Inside this order, the vertices at height $h$ that are ancestors of a vertex $v$ are the elements in the list that are between $(h,entrytime(v))$ and $(h,exittime(v))$.

So the problem is essentially reduced to the following:

Suppose we have an array of integers $a\_1,a\_2,\dots, a\_n$, given $x$ and $p$ how can we find the number of elements in the range $a\_1,a\_2,\dots, a\_p$ that are greater than $x$? (we just need $p-k$).

Various efficient solutions to this are discussed here:

---
Tags: algorithms, trees
---


# Question
Title: Is the FSA for that language right? Comparison between two solutions
Given the alphabet $ Λ = \\{a, b\\}$ construct a FSA for the following language:

$$ L=\\{α∈Λ^\* ∧ |α|a =even ∧ |α|b =odd\\}$$

where $|α|x $ is the number of occurrences of $x$ in $α$. Basically, only strings where the number of $a$'s is even and the one of $b$'s is odd.

My attempt was the following:

whereas that's the solution of my teacher:

I wonder if mine is correct, too. I tried to follow the paths and I think that mine is working.

# Answer
Your FSA would not accept the string `AAB` or `ABBBA`, or any string ending with a `B` or starting with `AB...` or starting with `BA...` etc., all of which it should.

One of your main issue is that you don't have any `B` paths out of state `1`, but more problematically you only have three states, when you need at least four. This is because you have 4 different possible states, so you need at least 4 states to store all of them (odd `A` & odd `B`, odd `A` & even `B`, even `A` & odd `B`, even `A` & even `B`).

Your teacher's is correct because it has essentially divided up the responsibility of checking the parity of `A`'s and `B`'s to different halves. That is, you're in the top half of the graph whenever the number of `A`'s is even, and the right half of the graph whenever the number of `B`'s is odd. This works because each additional letter added is going to either make `B` go from odd to even (or vice versa) or `A` to go from odd to even (or vice versa).
> 1 votes

# Answer
Any NFA for your language contains at least 4 states, as we can show using the fooling set method. Consider the follows 4 pairs of words: $$ (b,\epsilon),(\epsilon,b),(ab,a),(a,ab). $$ For each pair $(x,y)$ we have $xy \in L$, while for every two different pairs $(x,y),(x',y')$ we have $x'y \notin L$.

Fix an NFA for $L$. For a pair $(x,y)$, choose an accepting computation, and denote by $q\_x$ the state after reading $x$. I claim that $q\_x \neq q\_{x'}$ for different pairs $(x,y),(x',y')$. Indeed, since $xy \in L$, upon reading $y$ the NFA can reach from $q\_x$ to an accepting state. If $q\_{x'} = q\_x$ that would imply that $x'y \in L$, contrary to fact.

It follows that any NFA for $L$ contains at least 4 different states.
> 1 votes

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


# Question
Title: Let $ L = \{ \langle M \rangle : L(M) = \Sigma^* -\{\epsilon\} \}$, Show that $L\notin RE$
Let $ L = \\{ \langle M \rangle : L(M) = \Sigma^\* -\\{\epsilon\\} \\}$

Determine whether $ L\in RE, \space L\in R, \space L\in co-RE$, or none of the above.

I tried to show a reduction function from $L\_{\Sigma^\*}$ to $L$ to prove that $L\notin RE$ , here is my attempt:

$\forall M\in L\_{\Sigma^\*} : f(M) = M'$, where M' is a Turing machine which works as follows:

$\forall w\in \Sigma^\*: $ if $w=\epsilon$ accept w; Otherwise run M on w and answer as M.

I manged to show that if $X \in L\_{\Sigma^\*}$ than $f(X)\in L$, but the other direction ($X \notin L\_{\Sigma^\*}$ than $f(X)\notin L$) seems to be more problematic and I'm not sure that reduction will even work.

I will appreciate any direction.

Btw, I'm new to reduction so please try to be patient and understanding.

Thanks!

# Answer
Hint: Let $L\_{\Sigma^\*}$ the language of descriptions of Turing machines halting on all inputs. Choose some computable surjective mapping from $\Sigma^+$ to $\Sigma^\*$, and use it to reduce $L\_{\Sigma^\*}$ to $L$. Since $L\_{\Sigma^\*}$ is neither RE nor coRE, it follows that the same holds for $L$.
> 1 votes

---
Tags: turing-machines, reductions
---


# Question
Title: What are advantages / disadvantages of horizontal and vertical microprograms?
Currently I know:

About vertical micro programming: The control signals are not immediately passed to the ALU components, but are rather processed first and passed as an compressed function code.

About horizontal micro programming: There is just one wire connecting all ALU components directly. The signal contains for each component a bit indicating whether the component should be activated or not.

I guess H-$\mu$Programs generally runs faster as they have not to be processed extra. However have the disadvantage that the signals are pretty long.

Are there other advantages / disadvantages to each of these two types of micro programming?

EDIT: I saw a comment regarding the question being dated. Yes, it is. Nonetheless, examiners at university want to know such things. I had a hard time finding information, which is why I asked on this StackExchange, sort of as a last resort.

# Answer
This questions seems dated, about the way computers and instruction sets were designed in the 70's.

AFAIK, micro-ops in x86 CPUs have about 100 bits, and are decoded separately in each operation unit (ALU, LSU, FPU...) There is no gigantic flat microcode controlling every multiplexer.

There used to be several layers of microcode and ROM decoding tables instructions are translated into "vertical" micro-ops which are then decoded into "horizontal" signals (IIRC, the MC68000 was like that).

Pure horizontal microcode is impractical in modern chips. Long wires have parasitic capacitance and are "slower" than transistors. Using a large and wide microcode ROM outputting hundreds or thousands of signals to individual adders, multiplexers and registers would make a large and slow chip.

Additionally, nowadays processors are pipelined : A wide microcode would need hundreds of flipflops to propagate instruction decoding along the pipeline.
> 5 votes

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


# Question
Title: Smallest number with in a larger number with a certain length
I have a number with $n$ digits. I want to keep only $m$ digits out of it. What is the smallest possible $m$ digit number which can be generated from the larger number so that order of digits is retained.

Ex: 3422509739

I need the smallest 3 digit number by removing 7 digits with order retained which will be 039.

# Answer
This problem is very similar to subsequence problem that is solved using dynamic programming. So, there are several ways to solve this problem, but the algorithm that you choose really depends on the input size ($n$, $m$ and base of numbers).

I here explain the simplest algorithm. I assume that the number is given in base 10, which means that your digits are all between 0 and 9. You just need to iterate over the smallest digits first and construct the smallest possible subnumber from the digits after that.

```
Algorithm SmallestSubNumber(number[1:n], m)
Smallest = \inf;
For i=0:9
   For j=1:n-m
      If (number[j] == i):
          Smallest = min(Smallest, i*10^(m-1) + SmallestSubNumber(number[j+1:n], m-1));
   If (Smallest != \inf) return Smallest;

```
> 1 votes

---
Tags: algorithms, enumeration, number-formats
---


# Question
Title: Treating undirected graphs as a subcategory of directed graphs
Roughly, an undirected graph is very similar to a directed graph where for each edge (v, w), there is always an edge (w, v). That suggests that it might be acceptable to view undirected graphs as a subset of directed graphs (perhaps with an additional restriction that adding/deleting edges can only be done in matching pairs).

However, textbooks usually don't follow this treatment, and prefer to define undirected graphs as a separate concept, rather than a subcategory of directed graphs. Is there any reason for that?

# Answer
> 8 votes
You are absolutely correct; that's a perfectly valid way to view undirected graphs.

Sometimes, in undirected graphs, some things become easier and cleaner to reason about. For instance, you don't have to worry about the difference between weakly connected vs strongly connected components in undirected graphs. Algorithms for undirected graphs can sometimes be more efficient or simpler than if we were to apply the corresponding algorithm for directed graphs.

So: perhaps some textbooks choose to follow this treatment because it lets them introduce a problem first in the (easier) context of undirected graphs, and then generalize to the (harder) case of directed graphs. That's just speculation.

# Answer
> 3 votes
See this page for examples of problems for which the undirected-graph form is actually harder than the directed-graph form. These include, for example, finding a negative-weight cycle, and counting the number of Eulerian cycles. To me, these problems seem to be harder in undirected graphs because part of the task can be framed as somehow choosing the right "direction" for each edge -- which of course is "already done for us" when the graph is directed.

# Answer
> 0 votes
It's hard to *motivate* something very general out of the blue; it might make the proofs and the textbooks simpler, but not necessarily easier to understand and intuitively follow.
People usually find it more intuitive to learn a simple concept and then generalize it to something more abstract, rather than to define some super-generalized and abstract concept and then instantiate its particular cases. This is probably one of those cases.

---
Tags: graphs, terminology
---


# Question
Title: What's the difference between the rank and the degree of a type function?
### 1 Context

Near pg. 184 of *Lambda Calculus and Combinators*, the author is discussing the theory of dependent types. In particular, we are extending the lambda calculus to look at terms of form

$$ \Pi x : \sigma . \tau (x) $$

Now terms of this form denote type functions with **degree** and **ranks**, unless I am mistaken.

### 2 Textbook Passage on Degrees vs. Ranks

Here is what the textbook states:

> The definition assumes that we are given a set (possibly infinite) of *atomic type constants*, $\theta^n\_i$, each with a *degree $n$*. Each atomic type constant with degree $n$ will represent a type function intended to take $n$ arguments, the value of which is a type.

and then later:

> **Definition 13.7 (Type functions and types)** *Type functions* of given degrees and ranks are defined in terms of *proper* type functions, which are defined as follows.
>
> 1. An atomic type constant of degree $n$ is an atomic proper type function of degree $n$ and rank $0$.
> 2. If $\sigma$ is a proper type function of degree $m \> 0$ and rank $k$ and $M$ is any term, then $\sigma M$ is a proper type function of degree $m - 1$ and rank $k$.
> 3. If $\sigma$ is a proper type function of degree $m$ and rank $k$, then $\lambda x . \sigma$ is a proper type function of degree $m+1$ and rank $k$.
> 4. If $\sigma$ and $\tau$ are proper type functions of degree $0$ and ranks $k$ and $l$ respectively, and if $x \notin FV(\sigma)$, then $(\Pi x : \sigma . \tau)$ is a proper type function of degree $0$ and rank $1 + k + l$.
>
> A type function of degree $m$ represents a function of $m$ arguments which accepts types as inputs and produces types as outputs. THe rank of a type function measures the number of occurrences of $\Pi$ in the normal form of the term representing it.

### 3 Question

**Question:** I am totally confused between the notion of a type function's **degree** versus its **rank**.

The book states that the rank of a term is the number of $\Pi$'s in its (normal) form. But doesn't the number of such $\Pi$'s correspond exactly to the number of arguments it takes? That is, if a type function takes $n$ arguments, then doesn't that just mean there must be $n$ $\Pi$ symbols to capture those $n$ arguments?

# Answer
> 5 votes
> The book states that the rank of a term is the number of $\Pi$'s in its (normal) form. But doesn't the number of such $\Pi$'s correspond exactly to the number of arguments it takes? That is, if a type function takes $n$ arguments, then doesn't that just mean there must be $n$ $\Pi$ symbols to capture those $n$ arguments?

Nope. Let $\sigma, \tau$ be types (i.e., type functions with degree=rank=$0$). The type $$ \prod\_{x:\sigma} \tau $$ is the type of functions $\sigma \to \tau$, which do not take *type* arguments -- they take *value* arguments (of type $\sigma$). So, the degree is $0$ (not $1$), while the rank is $1$.

# Answer
> 4 votes
The degree of a type function is its arity, i.e. the number of parameters that it takes. This is the simple concept that you're familiar with, independent of what kind of objects the function manipulates. Rank-0 types are types of base objects like integers, strings, and more complex data structures. The atomic type constants of degree $0$ would be things like `int`, `char`, `bool`, `string`, etc. Atomic type constants of higher degree are type constructors like `list` (degree $1$; `list int` (the type of lists of integers) has rank $0$ and degree $1-1=0$), `map` (degree $2$, `fmap string int` (the type of finite maps from strings to integers) has rank $0$ and degree $(1-1)-1=0$), etc.

The rank of a type function conveys what kind of objects it works on. Type functions of rank $1$ are the types of functions that act on base types. For example, if $\sigma$ and $\tau$ are two atomic types of degree $0$, then¹ $\sigma \to \tau$ is the type of functions from $\sigma$ to $\tau$, and has rank $0+0+1=1$. For example, `int -> int` has degree $0$ (it isn't “missing” a parameter) and rank $1$ (it's the type of a function acting on base values). The type of curried functions of two arguments `int -> int -> int = int -> (int -> int)` has rank $0+(0+0+1)+1=2$and degree $0$. Functions that take a function as argument have a higher-rank type, e.g. `(int -> int) -> int` has rank $(0+0+1)+0+1 = 2$.

Intuitively, the rank of a type is the number of times you have to apply an object of this type or a part of that type to get to a base object. This can be more than the number of abstractions that you need to perform to construct an object of that type, which would be the arity of the object itself, as is shown by the example of `(int->int)->int` — it's the type of a function of arity $1$, but getting to a base object also involves applying the argument to an integer.

¹ <sub> $\sigma \to \tau$ a notation shortcut for $\Pi x:\sigma. \tau$ used when $x$ does not appear free in $\tau$, i.e. when the dependent product is actually not dependent, but just an ordinary function type. </sub>

---
Tags: lambda-calculus, dependent-types, types
---


title: Can software itself be encrypted?

text:
# Question
Title: Can software itself be encrypted?
Imagine that I need to install my server in a remote location, so my algorithm can do something fancy (collocation of server at a financial exchange is how I thought of this question, but it applies more generally).

Imagine also I don't trust the people I am working with. They will have access to my server and I cannot be there to stop them from opening up the box and copying the disks.

Is there any way for me to hide the business logic of my algorithm from them, while maintaining that algorithm's functionality? In other words, can I encrypt my software and yet have it operate at the same time?

My feeling is no, since the software needs to speak in machine language, using the instruction set architecture, which is pretty standard. But CS is full of surprises so I thought I'd ask.

If the answer is yes, how do I do it? If the answer is no, are there any safeguards I can implement?

# Answer
If you want a practical answer: with Intel SGX, the answer seems to be a qualified yes, but software development is likely to be more painful. (Similar with a TPM, though that will be even more annoying.) See, e.g., https://security.stackexchange.com/q/2459/971.

If you want a theoretical answer: in theory, you could use various cryptographic schemes for outsourcing computation (e.g., fully homomorphic cryptography, secure multiparty computation, SNARKs, outsourcing computation, and so on). As a general theorem, any computation you can do in polynomial time, could also be done on the remote server in polynomial time, with ability to verify that the result it gives you back is correct in polynomial time. However, in practice right now these schemes include an enormous performance overhead (a factor of a million slowdown or more), except for certain special tasks, so they're not at a stage where you could actually use them in practice today.
> 7 votes

# Answer
Software Obfuscation is one way of hiding the details of an algorithm so that it cannot easily be recovered. The idea is to introduce additional spurious control and data flow that cannot be easily removed. Disassembly tools then have a hard time converting the assembly language code back into readable source code.
> 1 votes

# Answer
An activation key that is only activated with entering a code. That code could be long like from a USB drive. But this is does not necessarily hide business logic.

If your algorithm uses critical constants you could encrypt them and again you must supply a decryption key at run time.

Encrypt the compiled (or interpreted) code just makes things a lot harder.

Obfuscate is a strong deterrent but with enough time and resources they will crack it.

Security SE may be a better fit for this question.
> 1 votes

---
Tags: algorithms, security, encryption
---


# Question
Title: Is there any way to get "around" the halting problem?
As I understand it, one proof of the Halting Theorem is done by contradiction; we assume we have program X which can determine if any program terminates. We input program X into program X (with some modifications at the output), and we arrive at a contradiction. However, is it possible for a program Y to exist, where program Y can determine if any program (except variants of Y itself, or most loosely any finite set exceptions) halts?

If the set of exceptions must be infinite, can we have at least the set of permissible inputs be infinite itself?

Please try to keep the answers at a lower level, I know a little bit of mathematics but I am a complete layman in computer science.

# Answer
Say that two programs are equivalent if they have the same halting behaviour and output on every input. The problem for your "finite exceptions" idea is that there are infinitely many programs equivalent to any program you choose. Given a program $P$, we can always modify it in infinitely many ways without changing its output or halting behaviour: for each natural number $n$, we can write a program that essentially counts to $n$ and then runs $P$.

I suppose the good news is that this means we can decide the halting problem on an infinite class of programs. For example, let $P\_n$ be the program `for i = 1 to n do [nothing]; halt;`: the halting problem is easily decidable on the set of all programs $P\_n$.
> 6 votes

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