title: Understanding serialization

text:
# Question
Title: Understanding serialization
I am a software engineer and after a discussion with some colleagues, I realized I do not have a good grasp of the concept serialization. As I understand, serialization is the process of converting some entity, such as an object in OOP, to a sequence of bytes, so that the said entity can be stored or transmitted for subsequent access (the process of "deserialization").

The trouble I have is: aren't all variables (be it primitives like `int` or composite objects) already represented by a sequence of bytes? (Of course they are, because they are stored in registers, memory, disk, etc.)

So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? What intricacies have I missed?

# Answer
> 42 votes
If you have a complicated data structure, its representation in memory might ordinarily be scattered throughout memory. (Think of a binary tree, for instance.)

In contrast, when you want to write it to disk, you probably want to have a representation as a (hopefully short) sequence of contiguous bytes. That's what serialization does for you.

# Answer
> 28 votes
> The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes? (Of course they are, because they are stored in registers, memory, disk, etc.)
>
> So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? What intricacies have I missed?

Consider an object graph in C with nodes defined as this:

```
struct Node {
    struct Node* parent;
    struct Node* someChild;
    struct Node* anotherLink;

    int value;
    char* label;
};

//

struct Node nodes[10] = {0};
nodes[5].parent = nodes[0];
nodes[0].someChild = calloc( 1, sizeof(struct Node) );
nodes[5].anotherLink = nodes[3];
for( size_t i = 3; i < 7; i++ ) {
    nodes[i].anotherLink = calloc( 1, sizeof(struct Node) );
}

```

At runtime the entire object `Node` graph would be scattered around the memory space, and the same node could be pointed-to from many different Nodes.

You can't simply dump memory to a file/stream/disk and call it serialized because the pointer values (which are memory addresses) couldn't be de-serialized (because those memory locations might already be occupied when you load the dump back into memory). Another problem with simply dumping memory is that you'll end up storing all kinds of irrelevant data and unused space - on x86 a process has up to 4GiB of memory space, and an OS or MMU only has a general idea of what memory is actually meaningful or not (based on the memory pages assigned to a process), so having `Notepad.exe` dump 4GB of raw bytes to my disk whenever I want to save a text file seems a bit wasteful.

Another problem is with versioning: what happens if you serialize your `Node` graph on day 1, then on day 2 you add another field to `Node` (such as another pointer value, or a primitive value), then on day 3 you de-serialize your file from day 1?

You also have to consider other things, like endianness. One of the main reasons why MacOS and IBM/Windows/PC files were incompatible with each other in the 1980s and 1990s despite ostensibly being made by the same programs (Word, Photoshop, etc) was because on x86/PC multi-byte integer values were saved in little-endian order, but big-endian order on the Mac - and the software wasn't built with cross-platform portability in mind. Nowadays things are better thanks to improved developer education and our increasingly heterogeneous computing world.

# Answer
> 15 votes
The tricky is actually already described in the word itself: "**serial**ization".

The question is basically: how can I represent an arbitrarily complex interconnected cyclic directed graph of arbitrarily complex objects as a linear sequence of bytes?

Think about it: a linear sequence is kind-of like a degenerate directed graph where every vertex has *exactly one* incoming and outgoing edge (except the "first vertex" which has no incoming edge and the "last vertex" which has no outgoing edge). And a *byte* is obviously less complex than an *object*.

So, it seems reasonable that as we go from an arbitrarily complex graph to a much more restricted "graph" (actually just a list) and from arbitrarily complex objects to simple bytes, information *will* be lost, if we do this naively and don't encode the "extraneous" information in some way. And that's exactly what serialization does: encode the complex information into a simple linear format.

If you are familiar with YAML, you might have a look at the anchor and alias features which allow you to represent the idea that "the same object may appear in different places" in a serialization.

E.g. if you have following graph:

```
A → B → D
↓       ↑
C ––––––+

```

You could represent that as a list of linear paths in YAML like this:

```
- [&A A, B, &D D]
- [*A, C, *D]

```

You could also represent it as an adjacency list, or an adjacency matrix, or as a pair whose first element is a set of nodes and whose second element is a set of pairs of nodes, but in all of those representations, you need to have a way of referring backwards and forwards to *existing* nodes, i.e. *pointers*, which you generally don't have in a file or a network stream. All you have, in the end, is bytes.

(Which BTW means that the above YAML text file itself also needs to be "serialized", that's what the various character encodings and Unicode transfer formats are for … it's not strictly "serialization", just encoding, because the text file is already a serial / linear list of codepoints, but you can see some similarities.)

# Answer
> 13 votes
The other answers already address complex object graphs, but it's worth pointing out that serializing primitives is also non-trivial.

Using C primitive type names for concreteness, consider:

1. I serialize a `long`. Some time later I de-serialize it, but ... on a different platform, and now `long` is `int64_t` rather than the `int32_t` I stored. So, I need to either be very careful about the exact size of every type I store, or store some metadata describing the type and size of every field.

Note that this *different platform* could just be the same platform after a future recompile.
2. I serialize an `int32_t`. Some time later I de-serialize it, but ... on a different platform, and now the value is corrupt. Sadly I saved the value on a big-endian platform, and loaded it on a little-endian one. Now I need to establish a convention for my format, or add *more* metadata describing the endiannness of each file/stream/whatever. And, of course, actually perform the appropriate conversions.
3. I serialize a string. This time one platform uses `char` and UTF-8, and one `wchar_t` and UTF-16.

So, I'd claim that reasonable-quality serialization isn't trivial even for primitives in contiguous memory. There are lots of encoding decisions you need to either document, or describe with inline metadata.

Object graphs add another layer of complexity on top of that.

# Answer
> 6 votes
There are multiple aspects:

# Readability by the same program

Your program has stored your data somehow as bytes in the memory. But it might be arbitrarily scattered across different registers, with pointers going back and forth between its smaller pieces \[edit: As commented, physically the data is more likely in main memory than a data register, but that does not take away the pointer problem\]. Just think of a linked integer list. Each list element might be stored at a totally different place and all that holds the list together are the pointers from one element to the next. If you were to take that data as is and tried to copy it on another machine running the same program, you would run into problems:

1. First and foremost, the register adresses your data is stored in on one machine might already be used for something completely different on another machine (someone is browsing stack exchange and the browser ate all that memory already). So if you simply override those registers, good bye browser. Thus, you would need to re-arrange the pointers in the structure to fit the addresses you have free on the second machine. The same problem arises when you try to re-load the data on the same machine at a later time.
2. What if some external component points into your structure or your structure has pointers to external data, you did not transmit? Segfaults everywhere! This would become a debugging nightmare.

# Readability by another program

Let's say you manage to allocate just the right addresses on another machine, for your data to fit into. If your data is processed by a separate program on that machine (different language), that program might have a totally different basic understanding of data. Say you have C++ objects with pointers, but your target language does not even support pointers on that level. Again, you end up with no clean way to address that data in the second program. You end up with some binary data in memory, but then, you need to write extra code that wraps around the data and somehow translates it into something that your target language can work with. Sounds like deserialization, just that your starting point now is strange object scattered around your main memory, that is different for different source languages, instead of a file with a well-defined structure. Same thing, of course, if you try to directly interpret the binary file that includes pointers - you need to write parsers for every possible way another language might represent data in-memory.

# Readability by a human

Two of the most prominent modern serialization languages for web based serialization (xml, json) are easily understandable by a human. Instead of a binary pile of goo, the actual structure and content of data is clear even without a program to read the data. This has multiple advantages:

* easier debugging -\> if there is a problem in your service pipeline, you just look at the data that comes out of one service and check if it makes sense (as a first step); you also directly see if the data looks like you think it should, when you write your export interface in the first place.
* archivability: if you have your data as a pure binary goo pile, and you loose the program that is meant to interpret it, you loose the data (or you will have to spent quite some time to actually find something in there); if your serialized data is human readible, you can easily use it as an archive or program your own importer for a new program
* the declarative nature of the data serialized in such a way, also means, it is totally independent of the computer system and its hardware; you could load it into a totally differently constructed quantum computer or infect an alien A.I. with alternative facts so it accidentally flies into the next sun (Emmerich if you read this, a reference would be nice, if you use that idea for the next 4th July movie)

# Answer
> 6 votes
In addition to what the other answers have said:

**Sometimes you want to serialise things that are not pure data.**

For instance, think of a file handle or a connection to a server. Even though the file handle or socket is an **`int`**, this number is meaningless the next time the program runs. To properly recreate objects that contain handles to such things, you need to reopen files and recreate connections, and decide what to do if this fails.

Many languages these days support storing anonymous functions within objects, for instance an `onBlah()` handler in Javascript. This is challenging because such code can contain references to additional pieces of data which in turn need to be serialised. (And then there's the issue of serialising code in a cross-platform way, which is obviously easier for interpreted languages.) Still, even if only a subset of the language can be supported, it can still prove quite useful. Not many serialisation mechanisms attempt to serialise code, but see serialize-javascript.

In cases where you want to serialise an object but it contains something that isn't supported by your serialisation mechanism, you need to rewrite the code in a way that works around this. For instance, you can use enums in place of anonymous functions when there are a finite number of possible functions.

**Often you want serialised data to be terse.**

If you're sending data over the network or even storing it on disk, it can be important to keep the size small. One of the easiest ways to achieve this is to throw away information that can be rebuilt (for instance, discarding caches, hash tables, and alternate representations of the same data).

Of course, the programmer has to manually select what is to be saved and what is to be discarded, and make sure things are rebuilt when the object is recreated.

Think about the act of saving a game. Objects may contain lots of pointers to graphics data, sound data, and other objects. But most of this stuff can be loaded from the game data files and doesn't need to be stored in a save file. Discarding it can be laborious so little things are often left in. I've hex-edited some save files in my time and discovered data that was clearly redundant, like textual item descriptions.

Sometimes space isn't important but readability is—in which case you might use an ASCII format (possibly JSON or XML) instead.

# Answer
> 3 votes
Let's define what a sequence of bytes actually is. A sequence of bytes consists of an non-negative integer called the *length* and some arbitrary function/correspondence that maps any integer *i* that is at least zero and less than *length* to a byte value (an integer from 0 to 255).

Many of the objects you deal with in a typical program are not in that form, because the objects are actually made up of many different memory allocations that are in different places in RAM, and could be separated from eachother by millions of bytes of stuff you don't care about. Just think of a basic linked list: each node in the list is a sequence of bytes, yes, but the nodes are in lots of different locations in your computer's memory, and they are connected with pointers. Or just think of a simple struct that has a pointer to a variable-length string.

The reason why we want to serialize data structures into a sequence of bytes is usually because we want to store them on disk or send them to a different system (e.g. over the network). If you try to store a pointer on disk or send it to a different system, it will be pretty useless because the program reading that pointer will have a different set of memory areas available.

# Answer
> 2 votes
The intricacies reflect the intricacies of data and objects themselves. These objects can be real world objects, or computer only objects. The answer is in the name. Serialisation is the linear representation of multi dimensional objects. There are many issues other than fragmented RAM.

If you can flatten 12 five dimensional arrays and some program code, serialisation also allows you to transfer an entire computer program (and data) between machines. Distributed computing protocols such as RMI /CORBA use serialisation extensively to transfer data and programs.

Consider your phone bill. It might be a single object, consisting of all your calls (list of strings), amount to pay (integer) and country. Or your phone bill could be inside out from the above and consist of discrete itemised phone calls linked to your name. Each flattened out will look different, reflect how your phone company wrote that version of it's software and the reason that object oriented databases never took off.

Some parts of a structure might not even be in memory at all. If you have lazy caching, some parts of an object might only be referenced to a disk file, and are only loaded when that part of that particular object is accessed. This is common in serious persistence frameworks. BLOBs are a good example. Getty Images might store a huge multi megabyte picture of Fidel Castro and some meta data like the image's name, rental cost and the image itself. You might not want to load the 200 MB picture into memory every time, unless you actually look at him. Serialised, the entire file would require over 200MB of storage.

Some objects can't even be serialised at all. In the land of Java programming, you can have a programming object representing the graphics screen or a physical serial port. There's no real concept of serialising either of them. How would you send your port to someone else over a network?

Some things like passwords /encryption keys shouldn't be stored or transmitted. They can be tagged as such (volatile /transient etc) and the serialisation process will skip them but they can live in RAM. Omitting these tags is how encryption keys inadvertently get sent /stored in plain ASCII.

This and the other answers is why it's complicated.

# Answer
> 2 votes
> The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes?

Yes, they are. The problem here is the layout of those bytes. A simple `int` can be 2, 4 or 8 bits long. It can be in big or small endian. It can be unsigned, signed with 1's complement or even in some super exotic bit coding like negabinary.

If you just dump the `int` binarily from memory, and call it "serialized", you have to attach pretty much entire computer, operating system and your program for it to be deserializable. Or at least, a precise description of them.

> So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? What intricacies have I missed?

Serialization of a simple object is pretty much writing it down according to some rules. Those rules are plenty and not always obvious. Eg an `xs:integer` in XML is written in base-10. Not base-16, not base-9, but 10. It's not a hidden assumption, it's an actual rule. And such rules make serialization a serialization. Because, pretty much, **there are no rules about bit layout of your program in memory**.

That was just a tip of an iceberg. Let's take an example of a sequence of those simplest primitives: a C `struct`. You could think that

```
struct {
short width;
short height;
long count;
}

```

has a defined memory layout on a given computer+OS? Well, it does not. Depending on current `#pragma pack` setting, the compiler will pad the fields. On default settings of 32-bit compilation, both `shorts` will be padded to 4 bytes so the `struct` will actually have 3 fields of 4 bytes in memory. So now, you not only have to specify that `short` is 16 bits long, it's an integer, written in 1's complement negative, big or little endian. You also have to write down the structure packing setting your program was compiled with.

**That's pretty much what serialization is about: making a set of rules, and sticking to them.**

Those rules can be then expanded to accept even more sophisticated structures (like variable length lists or nonlinear data), added features like human readability, versioning, backward compatibility and error correction, etc. But even writing down a single `int` is already complicated enough if you only want to make sure you'll be able to read it back reliably.

---
Tags: storage
---


# Question
Title: Collision resistant Hash function in chaos cryptography
In my earlier Question asked here Help in understanding how to apply nonlinear function in hashing about chaos cryptography, since then I have come across several research papers that apply atleat theoretically chaos based cryptography. It is still an active area of research with advantages and disadvantages.

How can I prove that the has collision is minimum or collision resistance for any chaos function used for chaos based cryptography, where the chaos map is the hash function?

An algorithm to achieve cryptography hashing is the chaos based cryptographic hash function which indexes all items in hash tables and searches for near items via hash table lookup. The hash

table is a data structure that is composed of buckets, each of which is indexed by a hash code.

Two hash codes for two different messages can collide if they have the same hash code. This is often called the Birthday paradox.

The properties of a good hash function is that there should be no hash collision. This property also holds for Locality sensitive hashing where a hash function is used to search for the approximate nearest neighbor.

How can I proof this statement for chaos based hashing in cryptography? If the hashing function is a chaotic map, $f()$, then how to show the expression of collision probability? Please help.

# Answer
> 2 votes
Chaos-based encryption ain't an active area of research among the best crypto researchers; it's looking like a dead end. You might find papers published on the topic, but they're generally in lower-reputation conferences. Why is it a dead end? Because it doesn't seem to work. The schemes typically end up being either insecure, or worse than existing algorithms (e.g., slower). Basically, it initially sounded like an intriguing idea, but at this point I would advise you that studying chaos-based cryptography appears to be a waste of your time, if you want to accomplish something useful or practical. (See also https://security.stackexchange.com/q/31000/971, though it doesn't really address this point.)

You can't prove collision-resistance. Even the state-of-the-art hash functions don't come with a mathematical proof of collision-resistance. See https://crypto.stackexchange.com/q/18730/351 and https://crypto.stackexchange.com/q/26094/351 and https://security.stackexchange.com/q/5101/971.

---
Tags: proof-techniques, search-algorithms, cryptography, hashing
---


title: improve the running time

text:
# Question
Title: improve the running time
How can I use divide and conquer to improve the running time of this algorithm?

input: A sorted array of length n

output: the # of elements such that abs(A\[i\]) \<= k

# Answer
> 2 votes
You have a sorted array of n elements.

If the first element is \> k then no elements have absolute value ≤ k. (Why ?)

If the last element is \< -k then no elements have absolute value ≤ k. (Why ?)

If the first element is ≥ -k and the last element is ≤ k then all n elements have absolute value ≤ k. (Why ?)

If neither of these criteria was fulfilled then we must have n ≥ 2 (why ?). Take a subarray containing the first n/2 elements, and a subarray containing the remaining n - n/2 elements, then count the elements with absolute value ≤ k in each subarray, and add the results.

---
Tags: algorithms, divide-and-conquer, algorithm-design
---


# Question
Title: Determine if the sequence of numbers is a post order traversal of a binary tree
The question is: given a sequence of numbers, find an algorithm that determines if the sequence of numbers is in post order traversal of a binary search trees.

Up to now, I have understood the following:

* In the post order traversal of the binary tree it follows Left, Right, Root. So the Left value has to be less than the Right value.
* The last element of the sequence is the root, assuming the sequence was in the post order traversal.

I do not know how to progress further with this. Also, is there a way to create a Divide and Conquer algorithm for this?

# Answer
Probably you consider binary search trees, otherwise the exercise is a little useless.

You already concluded that your input has postorder: post-left-subtree, post-right-subtree, root. Now the value of the root determines which values belong left, and which values belong right. So you are right: this is divide and conquer. Split the numbers according to the subtrees, and repeat for each of the two subtrees.

If a split of the input does not have the form post-left-subtree \< root \< post-right-subtree, you know what to conclude from that.

An example. The sequence is 1, 5, 9, 7, 3, 13, 17, 15, 11. So the root is 11. And we can split the sequence accordingly into left and right subtrees: 1, 5, 9, 7, 3 \< 11 \< 13, 17, 15. Continue with the left and right subsequences.

Another sequence is 1, 5, 13, 9, 7, 3, 17, 15, 11. No split 'at' 11 possible.
> 3 votes

---
Tags: graphs, binary-trees, graph-traversal
---


# Question
Title: Difference between fractional knapsack & greedy solution
I am trying to understand what the difference is between the fractional knapsack problem using dynamic programming, and the greedy solution version. Im looking at an example of the fractional problem which looks like:

What's the difference between that and the greedy solution? Are you not just taking the value-per-pound in this example too but it's just not explicitly stated?

# Answer
The fractional Knapsack problem isn't solved using Dynamic Programming, but can be solved using a greedy algorithm. Item A is \\$50/unit, B is \\$5/unit and C is \\$40/unit. The greedy method is to use as much of the highest value items as possible, which gives the solution on the image.

Dynamic Programming allows you to solve the problem when you cannot split the items.
> 1 votes

---
Tags: algorithms, optimization, dynamic-programming, greedy-algorithms, knapsack-problems
---


# Question
Title: Can Von Neumann bit extraction be made more efficient?
I want to develop a previous question regarding Von Neumann debiasing /randomness extraction.

The typical solution (as posted) is to take pairs of throws and output a bit based on a comparison of the two throws. This is the most simple solution.

My problem is that it's very wasteful of input entropy. The biased die can have values 1 - 6, but only a single bit is output. So 2 x log2(6) bits in, produce 1 bit out. It's actually less as the throws may be discarded if identical. What happens if the die is a D & D D120 (Disdyakis triacontahedron - 120 sides)? You'd be inputting 13.8 bits of entropy, and getting (practically) less than 1. That's incredibly wasteful of precious entropy. Is there a clever variant of Von Neumann that can output more than a single bit at a time?

My particular interest is actually not a bigger die, but more of them. For example you simultaneously throw 6 biased regular dice. Can you get better than 1 purely random bit out per pair of throwing rounds?

# Answer
> 2 votes
Suppose you are going to throw a 6-sided die N times. You can convert that to an integer in the range $\[0,6^N-1\]$, by viewing the sequence of N outcomes as a base-6 representation of an integer. This gives you a random number chosenly uniformly at random from $\[0,6^N-1\]$.

Now pick a value of $k$ such that $2^k \< 6^N$. Let $Y = \lfloor 6^N/2^k \rfloor \times 2^k$. You can now use the following algorithm to output a $k$-bit number (much of the time):

Generate a random number from the range $\[0,6^N-1\]$ by tossing a 6-sided die $N$ times. Suppose the number you get is $x$. If $x \< Y$, then output the value $x \bmod 2^k$ (which can be viewed as $k$ bits). Otherwise, output nothing -- you will have to re-roll.

This produces a uniform random distribution on $k$-bit values. It produces output on any given attempt with probability $Y/6^N$; on average, the expected number of times you'll have to repeat this procedure is $6^N/Y$, which is a bit more than $1$ (but not much more than $1$, as long as you're not too greedy and don't pick $k$ too large).

It's possible to do a bit better, by saving information about the value of $x-Y$ when you repeat the process, but this might not make a big difference in practice.

See also Generating uniformly distributed random numbers using a coin and Is rejection sampling the only way to get a truly uniform distribution of random numbers? and How to simulate a die given a fair coin and Isn't std::bernoulli\_distribution inefficient? Designing a bit-parallel Bernoulli generator.

---
Tags: randomness, entropy
---


# Question
Title: How to construct object oriented programming in pseudo code?
I am studying a data structures course in which we have given many assignments on constructing data structures (like trees, arrays, and linked lists).

In class template, what kind of notation should I write for these operators (::,-\>) and the others operators which are used in C++? Can anyone elaborate more about writing pseudo-code for object oriented programs?

# Answer
> 3 votes
Pseudocode has no formal definition. Use whatever notation you want, as long as it is either self-explanatory (even for people unaware of C++) or explained in the text.

I suggest looking at several textbooks and papers to see what the "industry standard" is, and using something similar.

---
Tags: data-structures, programming-languages
---


# Question
Title: Which Turing machine problems are Decidable?
Let $M\_0$, $M\_1$, $M\_2$,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ?

* Given a natural number $N$, does $M\_N$ starting with an empty tape halts in fewer than $N$ steps ?
* Given a natural number $N$, does $M\_N$ starting with an empty tape halts after at least $N$ steps?
* Given a natural number $N$, does $M\_N$ starting with an empty tape halts in exactly $N$ steps?

---

I've looked some of these similar problems like :-

Prove that this language is decidable or undecidable

Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable?

I've got some idea that $TM$ problems related to $N$ steps, only the cells upto $N$ are significant.

Such problems are decidable, however long input we take.

---

Hence, I come to the conclusion that $1$st part of my problem will be decidable similar to the reasoning as given above.

Similarly, for $3$rd part, if we check $N$th cell we can say $Y/N$ hence Decidable.

But, I am stuck in $2$nd part.

(What I think is that upto $N$th cell we can check if it halted, making it semidecidable otherwise it will definitely halt after the $N$th cell. Hence, I think it is also Decidable).

---

Please let me know how much correct progress I made. I don't have solutions for these questions. Need some confirmation ?

# Answer
> 1 votes
You can simulate a given Turing machine to a given number of steps. This allows you to decide Problem 1 and Problem 3, by running $M\_N$ on the empty type for $N$ steps (or fewer, if it halts earlier).

Regarding Problem 2, assuming that $N$ is in the language if

1. $M\_N$ halts on the empty tape, and
2. $M\_N$ doesn't halt within the first $N$ steps,

then you can use this language to solve the halting problem (using the same effective enumeration). Given $N$, in order to determine whether $M\_N$ halts on the empty tape:

1. Run $M\_N$ for $N$ steps. If it halts, answer Yes.
2. Otherwise, use Problem 2 to determine whether $M\_N$ halts on the empty tape, but not within the first $N$ steps.

Hence Problem 2 is undecidable.

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


# Question
Title: Describing time complexity when internally using a function of unknown complexity
Assume that I have some functions $f$ and $g$, both implemented perfectly, where

$$ f(x, g(z)) = \sum\_{k=0}^{k=\lfloor{x}\rfloor}g(k)\quad (x \> 1)\\,. $$

Function $g$ is of unknown definition. I would like to express the time complexity of $f$ in big-O notation. My initial thought was to do something similar to:

$$ O(\sum\_{k=0}^{k=\lfloor{x}\rfloor}T\_g(k))\\,. $$

Assume $T\_g$ represents the time function of function g. However, this representation feels inadequate and irreducible for asymptotic time complexity; there should be a better way to express $T\_f$.

How do I describe, in big-O notation, the time complexity of $f$?

# Answer
> 3 votes
In complete generality there is nothing much you can say. However, in many circumstances it will be the case that $g(n)$ is monotone, and in that case you can say that $$ \sum\_{k=1}^n g(k) \leq ng(n), $$ a bound which is often quite good.

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


title: Why doesn't the string match the root?

text:
# Question
Title: Why doesn't the string match the root?
From Reading 17 of 6.005 — Software Construction:

> Exercise Reading a Grammar 4:
>
> Which strings match the root nonterminal of this grammar?
>
> ```
> root   ::= (A B)+
> A      ::= [Aa]
> B      ::= [Bb]
>
> ```
> 1. `aaaBBB`
> 2. `abababab`
> 3. `aBAbabAB`
> 4. `AbAbAbA`
>
> Answer: 2 and 3

So far so good.

> Exercise Reading a Grammar 3:
>
> Which strings match the root nonterminal of this grammar?
>
> ```
> root    ::= integer ('-' integer)+
> integer ::= [0-9]+
>
> ```
> 1. `617`
> 2. `617-253`
> 3. `617-253-1000`
> 4. `---`
> 5. `integer-integer-integer`
> 6. `5--5`
> 7. `3-6-293-1`
>
> Answer: 2, 3, and 7

In the last question, why doesn't `integer-integer-integer` match the root if it can be our first step, i.e.

`root``integer-integer-integer`

Sure, it would not be the end of the story (i.e. it would contain some non-terminals) but neither was `aBAbabAB` in the question above and yet it was accepted as a string that matched the root.

Many thanks!

# Answer
In the text, they seem to suggest that there is a way of quoting characters so that they can be used as terminals even if they have the visible form as a non-terminal. One common quoting form is quotes (`'B'`) which is illustrated.

Character classes (`[bB]`) are another quoting form. The `B` in that character class cannot be a non-terminal because it is precisely a *character*. So the non-terminal `B`, although it looks very similar, is distinct, and the `B`s in the strings are characters, necessary by the definition of string they are using.
> 1 votes

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


# Question
Title: is this an example of nominal unification?
I am thinking that is the following a problem solved by nominal unification.

$\lambda a.X = \lambda b.\lambda c.c $

where we find $X$. The answer is obvious.

The reason is that it seems in nominal unification $X$ always will be an atom, not a function such as $\lambda c.c$. The theory seems works fine with this input, just did not saw any example similar to this one.

# Answer
Sure, these unify under nominal unification. You get a unifier like $X = (b\ a)\bullet\lambda c.c$ which simplifies to $X = \lambda c.c$. Figures 1 and 3 of Nominal Unification describe the relevant details of the algorithm. In particular the transitions will be $\approx?$-abstraction-2 and $\approx?$-variable followed by $\\#?$-abstraction-2 and $\\#?$-atom.
> 3 votes

---
Tags: unification
---


title: Proof verification |A∪B| ≤ n + m

text:
# Question
Title: Proof verification |A∪B| ≤ n + m
I'm rather new to formal languages and reading up on Peter Linz's *An Introduction to FORMAL LANGUAGES and AUTOMATA*. As an exercise in the pre-requisite chapter, there's a proof. I'm not so familiar with formal proofs so I would like someone to tell me:

* Does it prove it?
* How would you make this proof stronger? I am not interested so much in seeing an alternative way to prove this (assuming mine is good) - I would rather know how I can make my proofs better in the future.

PROOF:

```
|A∪B| ≤ n + m
n = |A|, m = |B|

```

Where A & B are sets. So if I understand correctly, I want to prove that the size of the union of A & B is smaller or equal to the sum of the individual sizes of A & B. Which intuitively makes lots of sense to me.

```
|A∪B| ≤ n + m
|A∪B| ≤ |A| + |B|

```

I then try to express the right-hand side differently. If I draw it, I can see that the following holds true (U for universal set, sorry still working out those symbols):

```
|A| + |B| = |U| - |A| + |A∩B| + |U| - |B| + |A∩B|
|A| + |B| = 2|U| - |A| - |B|  + 2|A∩B| (1)

```

And also

```
|A∪B|  = |U| - |A| - |B| + 2|A∩B| (2)

```

If I substitute back into the initial equation:

```
|A∪B| ≤ |A| + |B|
|U| - |A| - |B| + 2|A∩B| ≤ 2|U| - |A| - |B|  + 2|A∩B|
|U| ≤ 2|U|

```

Which is always true.

# Answer
Here is a more streamlined version of your proof.

Notice first that $$ A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B), \\ A = (A \setminus B) \cup (A \cap B), \\ B = (B \setminus A) \cup (A \cap B). $$ All these decompositions are into disjoint sets, and so $$ |A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B| |A| = |A \setminus B| + |A \cap B|, \\ |B| = |B \setminus A| + |A \cap B|. $$ A bit of algebra shows that $$ |A \cup B| = |A| + |B| - |A \cap B|. $$ Given this, $|A \cap B| \geq 0$ implies the desired result, $|A \cup B| \leq |A| + |B|$.
> 2 votes

# Answer
A similar, shorter, proof relies on the *inclusion/exclusion principle*, namely if $A$ and $B$ are finite sets, then $$ |A\cup B| = |A| + |B| - |A\cap B| $$ (If you're not familiar with this identity, look at a small Venn diagram.) So we can conclude $$ |A\cup B| = |A| + |B| - |A\cap B| \le |A| + |B| $$
> 1 votes

---
Tags: formal-languages
---


title: CLRS RAM model Description

text:
# Question
Title: CLRS RAM model Description
I'm seeking some clarification on a description of the RAM model in CLRS on page 23, section 2.2 (Analyzing Algorithms).

Firstly, it is mentioned that we assume integers are represented with $c\cdot\log\_2 n$ bits for some constant $c\geq 1$. Now take the integer value $2$, would it not be the case that we would need more than $\log\_2 2=1$ bit to represent the integer value $2$? Since we must express two as $(10)\_2$? Perhaps the constant $c$ is supposed to account for this discrepancy.

Secondly I'm a bit confused by this statement: "We require $c \geq 1$ so that each word can hold the value of $n$, enabling us to index the individual elements...". I understand that if $c$ were $0$ or negative then that would not make any sense, however, are we also to assume then that $c$ must be an integer?

Any intuitive descriptions of these basic properties would be great or relevant examples someone can come up with.

# Answer
> 5 votes
In the RAM model, variables hold a *machine word*, and operations on machine words take $O(1)$ time. The question is how big should a machine word be. In the variant of the RAM model used in CLRS, a machine word should be large enough so that a variable can count from 1 to $n$ (this is the meaning of the phrase "enabling us to index the individual elements"). To count from 1 to $n$ you need roughly $\log\_2 n$ bits, or more accurately, $\log\_2 n + O(1)$ bits. This is why we need $c \geq 1$; note that $c$ need not be an integer.

In the RAM model, indexing an array requires that the index is held in a single variable (or at least, this is one reasonable definition). This is why it is important that the machine word is large enough to index all arrays that could appear in an algorithm. If we only consider polynomial time algorithms, then all arrays have polynomial size, and so require indices of size $\Theta(\log n)$. This is the bare minimum needed to make the RAM model useful. It turns out that a larger machine word is not usually necessary, and so $\Theta(\log n)$ is a good choice.

Another reason that we want machine words to be able to hold indices (even if we somehow modify the indexing operation to handle an index spread across several machine words) is that we want a loop of the form

```
for i from 1 to n:
     if i equals j then do something that takes O(1) time

```

to run in time $O(n)$. This implies that the operation of incrementing an index should be $O(1)$, and that the operation of comparing two indices should be $O(1)$. So we want our machine words to be large enough to contain an entire index.

---
Tags: algorithms, algorithm-analysis, computation-models
---


# Question
Title: Identifying a starting point for maximum coverage
I have 10,000 sequentially numbered items I wish to characterize. For each item, I created a list of the other items I think might have a similar characteristic.

i.e.

```
Item 1: [2,4,7,8,9,...,9489] (list contains 250 items)
Item 2: [1,4,13,23,...,9424] (list contains 12 items)
Item 3: [1,2,4,7,...,9489] (list contains 140 items)
Item 4: [1,3,7,9,...,9211] (list contains 250 items)
Item 5: [1,3,7,9,...,9221] (list contains 250 items)
Item 6: [1,2,7,25,...,9248] (list contains 241 items)
Item 7: [4,5,6] (list contains 3 items)

```

If I only have time to test 50 items, How might I choose which items to test so that the maximum number of items is represented? The identified similarity is not necessarily bi-directional - notice item 7's list contains 4,5,6 but not 1 and 3(which both have 7 in their list).

Some lists may be very similar or even identical, as seen in items 4 and 5. Testing both 4 and 5 would not achieve the maximum coverage.

# Answer
> 0 votes
It sounds like you want to select a set of 50 lists whose union contains as many elements as possible. This is the maximum coverage problem, which is NP-complete, but there are standard techniques that can be used to get decent-quality solutions (there is an approximation algorithm using a greedy algorithm, and a formulation as ILP).

---
Tags: algorithms
---


# Question
Title: Iterate over each cell of a grid through whose interior a given line segment passes
Let $a,b\>0$ and suppose we have divided the domain $\Lambda:=\[0,a\]\times\[0,b\]$ into a grid of width $n\_x$ and height $h\_y$.

We enumerate the grid from bottom to top and left to right. Given $(x\_0,y\_0),(x,y)\in\Lambda$, I want to iterate over each grid cell through whose interior the line segment connecting $(x\_0,y\_0)$ and $(x,y)$ passes.

Suppose we number the first cell by $(0, 0)$ and the last cell by $(n\_x-1,n\_y-1)$. How can we find an efficient algorithm, which iterates over the desired cells?

# Answer
Use a line drawing algorithm, such as Bresenham's.
> 1 votes

---
Tags: computational-geometry, graphics
---


# Question
Title: Given a function and its complexity, what is the complexity of its circuit?
For example, given an element-wise function $f$, with input $x\in\\{0,1\\}^{p\times n}$, the complexity $T(f(x))=O(n)$, and that all numbers are represented using $p$ binary digits. Suppose that we also know the complexity of each individual operations inside $f$. For example, multiplication takes $O(m^{1.585})$ using Karatsuba algorithm, here $m$ is the number of digits of the product. Similarly, suppose that we know all the complexity of arithmetic operations like addition, subtraction, division, square root etc. In addition, suppose that we also know the complexity of all the basic boolean cells, e.g. Full Adder, Subtractor, Multiplier etc.

What is the complexity, in terms of number of boolean gates, of its equivalent boolean circuit? Can we derive a formula containing $n,p,m$?

---

If so, what is the complexity of a boolean circuits of a Cholesky decomposition, with input $X\in\\{0,1\\}^{p\times n\times n}$?

# Answer
> 2 votes
If you can compute a function on $N$-bit inputs in time $T(N)$ with code that doesn't use random-access memory (only straight-line code; no arrays or pointers or memory), then there exists a combinational circuit with $O(T(N) \cdot (\log N)^2)$ gates that computes the function. That's because each basic operation you can do in code -- add, multiply, compare, etc. -- can be done in $O((\log N)^2)$ gates.

If you can compute the function on $N$-bit inputs in time $T(N)$ with code, and the code does use random-access memory, there exists a sequential circuit with $O(T(N) \cdot (\log N)^2)$ gates that computes the function in $O(T(N) \log N)$ time steps. Or, you can do it with a combinational circuit with $O(T(N)^2 \cdot (\log N)^3)$ gates -- though this might not be tight.

Technical details:

* I am making some assumptions about the model of computation for the code -- e.g., a RAM machine, where each cell is $O(\log N)$ bits wide.
* The exponent 2 can be reduced to the exponent for multiplication (though this might not be very useful in practice).
* It may be helpful to note that any algorithm that runs in time $T(N)$ can be converted to an algorithm that runs in time $O(T(N) \log N)$ *and* that uses only $O(T(N) \cdot \log N)$ cells of memory, by using a balanced binary tree data structure to build a sparse array that is used to simulate its memory.

# Answer
> 3 votes
There is no mapping from algorithmic complexity to circuit size. A counterexample: consider the language of strings of all ones, $1^n$, for only those $n$ such that the $n$-th Turing Machine rejects the string $1^n$ within $2^{2^n}$ time. Then this function requires $\Omega\left(2^{2^n}\right)$ time to compute on any machine, but the circuit for it only has size $O(n)$, because you can "hard-wire" the answer into the circuit, which then only checks that all the inputs are $1$.

D.W. provides a construction from an algorithm to a circuit. However, note that this gives only an upper bound, which is not necessarily tight. In particular, no function requires circuits of size larger than $O\left(\frac{2^n}{n}\right)$, because that is the size of a circuit which simply enumerates that function's truth table for inputs of size $n$.

Consequently, if an algorithm takes $O(2^{2^n})$ time, then you can use D.W.'s construction for a circuit of size $O(2^{2^n}\log(n)^2)$, but it is immediate that this bound is not tight; there is also a circuit of size $O(\frac{2^n}{n})$, and there may be a much smaller circuit for it, as in the example above. What we really want to know when we ask *what is the size of this function's circuit* is a lower bound: a minimum size for any circuit.

Circuit size lower bounds is a particularly enigmatic part of computational complexity about which very little is known. For example, we do not know whether or not SAT can be solved with $O(n)$-size circuits, and we have not ruled out that each problem in NEXP can be solved with polynomial-size circuits.

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


# Question
Title: Given a Turing machine , How to construct a efficient boolean circuit?
The proof of $P\subseteq P\_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page no -105 ).

The idea is that you can compute configuration $c\_i$ from configuration $c\_{i−1}$ by examining the content of 3 adjacent cells (i.e. by constant size circuit).

**First Case** : Let us consider that snapshot is the configuration of Turing machine i.e. requires $O(T(n))$ size.

Number of variables $x\_{i,j}$, where $i$ represents a row in table and $j$ represent the colum( cook -levin reduction proof) are $T(n) \times T(n)$ many. Now when we combine the constant size circuits of all variables then size of the resultant circuit is going to be $T(n) \times T(n)$ **,which is polynomial but my goal was to design a circuit of size $O(T(n))$.**

**Second case** : Let us consider that snapshot is machine's state and symbols read by all heads. let us consider they are $z\_1,z\_2 \cdots z\_{T(n)}$ and size of each $z\_i$ is constant string. To compute a snapshot $z\_{i+1}$for this computation I need $z\_i$, all old head positions and current head symbol .This all are constant size string, so I need only constant size circuit to encode the computation (current head position only depends upon the three symbol in the table in cook - levin theorem, or In other words, it is a map say $M$: $\tau^3 \mapsto \tau$, $\tau$ is a tape alphabet. So the total size of the circuit is $O(T(n))$

**Question** : To design a boolean circuit of size $O(T(n))$ for Turing machine $M$ with running time $T(n)$?

# Answer
I'm not sure whether this can be done. However, using oblivious Turing machines, we can get a circuit of size $O(T(n)\log T(n))$. According to the proof sketch of Theorem 6.7 in the draft of Arora–Barak, given a Turing machine running in time $T(n)$ we can construct a Turing machine running in time $O(T(n)\log T(n))$ in which the head movements only depend on $n$. Such a Turing machine is known as an oblivious Turing machine. This means that you only need to update one specific cell per time step, and the result is a circuit of size $O(T(n)\log T(n))$ (details left to you).
> 1 votes

---
Tags: complexity-theory, turing-machines, circuits
---


# Question
Title: Showing that Bayes classifier is optimal
Consider domain $X$, label set $ Y=\\{0,1\\}$ and the zero-one loss.

Given any probability distribution D over $ X\times \\{0,1\\} $, we've defined the Bayes classifier $ f\_D $ to be-

$$ f\_{D}(x)= \begin{cases} 1 & \text{if }\mathbb{P}\[y=1|x\]\geq\tfrac{1}{2}\\ 0 & \text{otherwise.} \end{cases} $$

I wish to prove that, for any classifer $ g\colon X\rightarrow\\{0,1\\}$, $ L\_D(f\_D)\leq L\_D(g)$, which means that $ f\_D$ is optimal.

$L\_D(h) $ is defined to be the "true error" of the classifier $h$. That is, $L\_D(h)=D\\{(x,y)\mid h(x)\not = y\\}$.

I'm having some hard time proving this given the definitions above, and some hints/intuition will be appreciated.

# Answer
The true error of a classifier $h$ is $$ \begin{align\*} L\_D(h) &= \sideset{\mathbb{E}}{}{}\_{x,y \sim D} \Pr\[h(x) \neq y\] \\ &= \sideset{\mathbb{E}}{}{}\_{x,y \sim D} \begin{cases} \Pr\[y \neq 0|x\] & \text{if } h(x) = 0, \\ \Pr\[y \neq 1|x\] & \text{if } h(x) = 1. \end{cases} \end{align\*} $$ (All probabilities are with respect to $D$.)

The optimal classifier is thus the one that minimizes the loss function $$ \phi(x) = \begin{cases} \Pr\[y \neq 0|x\] & \text{if } h(x) = 0, \\ \Pr\[y \neq 1|x\] & \text{if } h(x) = 1 \end{cases} $$ for *all* $x$. We can rewrite the loss function as $$ \phi(x) = \begin{cases} \Pr\[y = 1|x\] & \text{if } h(x) = 0, \\ 1-\Pr\[y = 1|x\] & \text{if } h(x) = 1 \end{cases} $$ So if $\Pr\[y=1|x\] \< 1-\Pr\[y=1|x\]$ we should choose $h(x) = 0$, and if $\Pr\[y=1|x\] \> 1-\Pr\[y=1|x\]$ we should choose $h(x) = 1$; if $\Pr\[y=1|x\] = 1-\Pr\[y=1|x\]$ then the choice doesn't matter.

Finally, $\Pr\[y=1|x\] \< 1-\Pr\[y=1|x\]$ is the same as $\Pr\[y=1|x\] \< 1/2$, and this explains the formula for $f\_D(x)$.
> 11 votes

---
Tags: machine-learning, classification, statistics
---


# Question
Title: Projecting points on a Pareto-front onto a (hyper)plane?
I'm trying to implement the Biased Crowding Distance in NSGA-II as described in the paper Integrating User Preferences into Evolutionary Multi-Objective Optimization by Branke and Deb.

Basically, from what I understand, given a set of points on a Pareto-front, we need to project the points onto a hyperplane with a direction vector $\eta$. Doing this will give the new crowding distance $d'$ based on the locations of the individualson the hyperplane with direction $\eta$.

To illustrate, see the figure below.

My question is simple: how do we obtain the hyperplane given a user-specified direction vector $\nu$? Is it simply by getting the perpendicular of the direction vector?

And a follow up question would be: how would I project the points onto the hyperplane? If $p$ is the point and $v$ is the vector representing the hyperplane, is it correct that the new location of $p$, call it $p'$ is $\frac{v.x(p.x) + v.y(p.y)}{||v||^2} (v.x, v.y)$ based on this?

Thanks and any information would be very helpful.

# Answer
I'm not sure if this should be considered a computer science question or not, it seems more an algebra question than anything else.

A vector is a direction vector of a hyperplane if it is parallel to that hyperplane (source).

For any vector $\vec{v} = (v\_1, . . . , v\_n)^T$ you can find a plane parallel to it by taking the dot product of $v$ and your variable vector $\vec{x} = (x\_1, . . . , x\_n)^T$ and setting the result equal to some constant $c$.

Consider $\eta$ as described in the paper, then the hyperplane he is referring to will be $$\eta\_1 f\_1 + . . . + \eta\_n f\_n = c $$ for a constant $c$. Because you are only interested in the distance between the points after projection, and not the location of the projected points, you can select $c = 0$, as shifting around the hyperplane won't affect the distances between the projected points.

Since the origin is contained in this hyperplane, the hyperplane is a subspace, call it $H$. We can then represent each $p\_i$ as a vector $\vec{p\_i}$ and project the vector onto the subspace.

To project a vector onto $H$ we need to find a basis for $H$. This can be done by making $n - 1$ similar vectors to $\eta$, where the difference is a single value is set to $0$ (distinct from previous selections). E.g., the plane $3x\_1 + 4x\_2 + 5x\_3 = 0$ has a basis of $$\Bigg\\{\begin{bmatrix}3 \\ 4 \\ 0\end{bmatrix}, \begin{bmatrix}3 \\ 0 \\ 5\end{bmatrix}\Bigg\\},\Bigg\\{\begin{bmatrix}3 \\ 4 \\ 0\end{bmatrix}, \begin{bmatrix}0 \\ 4 \\ 5\end{bmatrix}\Bigg\\}, \text{ or } \Bigg\\{\begin{bmatrix}0 \\ 4 \\ 5\end{bmatrix}, \begin{bmatrix}3 \\ 0 \\ 5\end{bmatrix}\Bigg\\}$$

Once you have a basis of $H$ you can use this guide guide to perform the projection. Note, since you have to do this multiple times, coming up with $Q$ as described in the guide and saving it will allow you to perform the process on many points.
> 1 votes

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


# Question
Title: Casting to boolean in integer linear programming
I have variables $x \in \\{0,1,\dots,5\\}$ and $y \in \\{0,1\\}$, where

$$y = \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$

My problem is to maximize $y$. How can I use linear constraints for this?

I tried certain cases like Cast to boolean, for integer linear programming but that won't work if the problem is to maximize $y$.

# Answer
> 3 votes
Add the following two constraints: $$ y \leq 5-x \\ y \geq 1-x/5 $$ If $x = 5$, then these constraints state that $y \leq 0$ and $y \geq 0$, hence $y = 0$. If $x \leq 4$, then $5-x \geq 1$, and so the first constraint doesn't impose any constraint on $y$. On the other hand, $1-x/5 \> 0$, forcing $y = 1$; and this assignment satisfies the constraint since $x \geq 0$ implies $1-x/5 \leq 1$.

# Answer
> 0 votes
Let $f : \\{0,1,\dots,5\\} \to \\{0,1\\}$ be defined by

$$f (x) := \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$

Let $ y = f (x)$. We would like to *maximize* $y$. Note that the preimage of $1$ is

$$f^{-1} (1) = \\{0,1,2,3,4\\}$$

Wherever $y$ appears, just make $y = 1$ and then append the constraints $0 \leq x$ and $x \leq 4$, where $x \in \mathbb N$. Instead of an *optimization* problem, we have a *decision* problem that can be solved via integer programming, e.g.,

$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & \color{grey}{\text{(linear constraints on } x \text{)}}\\ & 0 \leq x \leq 4\\ & x \in \mathbb N\end{array}$$

---
Tags: linear-programming, integer-programming
---


# Question
Title: Finding all possible simple directed graphics given a set of nodes
Is it possible to find all simple directed graphs given a set of nodes? I was thinking of just finding all permutations of an adjacency list of lists. For example, given nodes A, B I can have the adjacency lists:

```
A | \
B | \

A | B
B | \

A | \
B | A

A | B
B | A

```

The constraints are: no self loops, simple graph, directed edges

I can probably code up the way I described above, but I wanted to make sure doing this wasn't hitting some sort of fundamental boundary of graph theory or cs.

I was also thinking about using an adjacency matrix where I can store the matrix in row-major or column-major order in a uni-dimensional array of 0s and 1s - permute the uni-dimensional array (which has to be possible) and rebuild the NxM matrix to represent the graph that way.

Apologies that this is more of a discussion than a question, but any advice would be much appreciated!

# Answer
Any of those will work, as long as you view the graphs $A\to B$ and $B\to A$ as different graphs. If you view them as being the same graph, then things are much more complex as you have to either do isomorphism testing or somehow enumerate in a way that doesn't produce isomorphic graphs more than once.

The fundamental barrier is that, in an $n$-vertex digraph has $n(n-1)$ possible edges, each of which may be present or not, so there are $2^{n(n-1)}$ possible digraphs on $n$ vertices. Your program must output all of these which is going to be infeasible for all but small graphs.
> 2 votes

# Answer
Enumerate all possible adjacency matrices. A matrix is a possible adjacency matrix for a directed graph if it is a $n\times n$ matrix with 0 or 1 in every entry, except that the diagonal has to be all zeros. It is easy to enumerate them, because this is equivalent to enumerating all bit-strings of length $n(n-1)$.

Consequently, there are $2^{n(n-1)}$ directed graphs. Thus unless $n$ is very small, the number of such graphs is enormous -- too many to enumerate all of them.
> 3 votes

---
Tags: graphs
---


title: Knapsack and set cover-like problem

text:
# Question
Title: Knapsack and set cover-like problem
Given $n$ sets $r\_1, r\_2, \cdots, r\_n$ and a number $\delta$ where $0 \le \delta \le 1$. Let $T=\cup\_{i=1}^{n}r\_i=\\{t\_1,t\_2,\cdots,t\_m\\}$. Each $t$ has a value $v(t)$, which is given to us. The task is to find a subset $S$ of $T$ that minimize the total value $\sum\_{t\in S}v(t)$ while guaranteeing $\sum\_{i=1}^{n}\frac{|r\_i \cap S|}{|r\_i|}\>\delta n$.

Is this problem NP-complete? If so, which problem should I reduce from?

I've tried reduce it from the knapsack problem. One of the steps is not in P time and the attempt failed.

# Answer
Your problem is an instance of the following problem:

VECTOR-MINIMIZATION:
*Input:* vectors $v,w \in \mathbb{R}^m$, a threshold $\gamma \in \mathbb{R}$
*Goal:* minimize $v \cdot x$, subject to $w \cdot x \ge \gamma$ and $x \in \\{0,1\\}^m$

In your problem, $v=(v(t\_1),\dots,v(t\_m))$ and $w=(w\_1,\dots,w\_m)$ where $w\_i = \sum\_{t\_i \in r\_j} 1/|r\_j|$, where the sum is over all $j$ such that the set $r\_j$ contains the element $t\_i$.

So, your problem is an instance of VECTOR-MINIMIZATION. In turn, VECTOR-MINIMIZATION is basically an instance of the knapsack problem (it is at least as hard as knapsack, and thus NP-hard).

That raises the question, is your problem any easier than the general VECTOR-MINIMIZATION problem (or knapsack)? In your problem, each $w\_i$ has a special form: it is a sum of a polynomial number of reciprocals of polynomial-size integers. I don't *think* there's any way to use the special structure of the $w\_i$'s (and there are exponentially many possible values for the $w\_i$'s), so I think your problem is NP-hard, but I don't have a proof at the moment.

That said, you can still use the standard algorithms for knapsack-like problems: e.g., integer linear programming (ILP).
> 1 votes

# Answer
Try reducing from Clique. The $r\_i$ are the vertex pairs in each edge (so $n$ will be the number of edges and $|r\_i|=2$ for each $1 \le i \le n$). Set $v\_i=1$ for each $i$, and set $\delta = \frac{k(k-1)}{4n}-\epsilon$, where $k$ is the threshold parameter for the Clique problem instance and $\epsilon$ is some tiny positive amount to make the $\> \delta n$ condition like $\ge \delta n$. (If this produces $\delta \> 1$, then add dummy vertices with huge costs and edges between them.) This way we are trying to find the *fewest* vertices such that we get at least $\frac{k(k-1)}{2}$ edges, i.e., a $k$-clique.
> -1 votes

---
Tags: np-complete, proof-techniques, knapsack-problems
---


# Question
Title: Solving Hidoku problem using reduction to Hamilton path
It seems like people have discussed this reduction here:

Is Hidoku NP complete?

But it looks like the solution that was given only tells you if the Hidoku problem has a solution or not (if an hamilton path/cycle exists), what about extracting the solution itself from this reduction?

Can someone see how it is possible?

Best regards, Tal

# Answer
For any **NP**-complete problem where the question is, "Can you complete this partial solution?" you can extract a solution from the decision problem just by filling in components of the solution one at a time and asking if there's still a solution.

Is there a solution with $1$ in the top-left corner? No. With $2$ in the top-left? No. With $3$? Yes. OK, let's fix the top-left to be $3$: we know this can be extended to a solution. Is there a solution with $3$ in the top-left corner and $1$ in the square next to it? And so on. (In fact, you can be a bit more efficient by using the fact that two of the neighbours of the square labeled $i$ must be $i-1$ and $i+1$.)

This is a specific case of the concept of "self-reducibility": a problem is self-reducible if you can find the answer given an oracle for smaller instances of the decision problem. (In the case of Hidoku, the instances the oracle is called on are smaller in the sense that they have fewer blank squares.) Some other examples of self-reducible problems are:

* SAT. Suppose you want to know whether a formula in variables $X\_1, \dots, X\_n$ is satisfiable. If it's satisfiable, then either there's a satisfying assignment with $X\_n=t$, or there's one with $X\_n=f$, or both. So replace $X\_n$ with $t$ and ask if the resulting formula in $n-1$ variables is satisfiable. If so, recurse; if not, set $X\_n=f$ and recurse.
* $3$-colourability. Suppose you want to know whether a graph $G$ is $3$-colourable. If it is $3$-colourable and it has more than three vertices, then two of the vertices must receive the same colour. So, pick two non-adjacent vertices $x$ and $y$ and merge them (delete $y$ and make every vertex that was adjacent to it be adjacent to $x$). If the resulting graph is $3$-colourable, then $G$ has a $3$-colouring in which $x$ and $y$ have the same colour, so recurse. If they don't, then any $3$-colouring must assign different colours to $x$ and $y$, so we can add an edge between them and try a different pair of non-adjacent vertices.

If this process ever gives a graph that contains a $4$-clique –which we can test in polynomial time – then $G$ is not $3$-colourable. Otherwise, we eventually reduce the graph down to a $3$-clique, which is $3$-colourable. We can recover the $3$-colouring by tracking which vertices got merged into the different vertices of the $3$-clique.
* Independent set. Suppose we wish to know if a graph $G$ has an independent set of size at least $k$. Pick a vertex $v$ and ask if $G-v$ contains a $k$-independent set. If so, $G$ has a $k$-independent set that doesn't include $v$, so recurse on $G-v$ to find out what it does contain. Otherwise, any $k$-independent set must contain $v$, so it can't contain any of $v$'s neighbours. So ask if $G-v-\Gamma(v)$ contains a $(k-1)$-independent set. If it does, recurse. If it doesn't, $G$ has no $k$-independent set.
> 2 votes

---
Tags: reductions, np, hamiltonian-path
---


# Question
Title: Help in understanding calculation of hash collision from a document
UPDATE

In an earlier question of mine asked here : https://math.stackexchange.com/questions/2206095/beginner-level-understanding-concept-on-how-to-derive-probability-of-hash-collis , I got the answer that the number of keys falling into a given bucket. In lay man's term, if I imagine a key to be an image as the data item and its hash as a binary string. The conversion of the image to its binary representation is done via a hash function. I denote 2 images by the variables $x \neq y$ for which I have two binary arrays represting their hash codes as a L-bit string ($L = 20$)

$b\_x = \[0,1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0\]$ $b\_y = \[1,1,0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0\]$

It is known that the the probability that two binary strings are of equal is $Pr(b\_x = b\_y) = \frac{1}{2^L}$. In the language of hashing this means that the probability that the hash code will collide is $\frac{1}{2^L}$. For $K$ ($K$ is the number of images or data items or keys) values to be equal, the expression becomes ${\frac{1}{2^L} }^K$

I want to know and understand if in Locality Sensitive Hashing we use this expression of probability or not. In the documents https://www.cs.utah.edu/~jeffp/teaching/cs5955/L6-LSH.pdf On page 3 it is explained that the probability of all hashes colliding is

P(all hashes are same) = $s^r$ where $s$ is a similarity measure obtained using a suitable distance metric and the other expressions. I cannot understand why these calculations do not use ${\frac{1}{2^L} }^K$ anywhere. Maybe they do, I am not sure.

Please correct me whereever I am wrong. Thank you.

# Answer
A hash collision among $K$ values is any two values among those $K$ being equal. The probability of that occurring is the combinatorical expression in the link, from which they estimate the probability (well).

The expression is $\left(1/2^l\right)^{K-1}$ for the probability that all of those values would be equal.
> 1 votes

---
Tags: probability-theory, hash-tables, hashing
---


# Question
Title: Strict-Binary Tree - Same Post-order & Pre-order sequences?
I'm going through some past exam papers for my course and I'm having trouble completing this one question.

It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order and post-order traversal sequence".

Is this actually possible? Wouldn't I need to visit the root node before anything else for both sequences, that isn't possible with post-order traversal in a strict binary tree right? Unless the tree consisted of a single node?

I assume I'm missing something obvious. Post-order = LRN, Pre-order = NLR.

# Answer
It is possible only If all nodes have same value.
> -1 votes

---
Tags: graphs, trees, binary-trees, graph-traversal
---


# Question
Title: What is the knowledge required to understand the formal definition of a Turing Machine?
As a computer science student I consider is essential to completely understand how a Turing machine is defined.

What **mathematical knowledge** is required in order to understand the **formal definition of a Turing Machine**, as explained in this Wikipedia link.

# Answer
All you need is some basic discrete mathematics.

The states, tape alphabet and states are **finite sets**; the blank symbol, starting state, accepting state and rejecting state are **elements** of one of those sets.

The transition function is a **function on finite sets**, defined using a **Cartesian product** of finite sets.

The tape is a **sequence** of elements of one of the sets.
> 1 votes

# Answer
All you need is some basic discrete mathematics.

The states, tape alphabet and states are **finite enumeration types**; the blank symbol, starting state, accepting state are **elements** of those types.

The transition function is a **function between finite types**, defined using a **product type** of finite types

The tape is a **stream type** of elements of one of the types.
> -1 votes

---
Tags: turing-machines
---


# Question
Title: Problems while trying to prove that $(r|s)^* = (r^*.s^*)^*$
I came across the following equality of regular expressions $$(r|s)^\* = (r^\*.s^\*)^\*\\,,$$ where $r$ and $s$ are two regular expressions and $.$ denotes concatenation, but I don't know how could I prove it.

**My try:**

I call $L(r)$ the language defined by the regular expression $r$. And I want to use the fact that two regular expressions $r$ and $s$ are equal iff $L(r) = L(s)$.

The LHS can be writen as follows: $$ L((r|s)^{\*}) = \bigcup\_{i=0}^{+\infty} L(r|s)^{i} = \bigcup\_{i=0}^{+\infty} (L(r)^{i} \cup L(s)^{i})\\,. $$

The RHS can be writen as follows: $$ L((r^{\*}.s^{\*})^{\*}) = \bigcup\_{i=0}^{+\infty} L((r^{\*}.s^{\*}))^{i}\\,.$$

But I got stuck at this point and I don't know how to proceed.

# Answer
In one direction, $$ L((r^\*s^\*)^\*) \subseteq L(((r|s)^\*(r|s)^\*)^\*) = L(((r|s)^\*)^\*) = L((r|s)^\*). $$ In the other direction, $L(r) \subseteq L(r^\*s^\*)$ and $L(s) \subseteq L(r^\*s^\*)$ imply that $L(r|s) \subseteq L(r^\*s^\*)$, and so $$ L((r|s)^\*) \subseteq L((r^\*s^\*)^\*). $$
> 6 votes

# Answer
Your mistake is in the step $$ L(r|s)^i = L(r)^i \cup L(s)^i. $$ Consider for example $r=a$ and $s=b$. Then $L(r|s)^i$ consists of all words (over $\\{a,b\\}$) of length $i$, whereas the righthand side is $\\{a^i,b^i\\}$.
> 3 votes

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


title: Counter Mode Encryption Vulnerabilities

text:
# Question
Title: Counter Mode Encryption Vulnerabilities
Hi All,
I am solving a question about counter mode encryption in symmetric crypto. I am new to the topic and don't really understand the matter, could you help me a little how to solve the following task?

*The formula for counter mode encryption is
Ci = Pi ⊕ E (IV + i, K).
Suppose we instead use the formula
Ci = Pi ⊕ E (K, IV + i).
Is this secure? If not, what's the possible attack?
*

# Answer
> 1 votes
If you know one block of plaintext (which in many situations is a reasonable assumption), you can break the second cryptosystem but not the first one (assuming your cipher is secure!). I'll let you figure out how.

You can extend this attack to the case in which one block of plaintext has small entropy, which is an even more realistic assumption.

---
Tags: cryptography
---


title: Sampling among constrained partitions

text:
# Question
Title: Sampling among constrained partitions
I'm working on a clustering problem and want to sample partitions (possible clustering solutions) among a set of constrained ones.

Here is the problem: I have a set of objects $O=\\{o\_1,\ldots,o\_n\\}$ and would like to sample among reflexive, symmetric and transitive relations $R \in O \times O$ such that samples satisfy a set of must-link/cannot-link constraints. More specifically, I do have for some pairs $o\_i,o\_j$ either that $(o\_i,o\_j) \in R$ or $(o\_i,o\_j) \not\in R$. Alternatively, I could see it as the problem of sampling graphs that are disjoint cliques with pre-specified arcs or absences or arcs.

Reject sampling is likely to not work in practice, as the number of rejection would quickly be prohibitive as n and the set of constraints get high enough (something we can expect).

Do any of you know if this problem has been treated, or any easy way to solve it? Uniformity within the set of samples is desirable, but not absolutely necessary.

Thanks.

# Answer
A reflexive, symmetric and transitive relation $R$ on $O$ is the same as a partition of $O$. If $(o\_i,o\_j) \in R$ then $o\_i,o\_j$ are in the same partition, and so can be merged. If $(o\_i,o\_j) \notin R$ then $o\_i,o\_j$ are not allowed to be in the same partition. After merging, we reach the following problem:

> Given a graph, partition the set of vertices so that each partition is an independent set.

Equivalently (up to a permutation of colors):

> Given a graph, find a proper coloring.

Intuitively, it seems that a random partition will have many parts, so you can try to generate a random sample in the following way. Greedily sample a "small" independent set whose size you choose in advance as a Poisson random variable with constant expectation, remove it from the graph, and repeat. Of course, this won't be a uniform sample. You can gather statistics in some small cases to see what is a good choice of parameters in this procedure, and whether the results are good enough for your purposes.
> 2 votes

---
Tags: sampling, partitions
---


title: Is the word problem of CFLs in NC?

text:
# Question
Title: Is the word problem of CFLs in NC?
Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string.

Lets say I have a PRAM and I want it to decide in $\log^k n$ time and $n^c$ space complexity whether $w$ is in $L(G)$ ($c$ and $k$ are both constants) – that is, the complexity stays within Nick's class.

Is there such an algorithm? If so what would be an idea?

# Answer
> 1 votes
It has been shown that CFL ⊆ NC² ⊆ NC \[1\] -- so yes, there is such an algorithm. I'm afraid the proof in that paper does not give you a PRAM algorithm, though.

---

1. On uniform circuit complexity by W. Ruzzo (1981)

# Answer
> 3 votes
The problem is not in NC unless P=NC. Jones and Laaser showed in "Complete Problems for Deterministic Polynomial Time" that the problem (therein called CFMEMBER) is P-complete. Interestingly, Ullman and Van Gelder showed in "Parallel Complexity of of logical query programs" that the same problem where the input CFG has no epsilon productions is in NC (Corollary 7.2).

---
Tags: algorithms, context-free, formal-grammars, parallel-computing, parsers
---


# Question
Title: How to reduce this regular expression into DFA
$(a(aa|b)^\*ab|b)((ba|a)(aa|b)^\*ab|bb)^\*((ba|a)(aa|b)^\*)^\*|a(aa|b)^\*$

I know long algorithmic procedures but since regex is large I tried a lot by substituting common patterns for some regex definition but didn't seem to help.

What can be done so that this regex can be converted to DFA easily.

# Answer
> What can be done so that this regex can be converted to DFA easily?

Algorithmic methods are doomed, if you insist on a DFA. Your regular expression contains about sixty characters. Roughly speaking, any procedure for converting to an automaton is going to produce at least one state per character of the regular expression. That means you're going to end up with an automaton with at least sixty states, and it's probably going to be nondeterministic. Determinizing that naïvely is going to give you $2^{\>60}$ states, which isn't quite as many as the number of atoms in the earth, but it's still an unmanageably huge number.

Do you really need a DFA? If, for example, you're trying to write a program that will accept strings that match this regular expression, it's straightforward to check if an NFA accepts a particular string: just scan along the string keeping track of the set of states the automaton could be in after each successive character. For a fixed automaton, this can be done in linear time.

If you do need a DFA, you're going to have to figure out what the regular expression does. Break it into chunks. $(a(aa|b)^∗ab|b)$ matches $b$, along with all strings that have an even number of $a$s, begin with $a$ and end $ab$. It's not too difficult to see that this language is matched by the following automaton (I've omitted a trap state that's reached if any character is read from state $q\_3$):

If you stare at that for a moment, you'll realise that states $q\_0$ and $q\_2$ are the same (both say "if $a$, go to $q\_1$; else, go to $q\_3$") so we can reduce the automaton to the following.
You could also use algorithmic state-minimization techniques to avoid having to notice things like this.

You can probably produce similar automata for the various "top-level" chunks of the regular expression, and chain them together to get a DFA for the whole thing.
> 1 votes

# Answer
Thinking outside the box: You can use implementations of an algorithm to convert this RegEx to a DFA easily. Looking for *regular expression to DFA online* in your favorite search engine will lead you pages that allow you to convert the expression within the page. This is very easy and will give you results within a minute.
> -1 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Most probable value of randomized procedure output
Let $n, m \in \mathbb{N}^{+}$. Let $\mathsf{rand}$ be a procedure which returns some random $x \in \\{0, 1, \ldots, m - 1\\}$ with a flat probability distribution. I have the following procedure:

```
W := an array of length m full of 0s
for i in 0, 1, ..., n - 1; do
    (x, y) := (rand(), rand())
    W[y] := max(W[x], W[y]) + 1
x := 0
for i in 0, 1, ..., m - 1; do
    if W[i] > x; do
         x := W[i]
return x

```

My question is: what is the most-probable value of $x$? I'm not even sure where to *begin* with the analysis here, due to the probabilities involved.

# Answer
The question sounds a bit difficult. I was able to calculate the *expectation* of $x$ when $m = 2$. The most probable value of $x$ should be very close to its expectation. Perhaps this will give you some ideas.

The idea is to construct an infinite Markov chain whose states are $|W\[0\]-W\[1\]|$, and whose transitions are labeled by whether $\max(W(0),W(1))$ increases or not. Here are the transitions (explained below):

1. At state 0, we transition to state 1 w.p. 1, increasing the maximum.
2. At state $n \> 0$, we transition to state $n-1$ w.p. 1/4; to state $n+1$ w.p. 1/2, increasing the maximum; and to state 1 w.p. 1/4, increasing the maximum.

The first case is trivial. For the second case, consider the array $a+n,a$. There are four options, each occurring w.p. 1/4:

* When $x=y=0$, the new array is $a+n+1,a$ (the maximum increases).
* When $x=y=1$, the new array is $a+n,a+1$ (the maximum doesn't increase).
* When $x=0,y=1$, the new array is $a+n,a+n+1$ (the maximum increases).
* When $x=1,y=0$, the new array is $a+n+1,a$ (the maximum increases).

The next step is to calculate the stationary probability (it is easy to check that the chain is ergodic). Denoting it by $p\_n$, we have

* $p\_0 = \frac{p\_1}{4}$.
* $p\_1 = p\_0 + \frac{p\_1 + \cdots}{4} + \frac{p\_2}{4} = p\_0 + \frac{1-p\_0}{4} + \frac{p\_2}{4}$.
* $p\_n = \frac{p\_{n-1}}{2} + \frac{p\_{n+1}}{4}$ for $n \geq 2$.

The sequence $p\_1,p\_2,\ldots$ satisfies the recurrence $$ p\_n = 4p\_{n-1} - 2p\_{n-2}. $$ The roots of $x^2 - 4x + 2$ are $2 \pm \sqrt{2}$, and since the series $\sum\_{n \geq 1} p\_n$ converges, we must have $p\_n = C (2-\sqrt{2})^n$. In particular, $p\_2 = (2-\sqrt{2})p\_1$. Substituting this in the formulas for $p\_0,p\_1$, we can calculate $$ p\_0 = \frac{4\sqrt{2}-5}{7}, \qquad p\_1 = \frac{16\sqrt{2}-20}{7}. $$ Notice now that when at state $n\>0$, the maximum increases with probability 3/4, and when at state 0, it always increases. Hence the probability that it increases at the stationarity is $$ \frac{3}{4} + \frac{p\_0}{4} = \frac{4+\sqrt{2}}{7}. $$ Denoting by $X\_n$ the expected value of $x$ when $m=2$ and $n$ is given, we deduce that $$ \lim\_{n\to\infty} \frac{\mathbb{E}\[X\_n\]}{n} = \frac{4+\sqrt{2}}{7} \approx 0.773459. $$ This is corroborated by experiment. When $n=1000$, the empirical average of $10^6$ trials is $0.773733$ (the expected error is of order $10^{-3}$).

The expected gap between $\max(W)$ and $\min(W)$ is $$ \sum\_{n=1}^\infty np\_n = p\_1 \sum\_{n=1}^\infty n(2-\sqrt{2})^{n-1} = \frac{p\_1}{(\sqrt{2}-1)^2} = \frac{4+8\sqrt{2}}{7} \approx 2.18767. $$ In particular, the limits of $\mathbb{E}\[\max(W)\]/n$ and $\mathbb{E}\[\min(W)\]/n$ (after $n$ steps) are the same.

In a similar way, it should be possible to compute $\lim\_{n\to\infty} \mathbb{E}\[\max(W)\]/n$ for any fixed $m$, though I don't know if there is a nice formula for this limit in general.

Other limits could also be interesting. For example, one could ask what happens if $n$ is fixed and $m\to\infty$ (this should be easy to answer), or when $n=m \to \infty$ (seems more difficult).

Calculating the exact expectation for given $n,m$ is possible using the same ideas, but there isn't probably any nice formula.
> 3 votes

---
Tags: probability-theory, randomized-algorithms
---


title: How is implication same as entailment

text:
# Question
Title: How is implication same as entailment
In propositional logic (Artificial intelligence to be specific) $\alpha$ entails $\beta$ iff $\alpha\Rightarrow\beta$ is a statement. However if I write the truth table for implies ($\Rightarrow$) if $\alpha$ is false implies that $\beta$ is a true sentence as shown in the table below in the fourth row.

\begin{array}{cc|c} \alpha & \beta & \alpha\Rightarrow \beta\\ \hline T & T & T\\ T & F & F\\ F & T & T\\ F & F & T \end{array}

Now this should be false according to the model checking approach, since there could be models in which $\alpha$ is false but $\beta$ is true given that $\alpha$ entails $\beta$. This is further supported by the book on artificial intelligence by Peter Norvig that states that $\alpha\vDash\beta$ iff M$(\alpha)\subseteq M(\beta)$, where $M(\alpha)$ is the set of all models where $\alpha$ is true.

# Answer
> 12 votes
Let $\varphi$ and $\psi$ be formulas of propositional logic. We write, as Norvig says, $\varphi\vDash \psi$ iff $M(\varphi)\subseteq M(\psi)$: that is, iff every truth assignment that makes $\varphi$ true also make $\psi$ true. This is the case iff $\vDash \varphi\Rightarrow\psi$, i.e., if the formula $\varphi\Rightarrow\psi$ is true in all truth assignments (is a tautology).

Entailment and implication operate at different levels. An implication is something that may be true or false, depending on which truth assignment you're considering at the moment, whereas an entailment is a statement about all truth assignments. In particular, the truth of the entailment $\varphi\vDash\psi$ depends only on truth assignments that make $\varphi$ true. If a particular truth assigment makes $\varphi$ false, then it cannot make the entailment false. Similarly, if an assignment makes $\varphi$ false, it cannot make the implication $\varphi\Rightarrow\psi$ false.

# Answer
> 3 votes
Very briefly, implication and entailment are not the same because they operate at different levels of logic. Implication applies to certain truth assignments. Entailment considers all possible truth assignments for some statement(s).

There is a helpful explanation of this on Philosophy Stack Exchange if you want to go more in-depth.

---
Tags: propositional-logic
---


# Question
Title: Tree structure that is like a quadtree/octree but splits a different number of times in each dimension?
I'm looking for a data structure that is like a quadtree where each level is a subdivision of the previous. However, unlike a quadtree I need the subdivision to occur a different number of times in the horizontal direction to the vertical direction. In a quadtree the space is subdivided once in each dimension (resulting in four children per node). In the tree I'm looking for the space may be divided a given number of times in one dimension and a different number of times in the other. Say for example, twice in the X and once in the Y (resulting in six children per node). Has such a space partitioning tree been given a name? Can anyone point me to an existing data structure that fulfills this requirement? Thanks!

# Answer
> 2 votes
You could use a k-d tree. A k-d tree normally alternates between partitioning horizontally and partitioning vertically, but you could certainly modify it to change that pattern (e.g., partition horizontally twice in a row; or equivalently, partition horizontally into three or four regions rather than just into two regions).

Not everything has a "name". There are many more possible algorithms and data structures than there are "names". So don't take it as some kind of negative if you can't find a "name" for it. "Modified quadtree" or "modified k-d tree" will do fine, if you need a way to refer to it.

# Answer
> 0 votes
Have you looked at STR-tree (sort-tile-recursive loaded R-Trees)? See examples here and here. The basis is an R-tree. The STR-algorithm load it in a way that resembles a grid. For example in 2D space, when you specify a node size of 25, it will try to divide the space into a recursive tree of 5x5 nodes. That means each node will contain a 5x5 grid of subnode, except for the leaf nodes, which will contain 25 data points/rectangles. Note that the splitting is usually not a regular grid of squares (covering the same amount of space), instead it creates rectangulars such they each cover the same amount of data points. I'm sure this loading algorithm could be modified to form other types of grids, such as 3x8, if you wish.

This algorithm is meant for initial bulk-loading of data. Once the loading is done, additional insertions (or removals) may destroy the grid-like pattern.

---
Tags: data-structures, search-trees, space-partitioning
---


# Question
Title: special case of best first search algorithms
I read somewhere that DFS is a special case of Best first search algorithm if f(n)=-depth(n). please justify this i am not getting it.:/

# Answer
Consider a node $u$ such that $depth(u)=l$.

In Best first Search when you evaluate $u$ with the evaluation function you defined, you have $f(u)=−l$.

```
queue

╔═══╤═══╤═════╤═══╗
║ r │ a │ ... │ u ║
╚═══╧═══╧═════╧═══╝

```

When you expand $u$ and you evaluate the first child of $u$ (suppose it is Node $v$) you have $f(v)=−(l+1)\<−l=f(u)$ so now you expand $v$ (that means that you put $v$ in the front of the queue) and you continue.

```
queue

╔═══╤═══╤═════╤═══╤═══╗
║ r │ a │ ... │ u │ v ║
╚═══╧═══╧═════╧═══╧═══╝

```

This corresponds to what you do when you use Depth First Search.
> 1 votes

---
Tags: search-algorithms, search
---


# Question
Title: Building a context-free grammar for this language
I have a hard time creating a context-free grammar for the language

$$L=\\{(a^n)^\*(b^m)^\*y\mid y\in\\{a,b\\}^\*,\ |y|=n+m \\}\\,.$$

Any help breaking down the problem is appreciated, since I'm getting nowhere with this one...

# Answer
I'm not sure to have fully understood your notation.

As production rules you could consider:

$S \rightarrow aSa \ |aSb \ | S\_1 | \epsilon$

$S\_1 \rightarrow bS\_1a | \ bS\_1b \ | \ \epsilon$

In $S$ for each $a$ you add an $a$ or a $b$ or you can go to $S\_1$ and then never come back to $S$ again.

In $S\_1$ for each $b$ you add an $a$ or a $b$.
> 1 votes

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


# Question
Title: Floyd–Warshall algorithm ,Behavior with negative cycles
I am sorry my English is not very good. my problem might look simple for everyone here. I have read about Floyd–Warshall algorithm in wikipedia,every thing was good but when I start reading "Behavior with negative cycles" I face problem in understanding this sentence: "There is no shortest path between any pair of vertices i, j which form part of a negative cycle, because path-lengths from i to j can be arbitrarily small (negative)" I don't understand what it exactly mean. can anyone help me please. Behavior with negative cycles

# Answer
Given a graph, suppose to have a cycle given by Nodes $i \ $,$\ j$,$\ k$ of negative cost.

Example:

* $w(i,j)=2,\ w(j,k)=4,\ w(k,i)-7$

```
+---+    +2      +---+
| i |+---------->| j |
+-+-+            +-+-+
  ^                |
  | -7             |+4
  |     +---+      |
  +----+| k |<-----+
        +---+

```

Suppose you want to find the shortest path between $i$ and $j$.

You have

$P=\\{(i,j)\\}$ with $cost(P)=2$

but you can loop through the negative cycle and have:

$P'=\\{(i,j),(j,k),(k,i),(i,j)\\}$ with $cost(P')=1$ $P''=\\{(i,j),(j,k),(k,i),(i,j),(j,k),(k,i),(i,j)\\}$ with $cost(P'')=0$ and so on.

You could loop forever through the negative cycle and decrease the cost of the path.

Same if you consider an undirected graph with an edge that has negative weight.
> 3 votes

---
Tags: algorithms, graphs, dynamic-programming
---


# Question
Title: How to reduce UNSAT problems so that less than $7/8+\epsilon$ of clauses are unsatisfied?
In this question I ask about what use is a solver that can find an assignment that satisfies, say, 90% of the clauses of a known satisfiable 3SAT problem in polynomial time. The answer seems to be: given a problem ϕ that may or may not be satisfiable, you perform a reduction on an input formula ϕ to another formula ϕ′ such that ϕ′ is 90% satisfied iff ϕ is SAT and run my hypothetical algorithm on ϕ′, which will tell you if ϕ is SAT or not.

My question is a follow-up: what is the reduction from ϕ to ϕ'?

# Answer
> 1 votes
The reference is Håstad's classic paper, Some optimal inapproximability results. It relies on the PCP theorem and on Raz's parallel repetition theorem. The proof is not particularly easy, and even the reduction itself is not so simple to state (if you take into account the PCP component).

---
Tags: satisfiability
---


# Question
Title: Proof that $A^* - \{x\} = A^+$ such that $A=\{a,b\}$ and $x \in \{a,b\}^*$
Exercise 1.1 (2) from Problem Solving in Automata, Languages, and Complexity by Du and Ko. P.7. the question is as following:

> Let A be a langauge over {a,b} and $x \in {a,b}^\*$. Find necessary and sufficient conditions in terms of x and A for the equation: $$A^\* - \\{x\\} = A^+$$

thus, by substation: $$\\{a,b\\}^\* - \\{\\{a,b\\}^\*\\} = \\{a,b\\}^+$$

Now this the LHS should equal to $\\{a,b\\}^\*$ because if we have two sets A and B, then $A \cap B = \phi$, then $A-B=A$. Now where is wrong?!!

I'm also trying to prove from RHS since this is equality to proof should be from both direction.

# Answer
> 2 votes
Consider the regular expression $(a+b)^\*$ as an example.

$(a+b)^+=(a+b)\cdot(a+b)^\*$

In $(a+b)^+$,with respect to $(a+b)^\*$, you are forbidding the generation of the empty string, that is you are removing $\epsilon$.

This could be generalized to every language $A$, either in the case of $A$ empty.

In fact if $A=\emptyset$:

* $ A^\*=\emptyset^\*=\\{\epsilon\\}$
* $A^+ =\emptyset \cdot \emptyset^\*=\emptyset$

and $A^\* \setminus \epsilon = A^+$

# Answer
> 2 votes
Your problem is that in going from $A^\*-\\{x\\}$ to $\\{a,b\\}^\*-\\{\\{a, b\\}^\*\\}$ you went a step too far. In the first expression, $x$ is a *single* string over the alphabet. Replacing that with the general expression $\\{\\{a,b\\}^\*\\}$ is incorrect, if for no other reason that $\\{\\{a,b\\}^\*\\}$ is a set consisting of a set of words and not a single word.

To complete this answer, see newbie's comment on your original post.

---
Tags: formal-languages
---


# Question
Title: Functorial type constructors in System F
I have come across the claim that all basic data types in System F, such as Bool, Nat, and List(U), can be expressed in the form $\forall \alpha (((T\alpha \rightarrow \alpha) \rightarrow \alpha)$, where $T(\alpha)$ is a definable functorial type constructor.

Can someone explain why this is true or refer me to a proof? Because I have not found a proof for this claim yet.

# Answer
The usual (categorical) characterization of inductive data types is as initial $F$-algebras for a functor $F$. An **$F$-algebra** is a pair of a type, $A$, and a function $a : FA \to A$. A **homomorphism** of $F$-algebras, $\varphi : (A,a) \to (B,b)$ is a function $\varphi : A \to B$ which satisfies $\varphi\circ a = b\circ F\varphi$. An $F$-algebra, $(\mu F,\mathsf{in}\_F)$, is **initial** if there exists a unique homomorphism from it to *any* other $F$-algebra. This means we have a function which takes an $F$-algebra $(A,a)$ and produces a function $\mathsf{fold}\_A(a):\mu F\to A$ which satisfies $$\mathsf{fold}\_A(a)\circ\mathsf{in}\_F=a\circ F(\mathsf{fold}\_A(a))$$ The type of $\mathsf{fold}$ in System F would be $\forall \alpha.(F\alpha\to\alpha)\to\mu F\to\alpha$. The free theorem for this (as calculated by this) specializes to $$\forall \alpha,\beta. \forall \varphi : \alpha\to \beta. \forall a : F \alpha \to \alpha. \forall b : F \beta \to \beta.\\ \varphi \circ a = b \circ F \varphi \implies \varphi \circ \mathsf{fold}\_{\alpha}(a) = \mathsf{fold}\_\beta(b)$$ which further specializes to $$\forall \beta. \forall b : F \beta \to \beta. b\circ \mathsf{fold}\_{F\beta}(Fb) = \mathsf{fold}\_\beta(b)$$ and $$\forall \beta. \forall \varphi : \mu F\to \beta. \forall b : F \beta \to \beta.\\ \varphi \circ \mathsf{in}\_F = b \circ F \varphi \implies \varphi \circ \mathsf{fold}\_{\mu F}(\mathsf{in}\_F) = \mathsf{fold}\_\beta(b)$$ If we can prove $\mathsf{fold}\_{\mu F}(\mathsf{in}\_F) = id\_{\mu F}$, then this would mean that $(\mu F,\mathsf{in}\_F)$ was an initial $F$-algebra as the above equation says: "any $F$-algebra homomorphism $\varphi : (\mu F, \mathsf{in}\_F)\to(B,\beta)$ is $\mathsf{fold}\_\beta(b)$ and thus exists and is unique". Of course to do this we need to actually give a definition of $\mu F$, $\mathsf{fold}$, and $\mathsf{in}\_F$.

By noting that $\forall \alpha.(F\alpha\to\alpha)\to\mu F\to\alpha$ is isomorphic to $\mu F \to \forall \alpha.(F\alpha\to\alpha)\to\alpha$, there's an obvious choice for both $\mathsf{fold}$ and $\mu F$: simply set $\mu F = \forall \alpha.(F\alpha\to\alpha)\to\alpha$ and $\mathsf{fold}$ to be the inverse image of $id$ with respect to that isomorphism. Explicitly, $$\mathsf{fold} = \Lambda\alpha.\lambda a\\!:\\!F\alpha\to\alpha.\lambda g\\!:\\!\mu F.g\[\alpha\]a$$ All that remains is to define $\mathsf{in}\_F$ and show that $\mathsf{fold}\_{\mu F}(\mathsf{in}\_F) = id\_{\mu F}$. The easiest way to define $\mathsf{in}\_F$ is to just follow the types: $\mathsf{in}\_F : F\mu F \to \forall \alpha.(F\alpha\to\alpha) \to \alpha$ so $$\mathsf{in}\_F = \lambda x\\!:\\!F\mu F.\Lambda\alpha.\lambda a\\!:\\!F\alpha\to\alpha.a(F(\mathsf{fold}\_{\alpha}(a))x)$$ This definition is particularly convenient as you may have noticed that while I've shown that *if* there's a homomorphism $\varphi : (\mu F,\mathsf{in}\_F)\to(A,a)$ then it is $\mathsf{fold}\_A(a)$, and I've shown that there is a *function* $\mathsf{fold}\_A(a):\mu F\to A$, I haven't shown that $\mathsf{fold}\_A(a)$ is a *homomorphism*. That is, I haven't shown $\mathsf{fold}\_A(a)\circ\mathsf{in}\_F = a\circ F(\mathsf{fold}\_A(a))$, but with the above definitions of $\mathsf{fold}$ and $\mathsf{in}\_F$ this is easily shown by normalizing. To finish, $$\begin{align} \mathsf{fold}\_{\mu F}(\mathsf{in}\_F) & = \mathsf{in}\_F\circ\mathsf{fold}\_{F\mu F}(F(\mathsf{in}\_F)) \\ & = \lambda g\\!:\\!\mu F.\Lambda\alpha.\lambda a\\!:\\!F\alpha\to\alpha.(a\circ F(\mathsf{fold}\_{\alpha}(a)) \circ \mathsf{fold}\_{F\mu F}(F(\mathsf{in}\_F)))g \\ & = \lambda g\\!:\\!\mu F.\Lambda\alpha.\lambda a\\!:\\!F\alpha\to\alpha.(\mathsf{fold}\_\alpha(a)\circ \mathsf{in}\_F \circ \mathsf{fold}\_{F\mu F}(F(\mathsf{in}\_F)))g \\ & = \lambda g\\!:\\!\mu F.\Lambda\alpha.\lambda a\\!:\\!F\alpha\to\alpha.(\mathsf{fold}\_\alpha(a)\circ \mathsf{fold}\_{\mu F}(\mathsf{in}\_F))g \\ & = \lambda g\\!:\\!\mu F.\Lambda\alpha.\lambda a\\!:\\!F\alpha\to\alpha.\mathsf{fold}\_\alpha(a)g \\ & = \lambda g\\!:\\!\mu F.\Lambda\alpha.\lambda a\\!:\\!F\alpha\to\alpha.g\[\alpha\]a \\ & = \lambda g\\!:\\!\mu F.g \end{align}$$
> 7 votes

---
Tags: lambda-calculus, type-theory
---


# Question
Title: How many integers can you represent with 6 bits?
I might be wrong but I think it must be 2^6 = 64 integers?

# Answer
Of course, it is 64 integers. If you are representing only positive integers then you can represent 0 to 63. If you are representing negative numbers also, then you must use 2's complement representation because it is the best and it is the standard format used in computers. Two's complement covers from -32 to +31, which is also 64 integers. If you use some other representation for signed numbers, like 1's complement & signed magnitude representation, then you will lose one integer because zero has two representations in these (ie., one for +0 & the other is -0). Because other schemes waste one integer place, only 2's complement representation is used for signed numbers.
> 0 votes

# Answer
Let's treat this as a combinatorics problem, so you can see how you get $2^6$:

* Each bit has 2 possible values, 0 or 1
* There are 6 bits that we can choose a value for
* The choice of value for each of these is independent, so we can find the total number of choices by multiplying the number choices for each bit together.

So, there are $2\times2\times2\times2\times2\times2 = 2^6 $ possible values. How you map these values onto integers is up to you.
> 0 votes

---
Tags: combinatorics, numeral-representations
---


# Question
Title: Complexity of solving multiple problems of the same complexity?
If I am given two languages $A$ and $B$ which are in NP, then we know that there exists a NDTM that can decide $A$ in polynomial time, and there exists another NDTM that can decide $B$ in polynomial time. Can I decide $A$ and $B$ in polynomial time using a NDTM by simply using a NDTM to check for belonging in $A$ then use another NDTM to check for belonging in $B$ and if both accept then it belongs to both $A$ and $B$?

# Answer
Yes, you can test whether $A \cap B$ is in $\textsf{NP}$ by testing $A$ and $B$ separately. Actually, you have proven that the class $\textsf{NP}$ is closed under intersection. See this lecture note (Exercise 1) for details and other cases.
> 3 votes

---
Tags: complexity-theory
---


title: How to tell if a Heuristic is monotonic

text:
# Question
Title: How to tell if a Heuristic is monotonic
I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,\*,W,W,W), where * represents a blank space. A piece can move into a blank space and can jump over one or two other pieces into a blank space. I've attached a picture of the graph.

This Heuristic is Admissible because the distance to the goal is ALWAYS more than the distance from the B's to the rightmost W.

The thing I'm not sure of is if this Heuristic is monotonic. My understanding of Monotonic is that the cost of going to an adjacent node plus the estimate of the new node have to be less than the total distance to the goal. How would I determine if this Heuristic is monotonic?

# Answer
If your heuristic is essentially the original problem, but with some constraints removed, it is monotonic. Otherwise, you must prove that there is no transition which does not uphold the formula in Caesar's answer.
> -2 votes

---
Tags: artificial-intelligence, correctness-proof, heuristics, searching
---


# Question
Title: In a flow network, is it possible to restrict the flow going into a node?
For example, if a node has 2 edges going into it and two edges coming out of it all with capacity 1, is there a way to make it so that only 1 unit of flow can go through this node (without just deleting edges)?

# Answer
> 8 votes
I believe you can represent node N as two nodes, A and B. Node A has all of the inbound flow edges of N, and Node B has all of the outbound flow edges of N. Nodes A and B are connected by a single edge which you can use to throttle the flow. The edge from A to B is the only edge out of A and the only edge into B.

# Answer
> 3 votes
If you have represented this as a MIP you can restrict the flow to be on only one arc. Are you currently representing this as a linear program?

You can introduce a binary variable for each arc, $X\_{i,j}$, and for each location $j$ you can introduce the constraint $$\sum\_i X\_{i,j} \leq 1 $$ where nodes i lead to node j. A similar constraint is required for the flow out of each node.

If you wish to solve as a linear program, you cannot restrict the flow to be on only one arc (though your objective function may achieve this) but you may restrict the total flow through a node by introducing a flow variable $F\_{i,j}$ and restricting the sum over arcs that lead to node $j$: $$\sum\_i F\_{i,j} \leq 1 $$ where nodes i lead to node j.

---
Tags: algorithms, network-flow
---