title: Why do we use multiple data structures?

text:
# Question
Title: Why do we use multiple data structures?
I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees.

Both runs in worst case O(n) in the same operations, so why don't we use only one data structure?

# Answer
> 3 votes
Aspects other than asymptotic worst case time are also important. For example

* Actual speed in practice
* Memory consumption
* Implementation difficulty

Algorithmic analysis almost never tells you the complete story and never should be used to justify blanket statements like "this data structure is the best if you need operations x,y,z".

# Answer
> 1 votes
$O(n)$ in BST means it was case degraded to Single Linked List, but it still has two pointers per node, while linked list has only one. But for balanced or almost balanced tree, the operations are $O(\log n)$. You can keep it balanced (using for example AVL tree or Red Black Tree, where both differ in cost of insert and delete by constant factor).
Linked list allows you to traverse in one direction, Doubly Linked List allows you to move in the both directions, it has two pointers per node, also if you do not use traversal in one direction, the cost of insert / delete is lower for Single Linked List. The notation makes this constant disappear. So taking memory footprint, actual time per unit operation, size of data stored, your needs and time to implement given data structure makes them differ a lot.

Also there are structures like Fibonacci heap, very good asymptotically, but rather heavy on small data and harder to implement.

There is no such structure that fits every situation and optimizes every possible feature, otherwise we would use only this one and learn about others for educational purposes only (or to stop people from reinventing the wheel).

---
Tags: algorithms, algorithm-analysis, linked-lists, binary-search-trees
---


# Question
Title: How to handle an undefined case with µ-recursive functions?
How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators?

For example, how should I proceed with the following one:

$\phantom{AAAA}pred(x) = undef$, if $x = 0$
$\phantom{AAAA}pred(x) = x - 1$, if $x \> 0$

How should I handle the $undef$-part?

# Answer
> 2 votes
$\mu$-recursive functions are partial functions because of the minimization operator. Without minimization, you get primitive recursive functions, and they're total. So an undefined value can only arise because the minimization operator is involved somehow. For example, you can define $$\mathrm{undef} := \mu(1)$$ where $1$ is the constant function (with arity $2$) whose value is $1$.

In general, to prove that a function is µ-recursive, you proceed as you would to prove that an object is a member of a class. You demonstrate that the object can be built according to the rules of that class, possibly using objects that other people have already proven to be members.

---
Tags: computability, turing-machines, proof-techniques, recursion, primitive-recursion
---


# Question
Title: How to show that certain summations are primitive recursive?
If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with

$$f(x\_1, \dots, x\_k , x\_{k+1})= \sum\_{i=0}^{x\_{k+1}}g(x\_1,\dots, x\_k,i)$$

is also primitive recursive?

# Answer
> 0 votes
Primitive recursive means the function can be calculated using loops where the number of iterations is calculated ahead before running the loop.

So how often would you run the loop to calculate the sum?

---
Tags: computability, closure-properties, recursion, primitive-recursion
---


# Question
Title: Why the Smallest Operable Data Type in Most Programming Languages Is One-Byte Sized?
Why the smallest operable data type in most programming languages is one-byte sized? Is it possible that to operate with a single bit? If it is possible, how to do it in practical?

# Answer
> 1 votes
That has mostly historical reasons. See Wikipedia:Byte. Operating on single bits is of course possible. How to do it depends on the programming language. In most languages you have bit level operators for AND, OR, XOR and so forth that you can use to manipulate single bits in a byte. In C you can use bit field structs to define data-types that are (logically) smaller than a byte.

# Answer
> 2 votes
Most instruction sets contain instructions that modify a single byte, but not instruction that modify a single bit and so higher level languages tend to reflect that.

Though modern high level languages include what is effectively a bit type, called boolean. Usually, it can only take two value (true or false), but a boolean requires a whole byte for storage.

If you need to store many bits, what you can do is to use a specialized data structure, which internally uses bytes or integers for storage (and so it stores 8 or more bits in a single underlying element). Such data structures include `std::vector<bool>` in C++ and `BitArray` in .Net.

# Answer
> 0 votes
Sometimes it **is** possible to operate even with single bits on the **processor** level. I would not advise you to do it, since it is way too cumbersome and not universal. E.g., if you really insist to do it for the Intel family, use FLAGS (or, if available, its extensions EFLAGS and RFLAGS).

---
Tags: programming-languages, computer-architecture
---


# Question
Title: Machine Learning - Support Vector Machines
I'm looking for good resources regarding **Support Vector Machines**, or suggestions where to start learning SVM.

Already used references:

* Stanford ML course by Andrew Ng is great place to star
* A Tutorial on Support Vector Machines for Pattern Recognition, Burges, 1998
SVM tutorials
* Neural Networks and Learning Machines, Third Edition Learning with Kernels - SVM, A. Smola

# Answer
> 5 votes
There are tons of tutorials for various backgrounds. What is your background? Here is one list of tutorials: http://www.kernel-machines.org/tutorials

# Answer
> 4 votes
Check out Metacademy. It is a wonderful learning guide for many topics in machine learning. Specifically, this page lists various resources for learning about support vector machines.

# Answer
> 3 votes
Some background info: You may want to start by studying perceptrons and the learning algorithm (a building block for SVMs). It may also be useful to read up a bit on kernel methods (dealing with high dimensional data) in machine learning and Lagrange multipliers and how to apply them in different optimization tasks.

For understanding the theory: There is a really good tutorial on SVMs which goes through (at least briefly) a lot of the background material and gives a good intro to SVMs.

"Pattern Recognition" by S. Theodoridis and K. Koutroumbas is a really good reference for SVMs and all of the theory behind a lot of pattern recognition related topics.

In practice: Have a look at LibSVM and start playing around with some datasets from UC Irvine's machine learning data repository. Play around with different kernel functions and see how the classification accuracy changes under various conditions for different datasets.

# Answer
> 2 votes
The following book is a very good and complete source on Machine Learning:

> Neural Networks and Learning Machines, Third Edition is renowned for its thoroughness and readability. This well-organized and completely up-to-date text remains the most comprehensive treatment of neural networks from an engineering perspective. This is ideal for professional engineers and research scientists.

# Answer
> 2 votes
In addition to listed references, I would recommend the following:

* A. Nefedov. Support Vector Machines: A Simple Tutorial, 2016
* N. Cristianini, J. Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods, Cambridge University Press, 2003
* B. Schölkopf, C.Burges, A. Smola. Advances in Kernel Methods: Support Vector Learning, MIT Press, 1999
* V. Vapnik. Statistical Learning Theory, John Wiley & Sons, 1998

---
Tags: reference-request, machine-learning, data-mining
---


# Question
Title: How to prove that a language $A$ is decidable?
How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering.

Word length alphabetically means a sorting first after the word length and then after the character ordering $(\epsilon,a,b,aa,ab,ba,bb, ...)$.

Hope somebody can help me like give a hint or an approach.

# Answer
I'll write $L$ for the language, $\mathscr{A}$ for the alphabet and $\mathscr{A}^\*$ for the set of all possible words.

If $L$ is decidable, then it's easy to list the words in $L$ in any order that doesn't depend on $L$, such as length-then-lexicographic order: list all the words in $\mathscr{A}$, and for each word, test whether it's in $L$ and output the word only if it is in $L$.

Conversely, suppose that there is a Turing machine $M$ that lists the words in $A$ in length-then-lexicographic order. By definition, this shows that $L$ is recursively enumerable. How can you go from this to the stronger property that $L$ is decidable?

The idea is that you can turn this into a decision procedure if you know when to stop. That is to stay, to decide whether a word $w$ is in $L$, stop the machine after $s$ steps. $s$ may depend on $w$ — if it doesn't, that means that $L$ can be recognized by a finite-state machine — so I'll write $s(w)$. If $w$ has been listed then $w \in L$ by assumption about the machine $M$, and if $w$ has not been listen then $w \notin L$ by construction of $s(w)$.

Of course, in general, there is no suitable function $s$: if $L$ is recursively enumerable but not decidable, that means that no computable function $s$ exists.

Use the fact that the order is length-then-lexicographic to find a suitable function $s$. There's a subtlety there: the function $s$ itself might not be computable — but it can be expressed in terms of how $M$ runs. The important point is that you can construct a machine $M'$ which runs $M$ for time and decides when to stop based on the output of $M$ and on some extra counter.
> 0 votes

# Answer
You know that a language $L$ is decidable if there is a TM, $M$ which when given a word $w$ as input always halts and accepts if $w\in L$ or halts and rejects if $w\notin L$. Here are some hints to get you started.

($\Rightarrow$) This is easy. If $L$ is decidable by a TM $D$, you can make an enumerator TM $E$ by trying all possible inputs in order. For word $w\_i$ in that order $E$ will run $M$ on $w\_i$ and write $w\_i$ if $M$ accepts.

($\Leftarrow$) Suppose you had an enumerator $E$ that lists all $w\in L$ in lexicographic order. Use that to construct a decider $M$ which when given $w$ as input, runs $E$ until it finds $w$ among the enumerated strings or fails to find $w$. Your task is to show that it will always either find $w$ or decides it does not appear on the enumeration in a finite amount of time.
> 0 votes

---
Tags: formal-languages, proof-techniques, decision-problem
---


title: Why is there no two-bit data type?

text:
# Question
Title: Why is there no two-bit data type?
Why do most programming languages (if not all) lack a 2-bit data type?

A **boolean** is a single bit with the values being **either** *true* or *false*.

Why is there no native, corresponding type where the values can be either *true*, *false*, *neither* or *both*? This data type can of course be constructed inside the language, but I figure there would be lots of usages for a more fundamental language support for it.

This data type would be very handy in, for instance:

* gene programming (values being: A, C, G or T)
* GUI programming (a checkbox that is: not checkable, unchecked, checked, or both/unknown)
* testing (test result can be: not run, pass, fail or inconclusive)
* quantum programming (values being: true, false, neither or both)

Is there a scientific reason to why this data type (quad, qool, qit etc.) has been excluded?

# Answer
Like Geier said, processors can't directly handle values smaller than a byte. So a boolean type that was actually implemented as just a single bit would in most cases be inefficient. The processor needs to do a bit of extra work to extract just that one bit.

The reason that the boolean type exists is more about semantics than anything else. Logical true/false values is a very useful concept. In many programming languages a conditional expression like "if x is 5" has a boolean value as the result. And lets not forget that a boolean type corresponds nicely to a single bit, which is the building block of the binary numbers that computers work with.

There has been tri-state "booleans" in use, and there probably still is today. But they are generally less useful and more complicated to deal with than the ordinary true/false ones.

What you are talking about would generally be implemented as bit flags (or bit fields), or simply by assigning different meanings to different numbers.
> 6 votes

# Answer
The reason is that architectures offer the types most often used. If you look at real programs, they handle characters (mostly implemented as 8 bit bytes), much more often integers (for array indices, much computation, things like file sizes). Approximations for real numbers are also important. Boolean values as such are very rarely handled (most conditions are handled as conditions in the CPU, and by conditional jumps). If you look at the types offered by C, they are a close match to the above. To give boolean values, the convention is that a zero value or a NULL pointer is false, as checking for those values is common.

Then there is the consideration of making shuffling values from/to memory has to be efficient, and current architectures live and die by their caches, which move multiple words at a time. Adding paths inside the CPU for handling another data size is costly too.

An extreme case of C weirdness was the CRAY, in which even characters where 32 bits, in the interests of maximal performance.
> 3 votes

# Answer
As well as the other answers that have been given, consider that it's not obvious what the basic operations on two-bit data types should be.

If you have two boolean values and want to combine them somehow, there are exactly 16 possible functions. Six of these are degenerate (i.e. they are constants or unary functions in disguise), leaving 10. They are:

* and
* or
* exclusive or
* left-implication
* right-implication

and the negations of these (nand, nor etc). The implications and their negations are trivially implementable in terms of negation and and/or, so you only need three. This is a tractable number. Hell, even ten is a reasonably tractable number of operations to provide if you can think up good names for them.

For two-bit data types it's far from obvious what most of the operations are useful for, and how they should be used, and it depends far more on what precisely the values mean.

For DNA, for example, one of the workhorse operations is reverse complement, which is only useful on a *vector* of nucleotides.

But if your values are the full lattice completion of a two-element domain (let's call them $\bot$, $0$, $1$ and $\top$), the interesting operations are join and meet. If it's the Klein four-group, then you want the group operations. If it's $GF(4)$, then you want field operations.

The abstract operations that the two-bit data type should provide are too tied to what the values *mean*, and there are too many of them ($2^{16}$ binary operations, admittedly including degenerate ones but were still talking "thousands" rather than "several") to provide them all.

Real data types are not just sets of values, they also have an internal structure. It's the structure which makes them complex. If it was just a matter of providing a set of values, then your favourite programming language or library could easily give it to you as an abstraction on top of the physical machine. But there are so many possibilities, that it's not clear what you specifically want.

If it is clear what structure you specifically want, then you don't want a type, you want a library.
> 2 votes

# Answer
Because it is not as useful to define it as a basic data type in general purpose programming language. In designing programming language it is important to keep the core language simple and small. Just because it has some applications doesn't make it essential for the core of a general purpose language, if every time someone used some data type we included in the core of a general purpose language then it would become too complicated and heavy. For such non-essential data types most general purpose programming languages provides easy ways of define them as a non-basic data type. For example, in C/C++ you can use the `enum` data type to implement a data type with a finite set of values.

On the other hand, Boolean data type is general and essential enough to be included in the core of most general purpose language. The conditional statements depend on it, the computer hardware depends on it, etc. So it is natural to include it as a basic data type in the core of these languages.
> 2 votes

# Answer
To understand why languages don't have a double-bit type, it may be helpful to consider why they have Boolean. Generally it's not because working with Boolean values is more efficient than working with integers, but rather because, with integers, even if a!=0 and b!=0 it's possible that (a & b)==0. If `a` and `b` are expressions which will always be either zero or one, the statements `if (a & b) ...` will be equivalent to both `if ((a != 0) & (b != 0)) ...` and `if ((a & b) != 0) ...`. If, however, the expressions may yield other values, then the two latter forms would not be equivalent to each other. If the intention had been to ensure that neither `a` nor `b` was zero, but the variables could in fact hold different non-zero values which have no overlapping bits, the expression which worked fine when `a` and `b` had to be zero or one would break. Requiring that integer values be cast to Boolean before being used in a conditional context compels the programmer to specify which of two plausible meanings was intended.

The fact that an `if` statement executes something or doesn't, and a loop likewise repeats or doesn't, creates an inherent need for a two-state conditional. While there may be some cases where a three-way or four-way branching construct would be helpful, most such needs are handled perfectly adequately by an n-way branching structure such as `switch`. Absent a particular reason to favor three-way and four-way branching over arbitrary branching, a two-bit type wouldn't really serve much purpose.
> 1 votes

# Answer
Added in response to link from why programming languages don't have types smaller than byte:

Writing a value which is narrower than a system's memory bus requires that a processor must do one of two things:

1. Read an entire word, update part of it, and write the whole thing back.
2. Output the part of the word that should change, while disabling the chips holding the parts of the word that shouldn't change.

Approach #2 will be generally be faster than approach #1 when it is feasible, but requires adding circuitry to implement. Early reprogrammable microcomputers had an 8-bit bis and did not include any signals to disable part of it; when later microcomputers used a 16-bit bus, including enough circuitry to independently enable and disable two halves of it was a burden, but it made it much easier to work with code that had been written for 8-bit systems. Allowing data to be written in 4-bit chunks would have required adding twice as much circuitry, without yielding a huge amount of additional benefit. When bus widths expanded to 32 bits, the amount of support circuitry doubled, but so did the maximum data throughput.

Thus, on most systems as constructed, writing a fraction of a byte would take twice as long as writing an entire byte; while it would be possible to build hardware to allow smaller writes, the benefits would fall short of the extra costs.
> 0 votes

---
Tags: programming-languages
---


# Question
Title: Equality of cardinality of maximum matching and minimum vertex cover in general
I'm preparing for exam and I came across this problem:

> We say that a graph is *König's graph* when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time algorithm deciding if a graph is *König's graph*.

I'm stuck. I know that in bipartite graphs this always holds. I also know that we can find maximum matching in every graph in polynomial time. But I don't know how to connect this with minimum vertex cover problem which in general is NP-complete.

# Answer
Let $M$ be a maximum matching. Any vertex cover must contain at least one vertex out of each edge in the matching. Hence the size of a minimum vertex cover equals the size of the maximum matching if there's a vertex cover consisting of one vertex out of each edge of $M$.

Denote the edges of $M$ by $e\_1 = (x\_1,y\_1),\ldots,e\_m = (x\_m,y\_m)$, where $m = |M|$. Let $v\_i$ be a Boolean variable which determines which of $x\_i,y\_i$ we pick. We can express the constraint that an edge not in $M$ is covered as a disjunction of two literals. Hence we can express the existence of a vertex cover of size $M$ as a 2CNF. Since 2SAT is solvable in polynomial time, we can determine whether such a vertex cover exists.
> 3 votes

---
Tags: algorithms, polynomial-time, matching
---


title: Snap/Fit a chain of lines to points

text:
# Question
Title: Snap/Fit a chain of lines to points
I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it.

Here is an image to illustrate what I want:

The figure shows a chain consisting of 3 individual lines. The lines are always connected, but their connecting points can be moved. The goal is to fit the connecting points such that the resulting lines are in a sense optimal with respect to the points/pixels (here in black with blue border), for example minimzing some distance. It would be nice if one could adapt this optimality criterion, e.g., such that the lines might snap to the point cloud coming from below the point cloud.

In my current problem I could also give some side conditions for the connecting (yellow) points, such as: point 1 has to be somewhere between x and y on the horizontal axis. Also, I could give conditions on the angles between the lines.

It would be awesome if someone could point me in the right direction and tell me actually what I am looking for :)

# Answer
> 1 votes
Yes. This is eminently doable. Here's the general recipe:

1. Define an "loss function" $L$. The loss function takes as input the location of the connecting points, and it outputs a measure of how good/bad this set of connecting points is. Smaller is better. You mention "minimizing some distance"; this is where you put that, but you'll need to decide on a specific loss function you want to minimize. If there are four connecting points, the loss function will take the form $L((x\_1,y\_1),(x\_2,y\_2),(x\_3,y\_3),(x\_4,y\_4))$ and will output a single real number. Choose a function that is continuous and differentiable.
2. Use gradient descent to find a location for the connecting points that minimizes the loss function. Pick some reasonable initialization value (e.g., where the user initially drew the lines; or use some heuristic to pick a crude guess at where to put the connecting points), and then use gradient descent to improve this initial choice and find a minimum for $L$.

This should be very efficient. It's also very flexible: if you decide you want a different criterion for what the line should look like, you achieve that by modifying the loss function. There are standard libraries for gradient descent, or if you prefer, you can implement it yourself without too much difficulty.

---
Tags: optimization, computational-geometry
---


# Question
Title: Is $\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$ correct?
I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063:

> ...and therefore the running time is $\Omega(m!)=\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$...

How can the second inequality be possible since $n!$ is super-exponential and it grows always faster than $2^n$? Perhaps i'm making a too stupid mistake?

# Answer
## Descriptively

The standard convention is that

$$f(x) = O(g(x))$$

should *really* be interpreted as

$$f(x) \in O(g(x)),$$

as $O(g(x))$ is most properly viewed as a set of functions. Yes, that means the former notation is a bit sloppy. Personally, I don't like it much, but that's the accepted short-hand.

By the same token, the standard convention is that

$$f(x) = O(g(x)) = O(h(x))$$

*actually* means

$$f(x) \in O(g(x)) \subseteq O(h(x)).$$

The former notation is a bit sloppy (and I don't like), but that's the accepted short-hand notation.

Or, in this case,

$$O(f(x)) = O(g(x))$$

should be interpreted as

$$O(f(x)) \subseteq O(g(x)).$$

The same holds for $\Omega$, too.

Yes, this is sloppy and imprecise. I think it would be clearer if authors didn't use this notational short-hand. But, it's a standard notational convenience. Hopefully, once you're aware of this, it should be possible to work out what was intended from context.

## Prescriptively

This use of notation is ugly and confusing and should be avoided, where ever possible.
> 5 votes

# Answer
This is where the abuse of notation "$f=\Omega(g)$" starts to turn into serious abuse. While I'm happy to write $f=\Omega(g)$1 in most contexts, as soon as you start talking about $\Omega(g)$ *as a set*, I think you're obliged to start using proper set notation. While we agree (some of us under duress) that $=$ can mean "is a member of" when it's written between a function and an asymptotic class, $=$ written between two sets just means equality, damnit, leading to exactly the confusion causing this question.

The equation you quoted should has been written something like $$f\in \Omega(m!) \subseteq \Omega(\sqrt{n}!) \subset \Omega(2^{\sqrt{n}})\\,.$$ (Exactly what the "$\subseteq$" should be depends on the actual relationship between $m$ and $n$, which isn't stated in the question. But $\subseteq$ had better be true because, if it isn't, the reasoning seems to be flawed.)

Alternatively, it could be split into something like, "$f=\Omega(m!)$, which gives us $f=\Omega(\sqrt{n}!)$ and, therefore, $f=\Omega(2^{\sqrt{n}})$." This maintains the standard abuse of notation but avoids writing $=$ between two sets that are manifestly not equal.

---

1 For example, taking "$O(g)$" to mean "some function in the set $O(g)$" allows one to write things like "$f(x) = x^2 + O(x)$" to bound error terms.
> 3 votes

# Answer
Ω(f(n)) represents a set of functions. In this case the equality doesn't mean that the sets are the same, but that all three apply to the runtime. (The sets aren't actually equal)
> 0 votes

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


# Question
Title: Computing optimal assignments using little memory
I have two lists where each item in the first list has a rating for each item in the second. I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item can only be matched once.

For example, there are 150 movies available, 100 people, and each person has rated each movie between 0 and 100. Once a movie is given to a person, it is no longer available for another person.

In this example, I'd like to find the scenario where the person/movie with the lowest rating is the best rating possible. Then, the average of all ratings is the best possible. Ideally, no one person would be unhappy with their movie (data permitting). There might be multiple optimal solutions, so I'd like to determine and rank the top 5 scenarios.

I plan to implement this in node.js and Javascript, so the memory footprint of data structure(s) is a factor.

What would be the optimal data structure and approach to solve something like this?

# Answer
Your problem is closely related to the assignment problem, and can be solved efficiently using techniques derived from that literature. I'll show how to solve it, by building up a solution step by step.

## Maximizing the lowest rating

Here is how you could efficiently find the assignment that maximizes the lowest rating. First, focus on the associated decision problem:

Input: movie ratings; an integer $t$
Goal: find an assignment where each person is assigned to a movie they rate at least $t$ or higher

This decision problem is an instance of bipartite matching, and can be solved using standard algorithms for it. Namely, look for any assignment that assigns each person a movie that they related at least $t$.

Now, to find the assignment that maximizes the lowest rating, use binary search over $t$.

This doesn't solve your problem yet, because it doesn't take into account that you want to resolve ties by maximizing the average rating.

## Resolving ties by maximizing the average rating

First, find the largest value $t$ such that there exists an assignment where everyone is assigned a movie they rate $\ge t$. (See above for how to do it.) Now if there are multiple such assignments, we want to find one of them where the average rating is maximized.

How do we do that? Answer: use a standard algorithm for the Hungarian algorithm.

In more detail, we do several steps:

1. Delete any (person,movie) rating where the person has rated the movie something less than $t$. It's not OK to assign that person that movie.
2. Now, you have an instance of the assignment problem, where each person has rated some of the movies with scores that are $t$ or larger. You want to find a matching assignment) that maximizes the average of the scores of assigned movies. Since every solution must assign 1 movie to each of the 100 people, the size of every assignment is the same, so maximizing the average is equivalent to maximizing the sum. Maximizing the sum of the ratings is exactly the assignment problem. Therefore, you can use any standard algorithm for solving the assignment problem (e.g., the Hungarian algorithm).

This will find an optimal solution: i.e., an assignment that maximizes the lowest rating, and that resolves ties by maximizing the average rating.

If you want to find the top-5 solutions, you can use an algorithm for enumerating solutions to the assignment problem in a streaming/output-sensitive fashion. See, e.g., Algorithm for a list of best solutions to the Assignment problem and Does Ford-Fulkerson always produce the left-most min-cut.
> 2 votes

---
Tags: algorithms, data-structures, optimization, matching, bipartite-matching
---


# Question
Title: Good resources for understanding semidefinite relaxation for combinatorial problems
I am looking for good, complete and understandable resources in the field of semidefinite programming and combinatorial optimization. Especially I have a combinatorial problem which I want to relax as SDP and want to compare the bound achieved with the LP relaxation. SO I need to know how to formulate a comb opt problem as SDP and also how to argue about the bound. Any resources would be appreciated.

Thanks.

# Answer
> 3 votes
The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys is an excellent handbook on approximation algorithms. It has an entire chapter devoted to the topic of SDPs. As of now you can download the older version directly from their website; however the printed text is pretty affordable.

---
Tags: reference-request, optimization, approximation, mathematical-programming
---


# Question
Title: Type-system combining type-states and typed effects?
Has anyone succeeded in implementing or designing a type-system that combines both type-state (linear types) and effect types (e.g. Koka)?

# Answer
> 9 votes
Edwin Brady has done some work in that area using dependent types in IDRIS. Take a look at his work, in particular Programming and Reasoning with Algebraic Effects and Dependent Types and Resource-dependent Algebraic Effects.

# Answer
> 7 votes
A lot of work on types for $\pi$-calculus does this. See e.g. (1) for a unified system. Sequential languages can be embedded into $\pi$-calculus, so this work also applies to sequential languages.

(1) A Uniform Type Structure for Secure Information Flow, K Honda and N Yoshida.

---
Tags: reference-request, type-theory
---


# Question
Title: How is the oracle function for Grover's Search algorithm obtained?
I've been using the IBM quantum experience to learn about and simulate Grover's algorithm. When they create the algorithm, they use a different set of gates depending on which oracle function $f(x)$ they want to use. In other words, they are explicitly putting in a set of gates of what they want to find before they look for it, then they get what they want -- a self-fulfilling prophecy.

How is the oracle function really implemented so that by simply looking at the choice of oracle function you don't immediately know the answer without evaluating it?

# Answer
> 5 votes
Here's the problem Grover's algorithm helps you solve:

Input: a function $f$
Output: a value $r$ such that $f(r)=0$

If you're paying attention, you should ask how $f$ is specified. This is the oracle part: $f$ is provided as a black box. That means, given any $x$, the algorithm can evaluate $f(x)$, but the algorithm can't "look inside the black box" and see how $x$ is represented. So, the algorithm doesn't have a way to "look at the choice of oracle function"; all the algorithm can do is supply some value $x$ and ask for the value of $f(x)$, and do that over and over again.

Why is this useful? There are some situations where we can easily specify a function $f$ but it seems to be very hard to find a value $r$ such that $f(r)=0$. (In fact, in many of those situations, even knowing how $f$ is implemented doesn't seem to help.) For instance, $f$ might be the SHA256 cryptographic hashing function: given any string $x$, we can efficiently compute its hash $f(x)$, but there seems to be no way to invert it short of trying lots and lots of candidate strings to see if any of them work.

Another example is $f(x,y)=x \times y - 179...23$, where $179..23$ is some specific large number that is known to be a product of two primes but whose factorization is unknown (we don't know what the primes are) -- we probably wouldn't actually use Grover's algorithm on that specific example, but it illustrates an example where we know how to specify a function where it's still hard to find an input that maps to zero.

Take a look at https://en.wikipedia.org/wiki/One-way\_function and https://en.wikipedia.org/wiki/Grover%27s\_algorithm.

# Answer
> 0 votes
On re-reading I found the source of the confusion. in classical logic, an *oracle function* is introduced in the construction of an inverse function x=f\_inv(y) when you have an efficient y=f(x). You don't know how the oracle produces the output f\_inv(x), but you know that you can check y=f(oracle(y)).

In Grover's algorithm, the term *quantum oracle operator* is used for the function that *checks* if the "quantum oracle" is right, not for the actual oracle making the predictions.

---
Tags: search-algorithms, quantum-computing
---


title: big-O and Θ notation subset

text:
# Question
Title: big-O and Θ notation subset
I was reading “Introduction to Algorithms” by CLRS and it says

> Note that *f(n) = Θ(g(n))* implies *f(n) = O(g(n))* since Θ notation is a stronger notation than *O* notation. Written set theoretically, we have *Θ(g(n)) ⊆ O (g(n)) .*

This means that Θ is a subset of O . Both the statements seem contradictory.

# Answer
> 7 votes
Lets refactor and reword these statements for ease of thought.

Let $A(n)$ be $Θ(g(n))$.

Let $B(n)$ be $O(g(n))$.

> Note that $A$ implies $B$ because $A$ is stronger than $B$.

This means for $A$ to be fulfilled we have to fulfill the criteria of $B$ and more. Therefore $A$ being fulfilled implies $B$ must also be.

> Written set theoretically, we have the set of functions that fulfill the criteria of $A$ are a subset of the functions that fulfill the criteria of $B$.

Well this is not contradictory, but actually equivalent in a sense to the last statement which showed that $A$ has the criteria of $B$ and more.

From our understanding of this point we can determine that: *All the functions that fulfill the criteria of $A$ fulfill $B$, but not all functions that fulfill the criteria of $B$ fulfill the criteria of $A$.*

This is really an equivalent statement to: *The functions that fulfill the criteria of $A$ are a subset of the functions that fulfill the criteria of $B$* because the second set contains the first.

And therefore $\Theta(g(n))\subseteq O (g(n))$ is true, and it is equally true that $f(n) = \Theta(g(n))$ implies $f(n) = O(g(n))$ without any contradiction.

Furthermore this makes sense with the definition for $\Theta(g(n))$ which states that: $f(n)\in \Theta(g(n))$ if and only if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$. Clearly by this definition, $f(n) \in Θ(g(n))$ does imply $f(n) \in O(g(n))$, and $\Theta(g(n))$ is clearly a subset of $O(g(n))$ as well.

# Answer
> 4 votes
No contradiction here. For simplicity, consider this example. You have a function, $f(n)$, if we say $f$ is $O(n^2)$ that would mean that $f$ is asymptotically less than a quadratic function. But if we know that $f$ is in fact linear, that would imply even stronger statement that $f$ is actually $\Theta(n)$. But linear functions are obviously one of the many functions bounded by quadratic function (such as $\log$, $n^{3/2}$, etc), hence it is a subset.

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


# Question
Title: How to match two sets of points based on the closeset distance?
I have a set of points (tiny triangles) $K=\\{1,2,\ldots, k\\}$ and a set points (tiny circles) $N=\\{1,2,\ldots, n\\}$ and a matrix of positive real values $\mathbf{D}=\left\[d\_{ij}\right\]$ for all $i\in K$ and for all $j\in N$. The entry of the matrix $d\_{ij}$ can be viewed as the Euclidean distance between triangle $i$ and circle $j$.

I would like to assign the triangles to the circles with the constraint that each assigned point is assigned to its closest neighbor. Also, the assignment must be one-to-one. For example, let

$$ \mathbf{D}=\begin{pmatrix} 1 & 1 & 5\\ 2 & 3 & 1\\ 5 & 8 & 6 \end{pmatrix}. $$ Now:

* triangle 1 would like to be assigned to circle 1 or 2 and then 3 (we have a tie);
* triangle 2 would like to be assigned to circle 3 then 1 and then 2;
* triangle 3 would like to be assigned to circle 1 then 3 and then 2;

How can I solve this problem?

I thought of creating a list of preferences based on $\mathbf{D}$ like in the example:

* List of preference for triangle 1: 1, 2, 3
* List of preference for triangle 2: 3, 1, 2
* List of preference for triangle 3: 1, 3, 2

But how can I continue on solving this?

# Answer
> 4 votes
You have an instance of a bipartite matching problem. There are some variations on the problem. I think you're looking for a minimum cost bipartite matching, but maybe you're looking for a stable matching.

# Answer
> 4 votes
Your problem statement is not very clear about whether the constraints are hard or soft.

## Hard constraints

Suppose the constraints are hard: each triangle must be assigned to one of the closest circles (there might be multiple possibilities, in case of a tie), and vice versa. For example triangle 1 can only be matched to circle 1 or 2; triangle 2 can only be matched to circle 3; triangle 3 can only be matched to circle 1. Then this problem can be solved in polynomial time.

Build a bipartite edge with one vertex for each triangle and one vertex for each circle. Draw an edge $(u,v)$ between triangle $u$ and circle $v$ if $u$ is one of the closest neighbors to $v$, and $v$ is one of the closest neighbors to $u$.

Then, you are looking for a perfect matching in this bipartite graph. There are efficient algorithms for this problem.

## Soft constraints

Your first step will be to more precisely specify the desired solution. You list multiple goals, but some of these might be contradictory or in tension, and you'll need to decide how to trade off between them.

One way to do this is to specify a single objective function. An objective function takes a candidate solution as input and assigns a "value" (a real number) to it. Then, the optimization problem is to find the solution that maximizes the objective function.

With that approach, the way to solve this will depend on the specific objective function you have in mind. You should first develop a specific objective function. Then, take a look at weighted bipartite matching, the assignment problem, and stable matching, to see if any of those meet your needs. If you've chosen an objective function that none of those techniques are able to maximize, ask a new question and specify the precise objective function you are trying to maximize.

---
Tags: algorithms, assignment-problem
---


title: Simple regular expression problem

text:
# Question
Title: Simple regular expression problem
new to automata theory and this is quite difficult for me so I'd appreciate a hint in the right direction if possible.

We want to find a regular expression for the language $L$ over $\Sigma = {a,b,c}$ where $L$ is the language of all strings of even length, contain $a$ at least once, and after the final $a$ letter there are no $b$s.

for example - $bcbabaca$ is a valid word.

Best thing I could come up with is somewhat akin to $R = ((a+b+c)(a+b+c))^\*a((a+b+c)(a+b+c))^\*$ and it has to be something like that since we need to control the length of the word to make it even, but still its no good and im having difficulties.

# Answer
> 2 votes
You're almost there.

$((a+b+c)(a+b+c))^∗$ gives you strings of even length.

$((a+b+c)(a+b+c))^∗a$ gives you strings of even length plus an $a$. That is, odd-length strings that contain at least one $a$ and end with an $a$.

Now, we're told that there are no $b$s after the last $a$. And there are certainly no $a$s after the last $a$, because that's what "last" means! So there can only be $c$s after the last $a$.

So, the answer is going to have to look something like $((a+b+c)(a+b+c))^∗ac^\*$. That's not quite right, because it doesn't force the whole string to be even-length and it does force the last $a$ to be in an odd-numbered position in the string (whereas, *hint*, it should be able to be even *or* odd).

I'm going to stop there because you showed enough in the question that I think you can finish this yourself, now.

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


# Question
Title: python, learn from users erros// multiple choice quiz
I am making a multiple choice quiz however I am finding difficulty on how to impletement a machine learning algrithm of somesort where by it can see which questions the user gets wrong and make a custom quiz for them for those questions.

many thanks

# Answer
You don't really need any complex machine learning algorithms for this. I mean, it would be cool to use it and try to guess what questions would stump them with AI, but I think you could get away with something simple.

Consider the following strategy:

1. Questions are given tags that identify the categories they fall under. You can use multiple tags to identify broader categories and more specific concepts.
2. Your system tracks the users percentage in each tag.
3. Optionally: The user selects some broad categories they want to study right now
4. Your system selects random questions from categories the user has a low success rate with
5. Occasionally the system breaks from that strategy to ask questions in categories it has a low confidence with, for example categories that the user has never tried. For example, it may follow a random selection that weights your worst categories highly, your low confidence categories moderately, and categories it know you are good at are weighted the least.

This AI doesn't really use any complex machine learning algorithms, but it gets the job done, probing the users abilities, and focusing on their weaknesses.
> 2 votes

---
Tags: algorithms, machine-learning
---


# Question
Title: Can we reduce an NP complete item to an NP item which is $\bf{non}$ P?
I'm curious if we can reduce an $NP$-complete problem to an $NP$ problem which is not a part of the $P$ set. Meaning, can we take an algorithm for this kind of $NP$ problem and use it to solve a single $NP$-complete problem?

If we could do this would it mean that the single $NP$ problem which is non $P$ is considered to be a part of the $NP$-complete problem set?

Is there a way to prove that all $NP$ problems which are non $P$ are considered to be a part of the $NP$-complete problem set?

# Answer
No, it is not possible to prove that all $NP$ problems which are not $P$ are $NP$-complete. In fact, the opposite has been shown: unless $P=NP$, there are $NP$ intermediate problems, neither in $P$, nor $NP$-complete. See https://en.wikipedia.org/wiki/NP-intermediate

So if you reduce an $NP$-complete problem to another $NP$ problem, all you've done is proved that that problem is also $NP$-complete.
> 8 votes

---
Tags: np-complete, reductions, np
---


# Question
Title: What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates
In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the first layer consists of OR (or AND) gates, then the second layer consists of AND (or OR) gates, the third layer consists of OR(AND) gates, and so on, what is the proof of this conclusion? Or any reference? I remember the proof that the PARITY problem needs exponential circuit complexity used this fact when using Håstad switching Lemma. Thanks!

Note: we don't need CNF(or DNF) here, because that corresponds to 2 layers and exponential number of gates. In general, the circuit above can be arranged as multiple layers, so CNF(DNF) is not necessary.

# Answer
Let $r$ be the root of your circuit (without loss of generality, an OR gate), and let $V\_i$ consist of those gates at distance $i$ from $r$. Assign (in your mind) a layer for each gate: layer 0 for the root, layer $2i-1$ for an AND gate in $V\_i$, and layer $2i$ for an OR gate in $V\_i$. The result is almost what you want – the only difference is that edges could span more than one layer.

In order to fix the problem, for each gate $g$, create gates in all layers above it (i.e., with smaller number) of the correct type, and connect them in a path (so all the new gates will have in-degree 1). Now you can arrange that each edge span exactly one layer.

Starting with a circuit of depth $D$ and $n$ gates, we have created a circuit of depth $2D$ and at most $nD$ gates. In particular, if the original circuit had polynomial size then so does the new one (with a different polynomial), and if the original circuit had constant depth (or logarithmic, or polylogarithmic) then so does the new one.
> 1 votes

---
Tags: complexity-theory, computability, circuits
---


title: Converting a non-planar graph to planar

text:
# Question
Title: Converting a non-planar graph to planar
Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness.

Besides connectedness, $G$ is guaranteed to have enough connectivity so that removal of a reasonably small amount of vertices do not disconnect the graph and there are several paths between two specified vertices (removing one or two vertices do not let $G$ be a tree).

I have looked it up on the Internet and could not find any research. Maybe it is because I do not know the proper keywords.

Is there any research on this topic? If so, could you provide a reference?

# Answer
These problems usually appear under the name "X edge deletion" and "X vertex deletion", where X is the graph class of interest, e.g., X could be "planar". There are also different variants where you allow for say edge addition and deletion (these are "editing problems"), or the operation could be edge contraction and so on.

In other words, you seem to be interested in both planar vertex deletion and planar edge deletion. For starters, you can see \[1\] and \[2\] (the problems seem FPT parameterized by the number of operations $k$).

---

\[1\] Marx, Dániel, and Ildikó Schlotter. "Obtaining a planar graph by vertex deletion." Algorithmica 62.3-4 (2012): 807-822. -- Non-paywalled version here.

\[2\] Golovach, Petr A., Pim van’t Hof, and Daniël Paulusma. "Obtaining planarity by contracting few edges." Theoretical Computer Science 476 (2013): 38-46.
> 7 votes

---
Tags: graphs, reference-request, planar-graphs
---


title: Turing Machine and decidability

text:
# Question
Title: Turing Machine and decidability
so the thing is that i have to prove that if the language $L ⊆ \Sigma^\*$ is decidable then both languages are also decidable. $$P\_1(L) = \\{w ∈ Σ\mid \text{ For every prefix v of w, we have }v ∈ L\\},$$ $$P\_2(L) = \\{w ∈ Σ\mid \text{ There's a prefix v of w, so that }v ∈ L\\}.$$

My idea is to create two TM for $P\_1$ and $P\_2$ and prove that they're decidable, but I don't know if it's right or not, and even if it is I have no clue how to proceed. I would be thankful for every help or tip!

# Answer
> 2 votes
I would go this way:

1. Assume that the language $L ⊆ \Sigma^\*$ is decidable by a TM M.
2. Build a TM M' that decides L1 by relying on M.
3. Build a TM M'' that decides L2 by relying on M.
4. State that by having assumed L decidable than L1 and L2 have become decidable as well.

M' and M'' will perform some operation (e.g. compute one or more prefixes v of the word w of increasing length), simulate M on v (as a Universal TM does with other TMs) and decide.

It should be sufficient to provide an informal description of what M' and M'' do and a diagram as the following: The diagram shows how to build a TM M1 relying on M: M1 does some operation (a copy) and then calls M (a TM it is supposed to exist).

Of course it is important that the "extra" operations performed by M' and M'' before calling M (those on computing prefixes) must be reasonably decidable.

---
Tags: computability, turing-machines, closure-properties
---


# Question
Title: Rules to follow to create edges in graph
I am currently writing a graph object in Swift, I see that there are different types of graphs, some that are undirected and some that are directed. Here are my questions :

* Can a graph be both directed and undirected, is there a specific name for such graph?
* What is the common approach to make an edge that would be bi-directionnal but whose weight depends on the direction you are following. Would it be acceptable to make an edge that hold two weights, one for each direction? Or should I create two edges?

Thank you.

# Answer
A graph that is both directed and undirected is called a Mixed graph.

All graph libraries that I know don't have direction dependent edge properties. Hence I would advise against introducing them if two directed edges do the job.
> 3 votes

---
Tags: graphs
---


# Question
Title: Difference between word logical addressing and byte logical addressing in this exercise?
I´m new here and this is the first question I´m posting (hopefully this is the correct site).

I have the exercise below:
Consider a virtual address space of 10 pages of 1024 words each (1 word = 2 bytes), mapped onto a physical memory of 32 frames. How many bits are needeed for each virtual address?

The answer they provide is:

```
| 4 bits for page | 10 bits for offset |

```

But I don´t figure out how do the 4 bits appear. The exercise explains that the logical addressing is *word* logical addressing (instead of *byte* logical addressing).

I´m confused about this two terms. How can I know if the addressing method is word based or byte based?

Thank you in advance

# Answer
> 0 votes
Page size =\> 1024 words = 2^10 words

Since it is word addressable format 10 bits will be required to identify offset within page.

There are 10 pages as 10 can't be expressed in 2's power format we need to consider 16 for identifying 10 pages i.e. 2^4=16.

So 4 bits are required for page number.

---
Tags: operating-systems, virtual-memory
---


# Question
Title: Is there any difference between extensible records and dependent maps
In a typed setting, records can be thought of as a map from field to type. If there is a well-typed record merge operation (which allows overlapping fields), is there any real difference between the resulting type and a dependent map in a dependently typed language?

# Answer
*Simple* records correspond to maps of dependent type (and we don't have a merge operation yet). More precisely, the record type

```
{ lbl1 : A1, lbl2 : A2, ..., lblN : AN }

```

corresponds to the product type

```
∏ (ℓ : label), A ℓ

```

where `label` is the sum type

```
lbl1 + lbl2 + ... + lblN

```

and `A : label → Type` is the type family defined by

```
A lbl1 ≡ A1
A lbl2 ≡ A2
       ⋮
A lblN ≡ AN

```

The record type above is also equivalent to the simple product

```
A1 × A2 × ⋯ × AN.

```

You asked about extensible records. There are at least two ways to do this. Without any additional technology we can model an extension of

```
{ foo : A, bar : B } ≤ { foo : A, bar : B, baz C }

```

with a couple of function that map between them (projection in one direction and extension by an extra field in the other). This is all very mundane.

We could also ask for the type of all possible record types. Suppose we have a type `label` of all possible labels (in practice it could be `string` or some such). The type of *all* record types is

```
record ≡ label → option Type

```

An element `R : record` is a mapping from labels to optional types, where `R lbl` takes value `None` if label `lbl` does not appear in `R` and value `Some A` if it appears and have type `A`.

If `R : record` then the type decribed by `R` is the product type

```
∏ (ℓ : label),
  match R ℓ with
  | Some A ⇒ A
  | None ⇒ unit
  end

```

This means that a record `r` of type `R` is a dependent function which takes a label  to an element of `A` if  appears in `R` and to the unit otherwise.

However, a `merge` operation is problematic, as well as a subtyping relation `R ≤ Q`. This is so because we cannot express the fact that a label `lbl` has the same type in record `R` and record `Q`. At best you can say that the types are isomorphic, or propositionally equal, but that's not what you want.

We *can* define an `extend` operation

```
extend : record → record → record

```

in which the first argument *overrides* the second one so that `extend R Q` has the fields of `R` additionally those fields of `Q` that do not appear in `R`:

```
extend R Q ≡
   λ (ℓ : label),
     match Q ℓ with
     | Some A ⇒ Some A
     | None ⇒ Q ℓ
     end

```
> 6 votes

---
Tags: type-theory, dependent-types
---


# Question
Title: Generalized sorting algorithm on partially ordered set generated by a relation
Assume we have a finite set $X$ of elements and any relation $\preceq$ on $X$. Such a relation may or may not generate a reflexive transitive anti-symmetric relation $\leq$ on $X$ (a partial order). Recall:

*reflexive*: We always have $x\leq x$.

*transitive*: If $x\leq y$ and $y\leq z$ then also $x\leq z$.

*anti-symmetric*: If $x\leq y$ and $y\leq x$ then $x=y$.

I'm looking for an efficient algorithm that decides whether $\preceq$ extends to a partial order and if yes, returns one or one with uniform probability or all possible orderings of $X$ which respect the partial order.

This naturally decomposes into two subtasks (not claiming that the best algorithm decomposes this way):

1. Decision whether $\preceq$ extends to $\leq$ or, in other words, extending by transitivity does not violate anti-symmetry. If it does, describing the partial order $\leq$.
2. Finding the possible orderings.

The second points is related this question.

# Answer
> 4 votes
You can efficiently test whether $\preceq$ extends to a partial order using topological sorting. Form a directed graph with vertex set $X$ and with an edge $x \to y$ whenever we have $x \preceq y$ and $x \ne y$. Then $\preceq$ extends to a partial order if and only if this graph has no cycles, which can be checked in linear time (e.g., by topologically sorting the graph).

Moreover, we can describe a minimal partial order $\le$ that is consistent with $\preceq$, as follows. Compute the transitive closure of this graph. Now declare $x \le y$ iff there's an edge $x \to y$ in the transitive closure, or $x=y$. (Equivalently, declare $x \le y$ iff $y$ is reachable from $x$ in zero or more steps, in the graph derived from $\preceq$.) By construction, the relation $\le$ defined in this way will automatically be reflexive and transitive; if the original graph has no cycles, then it is easy to prove that the relation $\le$ will be anti-symmetric as well and thus will be a partial order.

---
Tags: algorithms, sorting, partial-order
---


# Question
Title: Is Euler's totient function a primitive recursive function?
We consider the function $g$ which associates the number of prime integers with $n$ in the set $\\{0,...,n\\}$. I have to prove that $g$ is a primitive recursive function.

First I defined the set $A=\\{i∈\\{0,...,n\\}:\gcd(i,n)=1\\}$. To show that $A$ is a primitive recursive set I said that : $\\{0,...,n\\}$ is primitive recursive because ${k}$ is primitive recursive by characteristic function and $\\{0,...,n\\}=\bigcup\limits\_{k=0}^{n} \\{k\\}$ is primitive recursive by the property of $⋃$.

Then the function $\gcd$ is primitive recursive. Indeed we can see that with the function $lcm$. We have $lcm(a,b)=μk≤ab (∃j,l≤ab,aj=k∧bl=k)$ which is a primitive recursive expression. Then by operator division $\gcd$ is a primitive recursive function.

So $A$ is a primitive recursive set.

Now, to prove that $g$ is primitive recursive can I take :

$g(i)=\sum\limits\_{i=0}^{n} \chi\_{A}(i)$ with $χ\_A(i)=1$ if $i∈A$.and $g$ is a finite sum of primitive recursive functions so it is primitive recursive?

# Answer
A computable function is primitive recursive if and only if it can be computed by a program whose running time is upper-bounded by some primitive recursive function. Your function (usually known as Euler's totient function $\varphi$) can be computed in exponential time, and so is primitive recursive.
> 7 votes

---
Tags: computability, primitive-recursion
---


# Question
Title: Degree Reduction in Max Cut and Vertex Cover
I have been reading Alimonti and Kann's paper "Some APX-Completeness results for cubic graphs" and I don't understand why the degree-reduction gadgets for Max Cut and Min Vertex Cover have to be different.

Here are the two gadgets in question. The Min Vertex Cover gadget simply divides a degree $n$ node $v$ into a chain of nodes $v\_1,u,v\_2$, where $v\_1$ and $v\_2$ share the edges of $v$, increasing the Min Vertex Cover by 1 in the process. The Max Cut gadget on the other hand is rather more complicated and involves cycles. What I don't understand is why the simple Min Vertex Cover gadget can't be used for Max Cut?

Consider a degree 4 vertex $v$ in Max Cut. If you unfold the vertex as $v\_1,u,v\_2$ (as in the Min Vertex Cover example) you are adding 2 edges to the graph, both of which can be cut by placing $u$ on the opposite side of the cut to $v\_1$ and $v\_2$, so wouldn't the Max Cut just increase by 2? I'm probably missing something but I don't know what it is.

# Answer
> 2 votes
This is a counterexample.

Suppose you have this graph:

The maximum cut in this graph has four edges. If you follow the procedure used for vertex cover you get this cut:

In the image, the maximum cut has seven edges.

---
Tags: graphs, max-cut
---


# Question
Title: Convergence of recursive formula in TextRank
I am reading a paper about the TextRank algorithm in keyword extraction and they mention the recursive formula: $$ \displaystyle S(V\_{i}) = (1 - d) + d \ast \sum\_{j \in In(V\_{i})} \frac{1}{|Out(V\_{j})|} \\; S(V\_{j}) $$

where $ In(V\_{i}) $ are the vertices that point to $ V\_{i} $ and $ Out(V\_{i}) $ are the vertices that $ V\_{i} $ points to.

The paper claimed that this algorithm will converge for any arbitrarily small positive threshold and any arbitrary initial values by testing with experiments. However, I am attempting to prove it mathematically that this algorithm will always converge regardless of the choice of the threshold as well as the initial values, but haven't succeeded at this point. My approach is to prove that if $ E\_{ij} $ is the error at vertex $ i $ at the $ j $ iteration, then the sequence $ E\_{i1}, E\_{i2}, \dots, E\_{in} $ is a decreasing sequence. Intuitively, it means that the error rate approaches $ 0. $

Any hint or suggestion is appreciated.

# Answer
Your process is a Markov chain, so I suggest you try applying the theory of Markov chains. There's a rich and powerful theory that has been built up over time, which might be applicable here.

In particular, if we let $S$ denote the column vector $S = (S(V\_1),S(V\_2),\dots,S(V\_n))$, then there is a matrix $n\times n$ $M$ such that each iteration maps $S$ to $MS$. If the underlying graph is strongly connected, it looks like this Markov chain is irreducible, ergodic, aperiodic, and all its states are recurrent. From this you should be able to deduce that it has a stationary distribution $\pi$ and that the stationary distribution is the unique limiting distribution of the chain, hence the algorithm eventually converges. You should check all of this yourself carefully; I haven't checked any of this.

The rate of convergence will be dependent on the magnitude of the second-largest eigenvalue of the Markov chain.

Look at the analysis of PageRank for a detailed, worked example applying these concepts to a similar algorithm. This analysis can be found in many textbooks and algorithms courses.
> 2 votes

# Answer
I have read the article and I will address some concerns to keep you on the right track.

Since the smaller window behaves better, the convergence rate also decreases with longer window - very bad indicator. The F-measure has serious issues as statistic, but the $E$ indicator is not even a metric, this mere fact alarms in very nasty way, the convergence to arbitrary threshold might be possible, but the outcome is not conservative. In simple English even when it converges with error as small as $0$, this does not imply working solution yet.

As authors stated the maximum recall is strictly below $100%$, so this implies the $F-measure$ cannot be arbitrary good, hence the threshold is limited and when you go below critical level, it must diverge - so this is not arbitrary good but limited.

The score is not known in advance, but statistic used assumes real and , also you cannot set damping factor $d$ in range \[0,1\]. The error is calculated from consecutive iterations, so putting equiscore result in two iterations (let me say ambigous, or identical) it stops algorithm from scoring.

Another assumption comes from N-grams, it gives satisfactory bigrams after analysing over $10^9$ words  (sorry, non-english reference).

So summimg it up, you cannot prove it since some statements are false. You can put constraints from elements constituting the model, make assumption that you can squeeze all subproblems to the maximum, and this gives you bound how good is the model at best - since this is not arbitrary good as paper claims, this contradicts the statement, because it cannot converge when constants given aim at result better than calculated bound.
> 1 votes

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


# Question
Title: How to determine the dimensions of the bias vector in a Convolutional layer (tensor flow)?
In the Deep MNIST Tutorial for Tensor Flow, (and in general), we create a convolutional layer with a weight tensor, say W, of shape (patch dims, #input channels, # output channels). However, when we define the bias tensor, b, its shape is only (#output channels).

When we convolve W and the input x, with correct padding, we will get a volume with depth = #output channels. How can we add a single bias vector to such a volume?

Are we supposed to expand the bias vector to take on the spatial dimensions of the input x?

# Answer
No. The bias vector should indeed have the same dimensions as the output vector (not the dimensions of the input). In a neural network, after summing the weights times the inputs, the bias is added pointwise, then you apply the activation function (e.g., ReLu). The equation for a single neuron is something like

$$y = f(\sum\_i c\_i x\_i + c\_b)$$

where $x\_1,\dots,x\_n$ are the inputs, $c\_1,\dots,c\_n$ are the weights on the inputs, $c\_b$ is the bias, and $f$ is the activation function. Notice how we have one bias number per neuron, i.e., per output. (This equation gets modified a bit for convolutional neural networks but the relevant part still remains the same: we have one bias value per output.)
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Poly-time reduction from HAMPATH to HAMPATH-E
I need to prove that HAMPATH-e = { \< G,s,t,e \> | G is directed graph, s, t are vertices and e a edge } there is hamiltonian path between s to t that cross the edge e is an NP complete. i've already prove it's in NP. now i need to show poly-time reduction from HAMPATH to HAMPATH-e but i cant figure it out. any suggest?

# Answer
> 1 votes
You haven't specified which version of HAMPATH you're using, so I'll assume that for you, HAMPATH consists of all triplets $\langle G,s,t \rangle$ such that $G$ is a graph which contains a Hamiltonian path from $s$ to $t$. In that case, you can reduce HAMPATH to HAMPATH-E as follows: add a new vertex $s'$ and an edge $(s',s)$, and ask for a Hamilton path from $s'$ to $t$ through the edge $(s',s)$.

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


# Question
Title: Context-free and context-sensitive grammars in FSM with counters
Consider an extension of finite-state machines that utilizes a finite set $C$ of counters. Let's call them *counter automata*. Before execution, each counter $c\in C$ is set to zero. Every transition, aside from reading a character (possibly $\epsilon$), performs a *counter operation* – it either increments or decrements some counter $c$ by one ($c{+}{+}$ and $c{-}{-}$, respectively). Decrementation of a counter is forbidden if the counter is set to zero. Acceptation is done by accepting states, regardless of counter values. Alphabet is of finite size.

Is every context-free language accepted by a counter automaton? Is every language accepted by counter automata a context-sensitive one?

Please note that counter automata differ from counter machines (at least I can't prove that they're equal). The counters mustn't go below zero and there's basically only `JUMP NOT ZERO` operation available, aside from `INCREMENT` and `DECREMENT`.

I think that we can simulate a finite stack using a finite number of counters. We'd remember both the top and the bottom of the stack in states, and counter values would represent symbols on stack. Unfortunately, this stack would have fixed size. I don't know how to continue.

# Answer
> 4 votes
These counter automata have power incomparable to pushdown automata. In particular they are strictly weaker than counter machines as they have no proper zero test (if zero then .. else ..). Technically they are known as partially blind multicounter. Blind as they cannot act on zero, partially as they store only nonnegative numbers, and block when a counter is less than zero. As a language accepting device they are equivalent to Petri nets. They have been studied for instance by Greibach.

---
Tags: automata, computation-models
---


# Question
Title: Concatenation of $a^p$ and $a^m$ where $p$ and $m$ are primes, is irregular?
I believe that the concatenation $a^pa^m$ where $p$ and $m$ are primes is not regular, since I can show that $a^p$ is not regular using the pumping lemma, therefore there is no NFA for the 1st part, therefore the concatenation cannot be regular (I.e. there is no NFA to do the lambda transition)

Is the above reasoning correct?

# Answer
No, non regular languages are not closed under the concatenation, therefore the premise is wrong. See Proving that non-regular languages are closed under concatenation for a counterexample.
> 3 votes

# Answer
Contrary to the accepted answer, the language is irregular, but the reasoning is wrong. Instead of requiring m to be a prime, require m to be just any integer ≥ 0. Your argument would stay intact, but the language is actually the regular language $a^n$ for n ≥ 2.

(The accepted answer claims wrongly that the concatenation would always have an even number of a's, when obviously the number of a's can be 2 + p for any odd prime p).

David, I'm deeply disappointed with you. The usual method of demonstrating that an argument is wrong is to show that if the argument was right, it would "prove" something wrong. That's what I did. The argument that the poster gave could be used identically to prove something that is obviously incorrect, therefore the argument is wrong.

The argument given *only* used that $a^p$ where p is prime was irregular. Nothing about the second language $a^m$, m prime, was used at all. Therefore for the argument to be correct, the concatenation of $a^p$, p prime, with *any* other language would have to be irregular. Which is incorrect.
> -2 votes

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


# Question
Title: Community detection in weighted directed graphs for fixed number of communities
I have a weighted directed graph $G=(V,E)$ with positive weights. Say these vertices represent cities and the weight $w : V\_1 \rightarrow V\_2$ represents number of students moving into other cities for college. Note here that a city $A$ may have a small population and it may be sending a major proportion of it's outgoing students to another city $B$. If the converse holds true for city $B$, in that, most of it's incoming students come from city $A$ as a proportion of the entire incoming population, we say the weight of the edge connecting city $A$ to city $B$ should be high. So one can think of formalizing the above as a function of $\\% inflow$ and $\\% outflow$ problem. Now an algorithm like Gervin-Newman algorithm will find communities in such a graph. Here the number of communities detected increases over the number of cities considered. Is there a community detection algorithm for weighted directed graphs where I can pre-specify the number of communities I will be looking to get as output.

# Answer
There are lots of community detection algorithms that need the number of communities as input. For example, Bigclam \[1\], a matrix factorization approach, needs the number of communities as input. Another example is the seed expansion \[2\] method that needs the number of communities as input. I'm sure there are many algorithms that take the number of communities as input, but you need to do some research and find the one that is best suitable for you. Looking at these algorithms may be a good start.

You may also think about your own community detection algorithm specific to your problem. For example, you can use seed expansion and start with $k$ seeds (cities) and try to expand those seeds whenever *appropriate* (appropriate is a vague word, you need some calculations to see if an expansion is appropriate or not).

\[1\] Yang, Jaewon, and Jure Leskovec. "Overlapping community detection at scale: a nonnegative matrix factorization approach." Proceedings of the sixth ACM international conference on Web search and data mining. ACM, 2013.

\[2\] Whang, Joyce Jiyoung, David F. Gleich, and Inderjit S. Dhillon. "Overlapping community detection using seed set expansion." Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. ACM, 2013.
> 2 votes

# Answer
A very simple algorithm is as follows:

```
while #components < n
   delete the lightest edge in the graph

```

But perhaps you want to define more precisely what you want from your algorithm, e.g. which measure you want to maximize. Most community detection algorithms have some tuneable parameters.
> 0 votes

---
Tags: algorithms, cluster, clustering
---


# Question
Title: Can a graph have multiple identical elements?
Can a graph have multiple nodes that have the same value ? For instance, could a graph holding numbers have the same number present multiple times across the itself ?

My current approach is to not allow the insertion of the same element multiple times, and to instead enable an element to have an associated value, is it correct ?

Thank you.

# Answer
> 4 votes
Graphs don't have values. Graphs don't hold numbers. You don't insert a value into a graph. Graphs have vertices and edges.

You can augment a graph to associate each vertex (node) with a number, if you wish. If you do that, it's up to you to define whether or not you allow two different vertices to have the same number or not. There is no universal answer.

# Answer
> 1 votes
From your comment on D.W.'s answer, it seems to me that you're confusing a graph (the mathematical) object and an implementation of a graph in some programming language on some computer.

Mathematically, a graph consists of two sets $V$, and $E \subseteq V\times V$. There is nothing special about these sets, so vertices don't contain numbers, they don't have a "way to differentiate them", they're just elements of a set, and hence by definition, different. (As an aside, unless you're working with a rather unhelpful set theory, you will have at least some notion of equality, so you can use that to tell if two objects are the same.)

When implement a graph as a data structure, then the answers to all your questions are "it depends on how you want to do it". You can label things, you can not label things, vertices can also be containers, edges can also be containers, they can all be objects if you're using an OO language, or you can just have a bunch of arrays that store all the information however you want and you write code to piece it all together. There's no single right way to do it, you have to work out what makes sense in the situation you're in.

---
Tags: graphs
---


# Question
Title: Resource bounded reductions for RE-Complete problems
Given that the halting problem is RE-Complete, we can reduce any problem in RE to an instance of the halting problem. Are there are any results on the time-bounds for this reduction? Can we do this reduction in polynomial time in general? Exponential time? Polynomial space?

On the surface, defining an oracle machine like $P^{H}$, where $H$ is a black-box that solves the halting problem in $O(1)$ time seems to provide a tremendous amount of power over $P$ alone. However, if the reduction from a problem in $P$ (primes, 2-SAT, etc) to the halting problem takes exponential time (or worse!) then $P^{H}$ isn't *that* much more powerful than $P$ in terms of what it can solve *quickly*.

# Answer
> 3 votes
The reduction from $M$ to $HALT$ is essentially the function $x \mapsto \langle x, M\rangle$. This function can be computed very easily in linear time.

$P^{HALT} = Exp^{HALT} = Rec^{HALT}$. The computation you want to perform inside your reduction can be delegated to $HALT$ as part of $M$ in the reduction, i.e. just include the code for wherever you want to do inside your reduction and passed it on to $HALT$ and $HALT$ will execute that for you.

Let's say your reduction from $M$ to $HALT$ is $N$. We can define a new reduction as $x \mapsto \langle x, HALT \circ N \rangle$ from $M$ to $HALT$. The new reduction only attaches a fixed string (the code of $HALT \circ N$) to its input $x$ and computable easily in linear time.

The possibility of delegating work in reduction to $HALT$ is the reason that the reduction class doesn't matter (as long as your class of reductions are computable functions and powerful enough to attach strings) and we end up with the same class of functions when attach a $HALT$ oracle whether the class of reductions is $P$ or $Exp$.

# Answer
> 1 votes
When inputs for the halting problem are encoded as  prefixfree(Turing\_machine) || TM's\_input ,  even DFAs can do that reduction:

Let Me be an enumerator and let M be a machine that halts if and only if Me outputs M's input.  Now, regardless of what prefix-free code `prefixfree` is, "output prefixfree(M) followed by the reduction's input" describes a DFA reducing to the halting problem.
(If there's no prefix-free code for which that's an acceptable encoding of halting problem instances, then you'll need to be more specific.)

---
Tags: complexity-theory, polynomial-time, halting-problem, oracle-machines
---


# Question
Title: Computing maximum-cost subtree that uses at most k edges
I'm looking for an efficient algorithm for the following problem:

Input: a binary, complete tree with a cost on each edge, an integer $k$
Output: the maximum-cost subtree containing $\le k$ edges

For purposes of this problem, a subtree is defined to be a connected subset of edges. Each edge of the tree has a cost, and the cost of a subtree is the sum of the costs of the edges in the subtree.

Only edges have a cost, which is always positive. The tree always has a root node from which only one path originates and from which we must search, in the example it is the node numbered **1**. I read somewhere that it's possible to use a hashing function to compute it, but there was no explanation given.

I would also be interested to learn of an algorithm that works for graphs that aren't just binary trees.

Here's an example, with the desired subtree marked in yellow:

# Answer
> 4 votes
Say our tree is $T = (V, E)$ with weight function $w : E \to \mathbb{Q}$ and $|V| = n$, and we are looking for the maximum-weight subtree with at most $k$ edges.

There is a $\Theta(nk^2)$-time and $\Theta(nk)$-space algorithm for binary trees that uses ideas from dynamic programming.

*Idea:* Store in every node $v$ the maximum weight obtainable using $i \in 1, \dots, k$ edges for a subtree rooted in $v$, as well as two pairs $(b\_l, k\_l)$ and $(b\_r, k\_r)$ for each $i$ that indicate if the left resp. right edges is chosen, and how many edges are chosen from each subtree; that is, $b\_l + k\_l + b\_r + k\_r = i$. Compute these numbers bottom-up; the leaves initialize with all zeroes.

*Details:*

```
for v ∈ V {
  for i ∈ [1..k] {
    v.maxWeight[i]   = 0
    v.chooseLeft[i]  = 0
    v.edgesLeft[i]   = 0
    v.chooseRight[i] = 0
    v.edgesRight[i]  = 0
  }
}

globalMax = [null, 0, -1]

def annotate(v) {
  if v is not a leaf {
    annotate(v.left)
    annotate(v.right)

    for i ∈ [1..k] {
      for j ∈ [0..i] {
        w  =   [j > 0]   * w((v, v.left))  + v.left.maxWeight[max(0,j-1)]
             + [i-j > 0] * w((v, v.right)) + v.right.maxWeight[max(0,i-j-1)]

        if w > v.maxWeight[i] {
          v.maxWeight[i]   = w
          v.chooseLeft[i]  = min(j,1)
          v.edgesLeft[i]   = max(0,j-1)
          v.chooseRight[i] = min(i-j,1)
          v.edgesRight[i]  = max(0,i-j-1)
        }
      }

      if v.maxWeight[i] > globalMax[2] {
        globalMax = [v, i, v.maxWeight[i]]
      }
    }
  }
}

annotate(T.root)

```

What remains then is to move top-down from `globalMax[0]` and follow the `chooseX[_]` links with `edgesX[_]` to construct the optimal subtree with `globalMax[1]` edges and weight `globalMax[2]`.

Proof of correctness (by induction) and analysis are elementary.

The idea extends to trees of higher degree but then the factor $k^2$ changes to something more vicious; every node contributes something of the order of $k^{\operatorname{deg}(v)}$ then, if implemented naively.

# Answer
> 3 votes
I'll describe an extension of @Raphael's answer for arbitrary trees. It's probably not relevant for OP, but it might be for someone else.

The basic idea is the same. We use dynamic programming and our state is $dp\[x\]\[y\]$ = optimal cost for acquiring a $y$-edge connected subtree rooted in node $x$. As Raphael stated, for binary trees, it's as simple as iterating over how many edges we take from each subtree:

**Edit**: These formulas don't account for adding the node-son edges to the answer and possibly other details. The heart of the solution lies in the conceptual approach and is not affected by this.

$dp\[x\]\[y\] = max(dp\[son\[x\]\[0\]\]\[i\] + dp\[son\[x\]\[1\]\]\[y - i\], i = 0..y)$

Now, it would seem that if the degree were limited by three, we should iterate over how much we take from *each* of the first two subtrees. But we don't. Consider the exact same recurrence as a above, with a notational twist.

$dpFirstTwo\[x\]\[y\] = max(dp\[son\[x\]\[0\]\]\[i\] + dp\[son\[x\]\[1\]\]\[y - i\], i = 0..y)$

Ok so we've just ignored the third son. To take care of him, we'll do this again, but iterating over how many edges we take from the first two sons *combined*, which we have stored in $dpFirstTwo$.

So we have:

$dp\[x\]\[y\] = max(dpFirstTwo\[x\]\[i\] + dp\[son\[x\]\[2\]\]\[y - i\], i = 0..y)$

This can be easily extended. The main idea is that before processing the $i$-th son, we already have computed a, let's call it, $dpFirst(i-1)sons\[x\]\[y\]$ table. And we can combine these results with the $i$-th son's contribution in an identical manner with the binary tree case.

Also, I claim that the complexity can come down to $O(N ^ 2)$ *overall*, where $N$ is the vertex count. This is better than $O(N K ^ 2)$ for most $K$'s. To achieve this complexity, you just have to take care and not try to compute or iterate over states that cannot exist: A subtree with $5$ nodes cannot produce a $7$ edge subtree. If you do this, for each node you will do work proportional to the sum of pairwise products of sons subtrees sizes. Because these, in total, amount to all the pairs of nodes in the tree, we obtain the desired $O(N ^ 2)$ bound.

An implementation can be tested here: http://main.edu.pl/en/archive/pa/2007/bar. (You need $O(N ^ 2)$ time for 100 points)

---
Tags: algorithms, graphs, optimization, trees
---


# Question
Title: How do you call alternatives in the grammatical productions?
I have encountered a question, which asks what is a *syntactic form*. This motivated me to ask myself, what is the anatomy of the grammatic rule,

```
     S ::= A | B | C

```

Anatomy established that `S` is called *LHS* whereas `A | B | C is` called expectedly *RHS*. But, how do you call the individual alternatives within the RHS? Is it related to your syntactic forms?

# Answer
1. > how do you call the individual alternatives within the RHS?

As @Rafael mentioned, they are called *alternatives*.

Parsing Techinques: A Practical Guide, 2nd ed. (2008) by D. Grune and C.J.H. Jacobs, page 15:

> There is a more compact notation, in which several right-hand sides for one and the same left-hand side are grouped together and then separated by vertical bars, **|**. This bar belongs to the formalism, just as the arrow $\to$, and can be read “or else”. The right-hand sides separated by vertical bars are also called *alternatives*.

2. > Is it related to your syntactic forms?

From the same source (p. 13):

> Non-terminals \[`S`, `A`, `B`, `C` in the example\] are called (grammar) variables or *syntactic categories* in linguistic contexts.

It seems the terms *syntactic form* and *syntactic category* are used somewhat interchangeably. So, if an alternative is a variable, then it represents a syntactic form, but if it has more complex structure (it can contain terminals, or several non-terminals), then we might say that from the point of view of the grammar's author the alternative does not represent a syntactic form. But someone else can always turn it into one by defining a new non-terminal with an appropriate RHS.

Since B.C. Pierce's syntactic forms include terminals (`true`, `false`, `0`), I agree with the accepted answer that the term *syntactic form* is used somewhat informally and is not defined precisely.
> 4 votes

---
Tags: terminology, formal-grammars
---


title: Meaning behind 1/ϵ in FPTAS

text:
# Question
Title: Meaning behind 1/ϵ in FPTAS
I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS.

> A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size and also polynomial in $1/\epsilon$.

In this explanation, what does the $\epsilon$ stand for?

# Answer
> 6 votes
Suppose that your problem is a minimization problem: on instance $I$, you output a solution $O$ which should minimize some function $f(O)$. We say that an algorithm is a $(1+\epsilon)$-approximation if on instance $I$ it outputs a solution $S$ which satisfies $$ f(S) \leq (1+\epsilon) f(O) $$ for an optimal solution $O$. We also say that $S$ is a $(1+\epsilon)$-approximate solution.

An FPTAS is an algorithm that gets as input an instance of size $n$ and a number $\epsilon\>0$ (let's not worry about how $\epsilon$ is represented), returns a $(1+\epsilon)$-approximate solution, and runs in time $O(n^C (1/\epsilon)^D)$ for some constants $C,D\>0$.

Given an FPTAS, you can extract a polynomial time $(1+\epsilon)$-approximation algorithm for any $\epsilon \> 0$; furthermore, the dependence of the running time on $\epsilon$ is polynomial (in $1/\epsilon$).

A PTAS, in contrast, is an algorithm gets as input an instance of size $n$ and a number $\epsilon\>0$, returns a $(1+\epsilon)$-approximate solution, and *for any fixed $\epsilon \> 0$*, runs in polynomial time. That is, for every $\epsilon \> 0$ there exist constants $A\_\epsilon,C\_\epsilon$ such that the running time of the algorithm is at most $A\_\epsilon n^{C\_\epsilon}$.

Again, given a PTAS, for any $\epsilon \> 0$ we can extract a polynomial time $(1+\epsilon)$-approximation algorithm. This time, however, the dependence of the running time on $\epsilon$ can be arbitrary.

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


# Question
Title: How do bridges divide a larger network into smaller broadcast domains?
I am recently brushing up my computer network knowledge, and came across a seemingly peculiar statement:

> A network bridge divides a network into smaller broadcast domains.

As far as I could grasp the details, a bridge operates on the two lower layers of the ISO OSI model - the *physical* and the *data link* layers. What this means is bridge selectively forwards data link frames on the basis of the destination MAC address that can be found on each received frame.

But, the doubt arises when we consider the fact that the broadcasts are achieved using a broadcast IP address of that particular network. Now, due to the broadcast address being an entity/property of the network layer, should principally be not paid attention to by the bridge, and be flooded into all the interfaces available to it.

Then, how exactly does the bridge manage to filter the broadcast packets?

# Answer
> 3 votes
After quite a bit of research through YouTube and whatnot, I finally managed to find the answer.

A bridge (or a switch, both being data-link layer devices) DOES NOT divide the broadcast domains of the VLAN (the virtual LAN is formed by connecting the different physical segments using the bridge/switch).

A broadcast is sent with a special MAC address `FF:FF:FF:FF:FF:FF` (48 bits of 1s), of which the bridge/switch has no entry in its bridge table (and for that matter, will never have). The essential point to be noted here is that a bridge/switch follows a learning approach, in which until it is absolutely sure on which of it's port (or interface) a MAC address lies, it just forwards the frame to all the ports (except the one from which the frame has arrived). Hence, the bridge/switch, having no details of the destination MAC address of the broadcast frame, will go on to forwarding the frame to all of its ports (except one, the one from which it arrived).

What this means is that a bridge/switch cannot break the broadcast domain of the VLAN it is forming.

More related information:

https://youtu.be/reXS\_e3fTAk?t=335

---
Tags: computer-networks, network-flow
---


# Question
Title: Are there repositories of automatically generated (spam) webpages?
I'm interested to see if I can use machine learning/network analysis methods to automatically detect automatically generated (spam) webpages. I'm particularly interested in webpages that look structurally like a non-spam website, but on closer inspection are total rubbish.

If I want to test a method, I'd need some way of accessing (or generating) these webpages.

> **Question**: Where can I access automatically generated (spam) webpages?

Here's a sample of the kind of webpage I'm thinking about:

Image source

# Answer
> 3 votes
> Question: Where can I access automatically generated (spam) webpages?

You could use:

* a parody generator program.

They're usually based on Markov chains (e.g. SubredditSimulator) or context-free grammars (e.g. the well known SCIGen... according to the authors "with Markov chains you might get something syntactically correct, but it is likely to be boring"!).

Also a cut-up technique could be enough.
* a (web spam) dataset. The WEBSPAM-UK2007 collection is one of the largest and cleanest (and it's open). A description of the dataset can be found in *A Reference Collection for Web Spam* (the paper describes WEBSPAM-UK2006 but it's still valid).

You should check if it's *too broad*: the collections includes many different web spam aspects as possible (pages that are only advertising, pages with unrelated links, pages that automatically redirect...) and you seems only interested in pages that contain machine generated content.
* the spam messages in the email: email spammers often include **URLs** in their spam messages. Following those links you can store the HTML content. You should add a few heuristics to identify some false positives (e.g. exclude Alexa's Top 500 list and use SiteAdvisor's rating system to compile a whitelist).

This is the method used to create another well known dataset: Webb Spam Corpus (the original corpus was collected by Steve Webb). Further details are contained in Introducing the Webb Spam Corpus: Using Email Spam to Identify Web Spam Automatically (Steve Webb, Jamesa Caverlee, Calton Pu).

---
Tags: reference-request, machine-learning, natural-language-processing, data-sets
---


# Question
Title: What is the point of delimiters and whitespace handling
I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function regarding skipping the whitespace?

Namely, spec says

> Each lexical element is either a delimiter, an identifier (which may be a reserved word), an abstract literal, a character literal, a string literal, a bit string literal or comment. In some cases an explicit separator is required to separate adjacent lexical elements (namely when, without separation, interpretation as a single lexical element is possible). A separator is either a space character (SPACE or NBSP), a format effector, or the end of a line.

I also see a definition

```
relative_pathname ::= { ^ . } partial_pathname

```

where `.` is a delimiter but `^` is not. I do not understand why the difference. Moreover, ^ is a special character that can be only a part of `"string literal"`, `'char literal'` or `/extended identifier/` and I don't understand how to deliver this character to the path parser.

Anyway, I wonder what to do with pieces of text smashed to each other like `11'c'` or `"this is string litral"with_some_identifier`. Mine current lexer produces string\_literal followed by identifier. However, I feel that others don't do that. What is the common practice for lexing and whitespace skipping -- when whitespace is it mandatory and when is it optional? How do you specify that to the parser/lexer? I ask because do not see that parsers/lexers specify a lot of whitespace or separators in the production rules. Despite this stuff must be ubequitos, in practice, I do not see it at all. In JavaCC, for instance, you just specify whitespace chars in SKIP and it does the rest itself. What is the convention? I see that parser combinators support lexical.reserved words and lexical.delimiters. What is the purpose?

I guess that I can supplement every definition of identifier, delimiter and literal with optional whitespace prefix. Now, is it right that only identifiers and literals have to be separated by delimiters or whitespace? How do I ensure that?

# Answer
> Now, is it right that only identifiers and literals have to be separated by delimiters or whitespace? How do I ensure that?

If by "right" you mean it is the case in every programming language, then no, it is not right, and probably no non-trivial lexical statement would be either.

In many languages, integer literals do not have to be separated from a following identifier; in other languages, they do. In most languages, `<=` is different from `< =`, so identifiers and numbers are not the only classes of tokens which require explicit separation. (If you don't consider `<` and `=` to be "delimiters", then you cannot say that identifiers need to be separated by whitespace or delimiters, either, since `a<b` is normally valid.)

Maximal munch is a very common lexical algorithm. This views the input to be a sequence of lexemes where each lexeme starts precisely following the previous lexeme and continues as far as possible (so that if two lexemes are possible at a given point in the source code, the longest one is chosen regardless of whether the rest of the input would be valid or not). Not all lexemes are tokens; the set of lexemes includes ignorable whitespace, for example, which is recognized by the tokeniser but does not otherwise participate in syntactic analysis.

However, most languages have idiosyncratic exceptions. Consider the handling of `<::` in C++ or `1..2` in D; both of these require an explicit exception to the maximal-munch rule. A different issue is the handling of regular-expression literals in ECMAscript (and other languages), in which `/` and `/=` could be tokenised as a simple operator token, or they could be the first part of a regular expression literal. Which option is chosen depends on the immediate syntactic context. Yet another deviation from the above model is found in languages like Python and Haskell where layout (whitespace used as indententation) is sometimes syntactic.

To the extent that a language specification uses the maximal munch algorithm, whitespace is mandatory *precisely* in those contexts where maximal-munch would produce a different tokenisation. In such languages, whitespace is always discarded (after tokenisation) and there is no need to ensure it is supplied.

There is no global institution which regulates computer language designers. Each language community develops according to its own philosophy, customs, eccentricities and equivocations, and there is no higher truth to which one can appeal.

---

Particular languages may be based on a different tokenisation model, so you cannot make general language-independent statements based on the behaviour of a single language. In the comments streams, it has been suggested that this question actually applies to VHDL and that VHDL does not conform to the maximal munch model. The text cited in the OP apparently comes from section 13.2 of the VHDL Reference Manual. However, it seems clear (even from the text quoted in the OP), that the design is not much different from maximal-munch. I repeat, with emphasis added:

> The text of each design unit is a sequence of separate lexical elements. Each lexical element is either a delimiter, an identifier (which may be a reserved word), an abstract literal, a character literal, a string literal, a bit string literal, or a comment.
>
> **In some cases an explicit separator is required to separate adjacent lexical elements (namely when, without separation, interpretation as a single lexical element is possible).** A separator is either a space character (SPACE or NBSP), a format effector, or the end of a line. A space character (SPACE or NBSP) is a separator except within a comment, a string literal, or a space character literal.

So that makes it clear that the only case in which separation is obligatory is where the concatenated tokens could be tokenised as a (longer) combined token, which is essentially the maximal-munch rule.
> 6 votes

# Answer
As an interesting example where white space is absolutely important is the Swift language. Take the character '-' which matches the parsing rules for operator. But is it a binary or unary operator, and if it is unary, does it bind from the left or the right?

It depends on white space: White space on the left but not on the right -\> left unary (for example x = -y). White space on the right but not on the lift -\> right unary (for example x = y- which is invalid because there is no right unary minus operator). White space on both sides or on neither side = binary operator (x = y-z or x = y - z, but x = y- z or x = y -z are invalid).
> 0 votes

---
Tags: programming-languages, parsers, language-design, lexical-analysis
---