If a Triple Graph Grammar rule counts as a Mathematical Proof I am intrigued by Triple Graph Grammars (TGG) as a potential for formal mathematical proof.

  Triple Graph Grammars (TGGs) are a technique for defining the
  correspondence between two different types of models in a declarative
  way.

In some systems, proofs are simply trees of rules being applied to transform one syntax tree of terms into another. I don't really have a firm grasp of what that actually means in practice, but I think I understand the gist of it. As such, a proof is a transformation of a into b, so a correspondence between two different models. Some sort of isomorphism.

The diagrams below show (roughly) that there are links between source and target objects, defining how to transform them (bijection). I'm wondering if a TGG rule has enough information in it to allow it to be considered a valid proof of a transformation of isomorphism. That is, and I don't fully understand how to apply TGGs, you define a TGG between two forms of an object (or more generally, between two objects), and that definition is equivalent to a formal proof of the isomorphism between the two objects. Wondering if this is true or if it is close to true. If close / along the lines of the right direction, wondering what it would require to make it into a valid proof.

To summarize, the questions are:

If a TGG counts as a valid proof of transformation (maybe of isomorphism) from $A \to B$.
If a TGG counts as a valid proof of transformation from $B \to A$.
If not, what would be required to make it into a valid proof.

Some more notes are:

  A triple graph $G =(G_S \overset{s_G}{\longleftarrow} G_C \overset{t_G}{\longrightarrow} G_T)$ consists of three graphs $G_S$, $G_C$, and $G_T$, called source, correspondence, and target graphs, together with two graph morphisms $s_G : G_C \to G_S$ and $t_G : G_C \to G_T$. A triple graph morphism $m = (m_S, m_C , m_T) : G \to H$ consists of three graph morphisms $m_S : G_S \to H_S$, $m_C : G_C \to H_C$ and $m_T : G_T \to H_T$ such that $m_S \circ s_G = s_H \circ m_C$ and
  $m_T \circ t_G = t_H \circ m_C$. A typed triple graph $G$ is typed over a triple graph $T_G$ by a triple graph morphism $type_G : G \to T_G$. [source]

A function transforming A into B doesn't keep track of the actual individual steps between transformation, so the information is lost. But the TGG does. The only way to "prove" that A can be transformed to B with a function is to actually apply the function and compare the outputs. But with a mapping defined in a TGG, the "proof" would be the mapping itself, so you don't have to actually perform the transformation (or it seems). So given A and B and R (rule) in TGG context, R is the proof, we don't have to try converting A $\to$ B.

An example of this would be the transform between a parse tree and an abstract syntax tree. The parse tree let's say is the actual individual tokens organized into a tree of symbols and words, where every object in the tree is the same type of object (let's say a "parse node" object). The AST though is a tree of custom objects like "function node" and "variable node". So you convert the parse tree to the AST. How to prove that AST came from the parse tree. A function requires recomputing the output, maybe a TGG rule means it's automatically proven as a "derivation" of the parse tree.

Given I have parse tree A and AST B in memory, I would like to be able to say "A becomes B" without having to recompute it. I would like to say "B came from A" as well, which seems possible because of the bidirectional mapping of TGGs.

A TGG defines (generates) a language of triples of graphs.
This can be used for many things, including establishing a notion of correctness for forward and backward transformations.  So if you have some transformation A -> B, you can check if it is correct by checking if there exists some A <-C->B that can be generated by the TGG.

Correct forward and backward transformations do not have to be bijections, although this could be enforced by analysing the TGG appropriately.

As a proof, one could use a TGG to generate proofs of consistency.  So given some A and B, I can prove that A and B are consistent (and whatever produced B from A or A from B correct), by determining a rule application sequence that takes you from some start triple graph to some A<-C->B.

So for your concrete syntax tree and AST you could check for consistency without recomputing the trees.  In practice, however, such a consistency checker can actually be slower than a recomputation (but is sometimes still better, e.g., if the computation was non-deterministic or required some form of decision making).


Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance I have a set of thousands~millions of points on a sphere's surface, each with latitude, longitude.
I want to quickly get all points within a distance d of a particular sphere point latC, lonC.

The points are mostly concentrated at places where humans go often.
Some points have the exact same latitude and longitude.
d is orders of magnitude smaller than the Earth's radius r, so using arc instead of distance is totally OK
Getting a few extra points is OK (even a rectangle area instead of a circle area is better than nothing). Missing points is not OK
No persistence needed.

What data structure would give these points quickly consistently, even if the set is large?

What I tried:

Simple list: Checking all points is too slow.
Quadtree on latitude, longitude: Does not find points around the poles.

Geographic information systems use spherical triangular quadtrees to solve this problem. They are analogous to a quadtree, but defined over a sphere using triangular patches.

There are different variants with different bells and whistles, but you can refer to Quaternary Triangular Meshes (Dutton. "Encoding and Handling Geospatial Data with Hierarchical Triangular Meshes"), Sphere Quadtrees (Fekete. "Rendering and managing spherical data with sphere quadtree") and HTMs (Kunszt. "The Hierarchical Triangular Mesh") as approaches you can extrapolate from.

The basic idea is that you partition the sphere into coarse triangular patches, then subdivide those patches into smaller triangular patches recursively as needed. You can then perform basic queries like you would on a quadtree.

See Chen. "An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM" for a survey of different techniques, and related problems.


Is Binary search tree in 1D? This post says

  Binary Space Partitioning Trees are a
  generalization to dimensions > 1 of binary search trees

which indicates the binary search trees lives in 1d space.

Is my understanding right?

This just means that the elements stored in a binary search tree are one dimensional. Or more generally that they can be ordered in some meaningful way. You can think of this ordering as putting all the elements on a line, from "smallest" to "biggest" (for an appropriate notion of small and big depending on the particular case). And partitioning then always happens by cutting this line at some point. Hence the "1-dimensionality" of the binary search trees.

But in 2D space-partitioning for example, your data lives in a 2D space and you can not simply order them from "smallest" to "biggest". You need more freedom in the way you cut your space in half.

The trees themselves are just binary trees in both cases, the "dimension" comes from what the nodes represent and how the trees are used.


What is the origin of using Q to denote a set of states in an automaton? When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc.

Is there a particular reason why the letter $Q$ was chosen? As in, is $Q$ the first letter of a word historically related to automata? Or was it chosen totally arbitrarily?

The symbol $q$ to denote the state of a finite automaton appears (for the first time??) in Moore's 1956 paper Gedanken-Experiments on Sequential Machines and since the paper became very popular, I suppose that Moore's notation has been adopted since then. Apparently, Moore didn't use any special notation for the set of states, but it you adopt $q$ for a state, $Q$ seems to be an obvious choice for the set of states.

I don't think there is any special meaning for the letter $q$ (or $Q$).

[1] E.F. Moore, Gedanken experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, 129–156. Princeton University Press, 1956.


How many possible prime implicants are there in total for a 4-variable Karnough-map? The answer for this question is 81. But I count figure out why. Can someone explain to me how does this work. Thank you.

Hint: $81 = 3^4$. So each variable can appear in a prime implicant in three different forms. Can you figure out which?


Complexity of shortest paths if paths have to use edges from different partitions We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully partitions $E$.

For any two vertices in $V$, I need to find the shortest path between them.
The additional caveat is that no two edges which belong to the same partition may be in the path.

This has totally thwarted any polynomial algorithm I can think of. It confounds algorithms like Djikstra, because at any step during the process, it may be best to forgo the best available edge in favor of having a better choice still open in the future.

I've tried reducing it to the traveling salesman problem, and several others, but I can't quite get there. Proof-writing is not really my strongest suit. Any point towards proving this would be much appreciated.

EDIT: Yes, $S$ is a partitioning of $E$. This does seem to be perfectly analogous to rainbow graphs. Is it known that finding rainbow paths on an unweighted graph is NP-Hard?

If it helps, the problem you are trying to solve is looking for a "rainbow path" between the two vertices.  It's a relatively new area of research, and there's now a book:

Rainbow Connections of Graphs
X. Li and Y. Sun
http://www.springer.com/la/book/9781461431183

Or here's an earlier paper:
G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang. Rainbow connection
in graphs. Mathematica Bohemica, 133(1):85–98, 2008.

The result you're looking for is likely in one of those places, something they cite, or something that cites them.


Preprocess data such that locations within a rectangle drawn on a map can be found in less than O(n) time I came across this problem online and found no solutions or insight. The problem is stated as:

  Given a map as a square, and a set of locations on the map, users are able to select a rectangle on the map and all of the locations on the map are returned
  How would you preprocess the map data so that the find operation for the locations in the inner rectangle can be done in less than O(n) time?

I'm really stumped on this as the only thing I could think of is to create a hashmap that contains every single possible rectangle within the map with values that are lists of locations within said rectangle. However, it would not be practically feasible to store that much data.

Any help would be appreciated!

You should look into R-Trees.

  R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

The parts that apply the most to your case are the ones described on the Search subsection. This operation on this kind of trees have a complexity of   O(logMn):

  In range searching, the input is a search rectangle (Query box). [...] the elements are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.

Good luck!


Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships? Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to \mathbb{Q}^{+}$ such that $\forall S, S' \subseteq Q, \forall s, s' \in S$:

$$
\sum_{s'' \in S'}{W(s, s'')} = \sum_{s'' \in S'}{W(s', s'')} \Leftrightarrow \sum_{s'' \in S'}{W'(s, s'')} = \sum_{s'' \in S'}{W'(s', s'')}
$$

?

I believe, at least for the finite case, this should be possible and I'm trying to prove this "constructively" by finding $W'$.

So let $\epsilon \in \mathbb{Q}^{+}$ be a rational such that $\forall s_0,s_1,s_2,s_3 \in Q, \epsilon < |W(s_0, s_1) - W(s_2, s_3)|$ whenever that difference isn't $0$.

Obviously if we just round every non-rational weight in a grid with spacing $\epsilon$ we will not preserve equalities and I believe it'll be quite difficult to restore the exact relations.

So my idea is to round one weight at a time, and then fix the equalities that get broken by modifying only non-rational weights and repeating the process until there are only rational weights.

So start by taking two subsets $S, S' \subseteq Q$ and take $s \in S$ and $s'' \in S'$ such that $W(s, s'') \notin \mathbb{Q}$.
Now we can round this number to the nearest rational of the form $k\cdot \epsilon$.

Let $e = W(s, s'') - W'(s, s'')$ is the error we introduced.
Now if there was an $s' \in S$ and an $s'''$ such that $W(s', s''') = W(s, s'')$ then we modify that weight in the same manner, and thus the iff condition still holds for $s$ and $s'$.

Otherwise for $s' \in S$ we must have that some (more than one) weight $W(s', s''') \notin \mathbb{Q}$ and we can subtract $e$ from it and preserve the condition for $s$ and $s'$ with respect to $S$ and $S'$.

However we have now changed some other weight, and thus while we may have preserved the equality between $S$ and $S'$, we may have broken it for other subsets. So we have to consider every subset that is either a subset or superset of $S$ and $S'$, verify if we have broken that iff condition, and if so we must find an other weight and change it, and repeat the process until it we find an equilibrium. But does this actually happen?

My question is:

Does there exist such $W'$ or am I trying to build a non-existent function?
If $W'$ exists, is the above approach feasible in some way, or should I completely change strategy in order to find $W'$? Do you know any particular trick that can help in devising $W'$?

Identify $W$ with the set of all weights. Let $B$ be a basis of $W$ over the rationals. That is, you can write every weight in $w$ as a linear combination of elements of $B$ with rational coefficients. You can identify the weights with vectors $\vec{w}$ of length $|B|$. Each linear dependency that you want to avoid can be thus encoded as an inequality
$$
\sum_i \alpha_i b_i \neq 0,
$$
where the coefficients $\alpha_i$ are not all zero. We can moreover assume that the $\alpha_i$ are integers (by taking a common denominator).

Let $M$ be an integer larger than all $|\alpha_i|$ appearing in an inequality you are interested in. If we replace $b_i$ with $M^i$ then all the requisite inequalities will be satisfied, while all equalities will also be preserved.


String of minimum length in $\{a, b\}^*$ not in a regular expression I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression.

a. $b^*(ab)^*a^*$

My answer: $aab$

b. $(a^* + b^*)(a^* + b^*)(a^* + b^*)$

My answer: $abab$

c. $a^*(baa^*)^*b^*$

My answer: $bba$

d. $b^*(a + ba)^*b^*$

My answer: $abba$

I came up with my answers by trial and error. I don't know for sure if these are the shortest possible strings. Is the best method trial and error, or would there be some better algorithmic way?

First, the string of minimum length might not be defined properly since it might not be unique.

Here is a way to find a string of minimum length:

Convert the regular expression to a nondeterministic finite automaton.
Convert the nondeterministic automaton into a deterministic one.
Use a breadth first search until you encounter the first nonfinal state (if there is one at all).


What is the recurrence form of Bubble-Sort I understand how bubble sort works and why it is O(n^2) conceptually but I would like to do a proof of this for a paper using the master theorem.

As an example: The recurrence form for merge sort is T(n) = 2T(n/2) + O(n) which, using the master theorem, gives us O(n log(n)).

I am unsure of how to do this process with Bubble sort. What equation allows us to see that it is O(n^2)?

Bubble sort uses the so-called "decrease-by-one" technique, a kind of divide-and-conquer.
Its recurrence can be written as

$$T(n) = T(n-1) + (n-1).$$


An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$ If $n<100$ then $O(n^2)$ is more efficient, but if $n\ge 100$ then $O(n\log n)$ is more efficient.

I am sure that this statement is valid, but I don't know how to prove it or justify it. Can someone please help me?

Your statement is meaningless, since $O(n^2)$ and $O(n\log n)$ are just upper bounds on the time complexity. If you know that $A \leq 100$ and $B \leq 10$, you have absolutely no idea which is larger, $A$ or $B$.
Let us correct your statement to

If $n<100$ then $\Theta(n^2)$ is more efficient, but if $n \geq 100$ then $\Theta(n\log n)$ is more efficient.

This statement still has no truth value, since we don't know which functions are represented by $\Theta(n^2)$ and by $\Theta(n\log n)$. What we do know is that for large enough $n$, the $\Theta(n\log n)$ algorithm would be more efficient.
Suppose you instantiate your statement with specific functions $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n\log n)$. There is no reason to expect that there is a single crossover point. For example, take the following functions:
$$
f(n) =
\begin{cases}
100 & \text{if } n < 20, \\
n^2 & \text{if } n \ge 20
\end{cases} \\
g(n) =
\begin{cases}
50 & \text{if } n < 10, \\
200 & \text{if } 10 \le n < 20, \\
10^{300} n\log n & \text{if } n \ge 20
\end{cases}
$$
As you can see, $g(n)$ is faster for $n < 10$, and then for (astronomically) large enough $n$.
While such definitions are artificial, in practice we could have (say) $f(n) = 3n^2 + n\log n + 9n + 17$ and $g(n) = 10n\log n + 4\sqrt{n} + 50$, which might have several crossover points (I haven't checked).
Finally, even if there is a single crossover point, there is no reason to expect it to be exactly $n = 100$. The exact crossover point(s) depend on the functions $f(n),g(n)$. The only way to determine it is by running the two algorithms and comparing the running times.


Floating point Euclidean norm optimization Past few days I've been struggling with floating point number exercises, trying to learn how they work and what are their limitations. The exercise I've encountered today is as follows:

  The Euclidean norm of an n-dimensional vector $x$ with components $x_{1}...x_{n}$ is defined by:
  $$||x||_{2}=\left(\sum_{i=1}^{n} x_{i}^{2}\right)^{1/2}$$ How would you avoid overflow and harmful underflow in this computation?

I've come up with this solution, but I'm not sure if it really makes sense:

  There are some problems with underflow and overflow that can occur when computing Euclidean norm.Firstly, the component $x_{i}$ of the vector can be in the machine range, however its square root might be not. It is possible, that the square of $x_{i}$ can be either too small (underflow - $x_{i}$ considered to be 0) or too large (overflow) or the sum of the squared components can be too large (overflow again).The solution could be implementing an algorithm, that firstly splits the components of the vector 'x' into 3 parts:

  small magnitude numbers, for which underflow might occur: $x_{i}<y$
  medium magnitude numbers, where $y\leq x_{i}<Y$
  large magnitude numbers, for which $x_{i}>Y$

  When $y$ and $Y$ are thresholds set by machine precision limits. Then, small magnitude numbers will be scaled by a scalar $S$ and then their sum of squares 'unscaled' by the same $S$. Similarly, large magnitude numbers will be scaled by an appropriate $s$, and then descaled again.

I've taken the algorithm from this book, but I'm not sure if I understand it correctly and if I explained the solution properly. It would be also helpful to reproduce this algorithm in R language, however, I don't understand the explanation to the point of replicating it.

Roughly right.

You can first calculate the sum of squares. If it overflows, then you find a large power of two M, divide all numbers by M, calculate the norm, and multiply by M. If overflow happens at $2^{1023}$, then you have numbers greater than $2^{500}$. Dividing by M=$2^{700}$ means you get neither overflow nor underflow.

You may have underflow in some of the squares. Check how much error an underflow can produce. Then you check how large a sum wouldn’t be influenced by these errors. If the sum of squares is larger than say $2^{-900}$ then there may be products with underflow but they don’t affect the sum. In that case you are fine.

Otherwise, multiply all numbers by M, calculate the norm, and divide by M.


Is there a computationally reasonable algorithm for generating a set of polygons from a set of 2d points? Is there a known/existing algorithm for taking a 2D canvas covered in  arbitrarily/randomly distributed points and dividing it entirely into a set of non-overlapping polygons? An example of the kind of result I'm looking for:

Yes, there are even algorithms which are able to satisfy additional constraints. It can occur as a subtask during mesh generation. The vanilla algorithm is the Delaunay triangulation, which is closely related to the Voronoi diagram (in case you wonder why D.W. thinks that the Voronoi diagram answers your question).


Finding the element that occurs the most in a very large file I've heard this interview question asked a lot and I was hoping to get some opinions on what good answers might be: You have a large file 10+ GB and you want to find out which element occurs the most, what is a good way to do this?

Iterating and keeping track in a map is probably not a good idea since you use a lot of memory, and keeping track as entries come in isn't the greatest option since when this question is posed the file usually already exists.

Other thoughts I had included splitting the file to be iterated through and processed by multiple threads and then have those results combined, but the memory issue for the maps is still there.

When you have a really large file and many elements in it, but the most common element is very common -- occurs $> 1/k$ fraction of the time -- you can find it in linear time with space $O(k)$ words ( the constant in the $O()$ notation is very small, basically 2 if you don't count the storage for auxiliary things like hashing). Moreover, this works great with external storage, as the file is processed in sequence one element at a time, and the algorithm never "looks back". One way to do this is via a classical algorithm by Misra and Gries, see these lecture notes. The problem is now known as the heavy hitters problem (the frequent elements being the heavy hitters).

The assumption that the most frequent element appears $> 1/k$ fraction of the time for $k$ a small number may seem strong but it is in a way necessary! I.e. if you will have sequential access to your file (and in case the file is huge random access will be too expensive), any algorithm which always finds the most frequent element in a constant number of passes will use space linear in the number of elements. So if you don't assume something about the input you cannot beat a hash table. The assumption that the most frequent element is very frequent is maybe the most natural way to get around the negative results.

Here is a sketch for $k = 2$, i.e. when there is a single element that occurs more than half the time. This special case is known as the majority vote algorithm and is due to Boyer and Moore. We will keep a single element and a single count. Initialize the count to 1 and store the first element of the file. Then process the file in sequence:

if the current element of the file is the same as the stored element, increase the count by one
if the current element of the file is different from the stored element, decrease the count by one
if the updated count is 0, "kick out" the stored element and store the current element of the file; increase the count to 1
proceed to the next element of the file

A little bit of thinking about this procedure will convince you that if there exists a "majority" element, i.e. one that occurs more than half the time, then that element will be the stored element after the whole file is processed.

For general $k$, you keep $k-1$ elements and $k-1$ counts, and you initialize the elements to the first $k$ distinct elements of the file and the counts to the number of times each of these elements appears before you see the $k$-th distinct element. Then you run essentially the same procedure: an element's count is increased each time it is encountered, all element counts are decreased if an element that is not stored is encountered, and when some count is zero, that element is kicked out in favor of the current element of the file. This is the Misra-Gries algorithm.

You can of course use a hash table to index the $k-1$ stored elements. At termination, this algorithm is guaranteed to return any element that occurs more than $1/k$ fraction of the time. This is essentially the best you can do with an algorithm that makes constant number of passes over the file and stores only $O(k)$ words.

One final thing: after you found $k$ candidate "heavy hitters" (i.e. frequent elements), you can make one more pass over the file to count the frequency of each element. This way you can rank the elements between each other and verify whether all of them occur more than $1/k$ fraction of the time (if there are less than $k-1$ such elements, some of the elements returned by the algorithm might be false positives).


Big-endian systems and the smallest memory address I read on en.Wikipedia that "Big-endian systems store the most significant byte of a word at the smallest memory address and the least significant byte at the largest. A little-endian system, in contrast, stores the least-significant byte at the smallest address."
But I don't know what is "the smallest memory address", and how does "Big-endianness is the dominant ordering in networking protocols, such as in the internet protocol suite, where it is referred to as network order, transmitting the most significant byte first", in those type of protocols, the first is accessed the smallest memory address and in little-endian system is accessed the memory address?

If the map of memory bytes were arranged from left to right in incremental address order, the smallest address is on the left.  The largest address is on the right.
Let's say you are storing the 32-bit value, 19088743, which is 0x01234567 in hex, at address 0x1000.  Hence, the 4-byte value will span over the 4 bytes at memory address 0x1000, 0x1001, 0x1002, and 0x1003
In big endian, the 01 is stored at 0x1000 (the smallest address) and the 67 is stored at 0x1003 (the largest address).  Exactly how you would think of it if you had never heard of little endian.
In little endian, the 01 is stored at 0x1003 (the largest address) and the 67 is stored at 0x01000 (the smallest address).
Big Endian and Network Byte Order generally mean the same thing.
Big Endian
|===================================|
| 0x1000 | 0x1001 | 0x1002 | 0x1003 |
|-----------------------------------|
|  0x01  |  0x23  |  0x45  |  0x67  |
|===================================|

Little Endian
|===================================|
| 0x1000 | 0x1001 | 0x1002 | 0x1003 |
|-----------------------------------|
|  0x67  |  0x45  |  0x23  |  0x01  |
|===================================|


Why page size = size of one cache way? Why is that the page size equals the size of one cache way?

My book states "A direct-mapped cache cannot be bigger than a page".

Assume you have different processes sharing memory. That means you can have different pointers pointing to the same physical memory. If you have two different pointers, pointing to the same physical memory, but pointing to different entries in the cache, then you will be in trouble.

In practice, memory mapping is done page by page. So both pointers will have the same offset into a page, but the page numbers can be different. One pointer can have an even page number, one an odd page number. If your cache is bigger than a page, for example two pages, then two pointers with an even and an odd page numbers would point to different cache entries, exactly what we want to avoid.

Of course an operating system could just not do any memory mapping that creates two pointers to the same memory location pointing an odd number of pages apart, and then the cache could be two pages in size.


Unique path sums in a DAG using vertex instrumentation I stumbled across this paper from Ball et al.
In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control flow graphs of programs), these values are summed up. Afterwards they are able to reconstruct the executed path from the sum of the values of the traversed edges.

For my research problem, I can not instrument edges, but vertices. To optimize vertex instrumentation I found a great paper from Knuth. However, I can not find a publication about determining vertex values that can be used in a manner as the edge values from the Ball paper.

Does anyone know about an algorithm to fulfill my task?

The paper of Ball can be found here: http://www.cs.ucr.edu/~gupta/teaching/260-08/Papers/pathprof.pdf

I think the solution is easy. In addition to the global variable r, we keep a global variable lastVertex. Before exiting a vertex v, we set lastVertex=v. Now, when entering a vertex, we know which vertex we came from and we only need to keep a map in each vertex from each possible previous vertex to the corresponding transformation of r. This is only slightly less efficient than with edges, as we need to do a lookup in a map in each vertex. For larger graphs, this may be memory intensive though.


Is rejecting in polynomial time required for language to be in P? Language $L$ is in $\mathrm{P}$ if and only if there exists some Turing Machine $M$ such that for every word in $L$, $M$ either accepts or rejects it in polynomial time. Right?

But what if all we know about our language is that there exists TM $M'$ such that for every word in $L$, $M$ accepts it in polynomial time, but for words not in $L$ it might not halt at all, for example? Is existence of $M'$ enough to say that $L$ is in $\mathrm{P}$, and why/why not?

Suppose you have a problem $A$, and a TM $M$ which accepts all the words $w \in A$ within a polynomial time bound $p(|w|)$, and diverge (or reject) otherwise.

Then, we can craft a new TM $N$, which on input $w$ performs the following:

simulate $M$ with input $w$ for $p(|w|)$ steps;
if $M$ accepts, we make $N$ accept as well
otherwise we make $N$ reject

It is immediate to see that $N$ runs in polynomial time: simulating a step of $M$ requires polynomial time on the $M$ configuration (whose size remains polynomial during the whole simulation), and we only need a polynomial number of steps.

Further, $N$ decides $A$ by construction.

TL;DR: if we know we can only accept a word within a time bound $t$, we can set an alarm on $t$. When the alarm rings, if we have not accepted before, we know it's a reject.

Conclusion: your alternative definition of $P$ is equivalent to the regular one. I would argue that it is harder to work with in proofs, though.


Why do P-class problems not require a witness like NP? If I am given a problem in P, to claim that I have solved it, I would need to give proof, right? For example, to show a number is not prime, if I use some deterministic algorithm, I can return the prime factors of that number.

I am finding it weird that P does not require a witness/certificate in the definition like NP.

If we look at decision problems, then a problem is in P if for "YES" instances "I think the answer is YES" is a witness that can be checked in polynomial time :-)


How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem? 3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring:

  Reduction from 3-Coloring instance: adding an extra vertex to the graph of 3-Coloring problem, and making it adjacent to all the original vertices.

Following the same reasoning, 5-Coloring, 6-Coloring, and even general $k$-Coloring problem can be proved NP-Complete easily. However, my problem comes out with the underlying mathematical induction:

  My Problem: What if the induction goes on to $n-1$-Coloring and $n$-Coloring problem, where $n$ is the number of vertices in the graph? I certainly know that $n$-Coloring problem can be solved trivially. So, is there something wrong with the reasoning? How to understand the reduction from 3-Coloring problem to the general $k$-Coloring one?

The $k$-coloring problem is usually defined only for constant $k$, so $n$-coloring doesn't make sense. For every constant $k \geq 3$, the reduction you mention works. By adding a superconstant number of vertices you can show, for example, that $(n/2+3)$-coloring is NP-complete.


What's the dual problem of stable matching? So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?

From http://kuznets.fas.harvard.edu/~aroth/papers/1993_MOR_StableMatchingsOptimal.pdf :

  Shapley and Shubik (1972) observed that [the dual] formulates the problem of finding payoff vectors in the core of the above assignment game.

The assignment game described is that two agents who choose to match get a total "value" equal to the edge weight between them, and they can split this value between them in some way; these are the "payoffs".

It might be nice for future readers if you put the LP and dual in your question....


Computing the partition function Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$?  What's known about the complexity class of this problem as a function of $n$?

Perhaps I'm missing something trivial here, but other than listing some recurrent definitions of this function and some of their asymptotics, I don't see this precise information (complexity class, and known algorithms with their runtime/space complexity) in either of these articles:

Partition (number theory)
Partition function (number theory)

Johansson gave a nearly linear time algorithm (in terms of the output size!) in his paper Efficient implementation of the Hardy-Ramanujan-Rademacher formula. This work is mentioned at the very end of the Wikipedia article on the partition function.


Reduction 3SAT and CLIQUE Hello everyone this is my first question ever and I apologize if I ask in the wrong manner causing this post to be either closed or deleted. I'm learning Reductions and my professor has asked us to write a paper on reductions (3SAT)

When doing the Reduction from the Clique Problem to 3SAT, I understand that we make clauses and every clause contains 3 literals (hence, 3SAT) but my problem comes when choosing what literals and why they choose them. How do I know which literals to choose? So I know that in every clause I'll have x1, x2 and x3, but how do I choose their assignment order? In one clause I have (x1 or x2 or x3) and in another I have (x1 or not x2 or not x3). How were these chosen?

Also, it seems they don't begin with a graph in mind already. What if I'm given a graph to begin with, how would I convert it into x1, x2, x3? If for clause I have 3 vertices, how would I assign them their respected boolean expression? Thank you very much

Here is one possible way to reduce Clique to SAT (you can then further reduce it to 3SAT). This type of reduction is often used in (propositional) proof complexity, an area of complexity theory.

Given a graph $G = (V,E)$ and a number $k$, we will have variables $x_{iv}$ for every $1 \leq i \leq k$ and every $v \in V$. You should think of $x_{iv}$ as stating that $v$ is the $i$th vertex in the clique. We want to encode the following constraints:

For each $i$, there is an $i$th vertex in the clique: $\bigvee_{v \in V} x_{iv}$.
For each $i,j$, the $i$th vertex is different from the $j$th vertex: for each $v \in V$, $\lnot x_{iv} \lor \lnot x_{jv}$.
For each non-edge $(u,v) \notin E$, $u,v$ cannot both belong to the clique: for each $i,j$, $\lnot x_{iu} \lor \lnot x_{jv}$.

You can think of the second constraint as a special case of the third one.

If we take all these clauses together, we get a CNF which states that "the $x_{iv}$ encode a $k$-clique in $G$". This CNF is satisfiable iff $G$ contains a $k$-clique.

If you want to get a 3CNF, all you need to do is to convert the constraints of the first kind into 3-clauses. There is a standard way to do this: if the vertices are $v_1,\ldots,v_n$, we replace $\bigvee_{v \in V} x_{iv}$ with
$$
x_{iv_1} \lor x_{iv_2} \lor y_{iv_2} \\
\lnot y_{iv_2} \lor x_{iv_3} \lor y_{iv_3} \\
\lnot y_{iv_3} \lor x_{iv_4} \lor y_{iv_4} \\
\ldots \\
\lnot y_{iv_{n-2}} \lor x_{iv_{n-1}} \lor x_{iv_n}
$$
Here the $y_{iv}$ are new variables. This set of clauses is equivalent to the original clause $x_{iv_1} \lor x_{iv_2} \lor \cdots \lor x_{iv_n}$.


Optimal coverage of a $D$-dimensional grid with small blocks I have a $D$-dimensional grid with the size $(N_1, \ldots, N_D)$, where $N_i$ are natural numbers, and a "flat block size" $M$, also a natural number. I want to find a decomposition $(m_1, \ldots, m_D)$ such that:

$\prod_{i=1}^D m_i = M$,
$R = \prod_{i=1}^D f(N_i, m_i) m_i - \prod_{i=1}^D N_i$ is as low as possible. Here $f(N,m)$ is the minimal number of blocks of length $m$ necessary to cover a 1D grid with size $N$ (or, formally, $f(N, m) = N / m$ if $N$ is a multiple of $m$, and $f(N,m) = N\,\mathrm{div}\,m + 1$ otherwise).
The number of $m_i$ equal to 1 is as high as possible (but this is low priority, the condition 2 is more important).

How should I approach this? Is there some standard algorithm this can be reduced to?

In my case $M$ is not very big (of the order of 1000). Also, an absolute minimum in all cases is not strictly required; if there is an approximate algorithm, it will do to.

(In case anyone is interested in the application, I want to use it to find work group dimensions for an OpenCL kernel with a known global size and total number of work items).

One unsophisticated approach is to factor $M$, then exhaustively explore all possible decompositions of $M$ into a product of $D$ integers, and see which is best according to your criteria.  I suspect this will prove to be an entirely reasonable solution for your example parameter ranges.

The number of possible decompositions is exponentially large, in general.
If $M=\prod_i p_i^{e_i}$, then there are $\prod_i {D+e_i-1 \choose e_i}$ possible decompositions, which (depending upon $M$) could be rather a lot.

However, for your particular parameter values, the number of possible decompositions will probably still be manageable, so the unsophisticated algorithm should work fine.  If $D=3$ and $M$ is 32 times a random number from 1 to 32, then the number of possible decompositions will range from a minimum of 21 possibilities (for $M=32\times 1$) to a maximum of 252 possibilities (for $M=32\times 30$).  That's small enough that you can easily enumerate all possibilities and see which is best.

If you increase $D$ to $D=7$, then the number of possible decompositions will vary from a minimum of 462 (for $M=32\times 1$) to a maximum of 45276 possibilties (for $M=32\times 30$).  That's still small enough that you can enumerate all possibilities and use the unsophisticated algorithm I mention above.

If you run into some other parameter choices where there are too many decompositions, a simple variant would be to randomly pick a bunch of different decompositions and see which of those is the best.  It's not the fanciest algorithm around, but it's a reasonable thing to try.

Anyway, this should solve your problem for the parameter sizes you mention.


How many bits for offset/frame/page I'm working on the following exercise and can't get the calculations right:

Assume an OS uses:

33 bits for physical address
34 bits for logical address
2KB frame size

Calculate:

How many bits are used for the offset
How many bits are used to identify a frame
How many bits are used to identify a page

And then:
Assuming the page tables include the valid and dirty(edit) bit, calculate the size (in bits) of a process' page table using all pages.

I have a hard time understanding this type of calculation and will greatly appreciate any help.

The frame size is 2KB. Assuming memory is byte-addressable, we need an offset into 2000 different bytes. 2000 is approximately (2^10)*2 = 2^11, so we need 11 bits for the frame offset.

Then, we can easily calculate that 33 - 11 = 22 bits are used to identify  a physical page (frame), and 34 - 11 = 23 bits are needed to identify a virtual page.


How to find the big O notation of $\log^b x$ How would you determine big O notation for $\log^b x$? I don't think you can simply say $O(\log^b x)$, can you?

If you can, then here is a better question: $x^3 + \log^b x$. How would you know if it's $O(x^3)$ or something else depending on the $b$ value?

How would you determine big o notation for this? I don't think you can simply do O(log(x)^b) can you?

$\mathcal O\left(\log^b x\right)$ or $\mathcal O\left(\left(\log x\right)^b\right)$ is correct.

  x^3 + log(x)^b

Assuming $b$ is a constant. You always take the fastest growing term in a polynomial. $T(x)=\mathcal O\left(\log^b x\right)$ is called polylogarithmic time. In this case, $\mathcal O\left(x^3\right)$ grows faster than $\mathcal O\left(\log^b x\right)$.

You can see a list of different complexities (sorted from lowest to highest) here.


Uses of the type Unit The Unit type is a singleton type containing the constant unit. In functional languages with side effects, unit is used in functions that perform side effects. For example print is a function from string to Unit.

Unit also corresponds to truth. If you view the type of the expression as a proposition and the program as a proof, Unit corresponds to truth since you can always prove Unit by using the constant unit.

My question is aside from these two uses, is there any other uses of Unit?

Some other usages of the type Unit (I'm sure the list is not exhaustive):

(1) The value of type Unit is used to simulate functions of arity 0 in strict languages that don't have zero-argument functions, like in OCaml: f (). Essentially this is just for deferring computations.

(2) It also can be used to instantiate some parametrically polymorphic type when the actual "payload" is not some data, but the shape of a data structure, like when it's only the length of a list is of interest to us.

(3) Unit is used in dependently typed languages, for instance as a type-level analogue of the empty list or a dummy value.
A simple example in Coq:

Fixpoint nat_to_tuple (n : nat) : Set :=
match n with
  | O => unit                 (* ! *)
  | S n' => nat * nat_to_tuple n'
end % type.

Eval compute in (nat_to_tuple 3).

(* Evaluates to (nat * (nat * (nat * unit)))
   Note: unit in Coq corresponds to Unit in the question;
         nat is the type of natural numbers;
         Set is the type of types of programs.
 *)

You might want to take a look at a more educational (but longer) example on implementing the head function(hd) for length-indexed lists in the Certified Programming with Dependent Types book by A. Chlipala.


Pseudo code of recursive method of printing all permutations of $n$ given integers I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different.

Is there a way to explain this code more easily as I really don't get the purpose of the swapping.

PERMUTATE(A, start, end)
   if start == end return A
   else
      PERMUTATE(A,start+1,end)
      for i = start+1 to end
         SWAP(A[i],A[start])
         PERMUTATE(A,start+1,end)
         SWAP(A[start],A[i])

Your procedure produces all permutations of the input, returning it to its original state at the end.

When the input has length 1, there is nothing to do.

Otherwise, suppose that the input is $a_1,\ldots,a_n$. Let us represent all permutations of $a_1,\ldots,a_n$ as $[a_1,\ldots,a_n]$.

Here is what the procedure does:

Output $a_1,[a_2,a_3,\ldots,a_{n-1},a_n]$.
Output $a_2,[a_1,a_3,\ldots,a_{n-1},a_n]$.
Output $a_3,[a_2,a_1,\ldots,a_{n-1},a_n]$.
...
Output $a_n,[a_2,a_3,\ldots,a_{n-1},a_1]$.

In the first step, the procedure just goes over all permutations of the tail of the list, consisting of all but the first element.

In the second step, it switches $a_1$ and $a_2$, goes over all permutations of the tail, and then switches $a_1$ and $a_2$ back.

In the third step, it switches $a_1$ and $a_3$, goes over all permutations of the tail, and then switches $a_1$ and $a_3$ back.

And so on, until in the $n$th step, it switches $a_1$ and $a_n$, goes over all permutations of the tail, and then switches $a_1$ and $a_n$ back.


Flaw with Cross Entropy Error in Neural Networks I've recently been working on creating a neural network to classify handwritten digits. I implemented 1-of-N encoding such that there are the same number of output nodes as possible digits (The expected output is 0 for all digits' nodes except for the digit that was inputted, which would be 1).

Because this is a classification problem, I opted for Cross Entropy Error. I followed this model shown here: https://visualstudiomagazine.com/articles/2014/04/01/neural-network-cross-entropy-error.aspx
and also shown here:
http://www.mathworks.com/help/nnet/ref/crossentropy.html

The error function is:

$$-\frac1n\sum y\ln(\hat y)$$

Where $y$ is the expected output and $\hat y$ is the predicted output.

However, after I implemented my network I noticed a problem. Because this formula for cross entropy error does not account at all for the error of the predicted output for the nodes that have an expected output 0 (since the CE function multiplies all of those costs by the expected 0), the network tunes the weights/biases to always output nodes close to 1. Therefore, I end up getting a list of 1s. According to the CE cost function this is good because one of the outputs is spot on, but it doesn't even look at the other nodes' error  (which is huge), so it is impossible to decide on one output.

Maybe I'm missing something? I see the alternate CE function is

$$-\frac1n\sum y\ln(\hat y) + (1-y)\ln(1-\hat y)$$

but according to the MathWorks link above, it shouldn't be used for 1-of-N encoding where there are more than $N=1$ output nodes (Not sure why this is the case).

So my question would be:
Why is the first Cross Entropy Error equation viable for classification if it does not account for the error of the nodes where 0 is expected, as it always tends all the nodes to 1?

Make sure you use softmax as your final layer.  This will ensure that the outputs sum to 1.  You need this for cross-entropy loss to be meaningful.

Note that the correct cross-entropy loss is

$$-\frac{1}{n} \sum_{i=0}^9 y_i \log \hat{y}_i,$$

where $i$ ranges over all of the classes.  You omitted the dependence on the classes.

Once you change the outputs to use softmax, the anomaly you saw can't happen.  The network can't cause all nodes to output 1, because softmax renormalizes the outputs so they sum to 1.  This then works cleanly with cross-entropy loss, which only makes sense if the outputs are guaranteed to sum to 1 (i.e., cross-entropy loss only makes sense if we have $\sum_i y_i = 1$ and $\sum_i \hat{y}_i = 1$).


What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time? Here we see a very interesting attempt to show that $\mathrm{P} \ne \mathrm{NP}$ by Norbert Blum.

Here we see 116 previous attempts at solving P vs. NP.

Here we see the P vs NP problem defined as:

  The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time).

Here the commentator writes:

  I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

My question is: What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

In short, if we prove $P=NP$, then we know a whole lot more about computation than we did before, even if we don't find the algorithm, and that was the objective behind research on $P=NP$ all along.

It's much worse, because most researchers believe that $P\ne NP$, meaning that even when the proof is discovered, it means that we won't be able to find a polynomial-time algorithm for SAT, not because we're looking in the wrong places, but because no such algorithm exists.

But that doesn't worry most complexity theorists, because the would-be algorithm for SAT that you describe is only a practical application, a spin-off, of the proof. And if you care about practical applications, then why are you working on $P=NP$? It's the most theoretical question in computer science!

Rather, the motivation behind research in this direction is* to better understand computation, very much akin to why mathematicians care about the Riemann hypothesis, and why physicists build giant particle colliders, even though we already have giant databases of prime numbers and even though the discovery of new particles mostly does not help us build faster rockets or better fusion reactors.

But what don't we understand about computation? We can build marvellous AI systems that recognize faces and Chinese characters, and predict the weather! Those are results of the form, this problem can be solved with so-and-so many resources, but on the flip side, one can ask, for this problem, what is the minimum amount of resources needed? The current state of affairs in the last regard is rather embaressing, because as far as we know:

SAT has a linear-time (!) algorithm**
SAT has an algorithm that uses $O(n^{1.802})$ time and $O(\sqrt{n})$ space
every language in $NP$ has a circuit with $5n$ gates.
The Succinct Circuit Satisfiability problem***, which is $NEXP$-Complete ($NEXP$ is the exponential-time version of $NP$), can be solved in polynomial time with a randomized algorithm with bounded error (i.e. it gives the wrong answer only with probability $\leq \frac{1}{n}$)
Everything that can be computed using a polynomial amount of memory can be solved using a polynomial amount of time. For example, the Quantified Boolean Formula problem, which is like SAT except instead of an $\exists$ quantifier, there are any number of $\exists x\colon\forall y\colon\exists z\colon\cdots$ quantifiers.

Until these ridiculous scenarios are ruled out, we cannot honestly say that we understand computation in any depth. And that is the utility that you ask for, of why anybody at all works on $P=NP$.

I encourage you to read this wonderful survey of Scott Aaronson where in section 1.2 he addresses all the usual objections, like, what if $P=NP$ but we can't find the algorithm, or what if we do, but it's exponent is hopeless, or...

*as far as I can tell, as someone who is not a professional complexity theorist, but who did write his Master's thesis on the topic.

** We do not know whether nondeterminism gives you an advantage for solving SAT, but we do know, since 1983 [1] that nondeterminism gives you an advantage for some language, because there is a language $L$ solvable by a non-deterministic machine in $O(n)$ time but not by any deterministic machine in $O(n)$ time. In 2001, that result was improved [2] to a language in $NTime(n)$ but not in $DTime(n\sqrt{\log(n)})$.

*** The Succinct Circuit Satisfiability problem is this: fix some encoding of Boolean circuits as binary strings. You are given a circuit on $n$ inputs. Interpret the truth table of this circuit as a binary string of length $2^n$. Interpret that string as representing a circuit. Is that circuit satisfiable?

[1] Paul, Wolfgang J., et al. "On determinism versus non-determinism and related problems." Foundations of Computer Science, 1983., 24th Annual Symposium on. IEEE, 1983.

[2] Santhanam, Rahul. "On separators, segregators and time versus space." Computational Complexity, 16th Annual IEEE Conference on, 2001.. IEEE, 2001.


Linked allocation in operating systems: why not use a doubly linked list? I'm reading here that linked allocation uses a linked list, where each block has a pointer to the next block. For sequential access, this would take moving through the blocks one by one. Would it not better to use a doubly linked list so that this time could be cut in half?
Algorithmic analysis
I understand that sequential access remains ( O(n) ) worst case time for both singly linked list and doubly linked list. But non-asymptotically the time spent does become half.

Singly and doubly linked lists have the identical (terrible) linear access time. Using doubly linked lists would not help performance. The only benefit you'd get is that reading file backwards is more efficient.
No modern file system uses linked allocation anymore. Most use ranges of consecutive blocks, so called extents. Extents are usually more space-efficient and support random access. Neither Singly or doubly linked lists support random access. In practice these days the metadata for a file is read in at once (with all its extents), this is fast. Reading all nodes of the linked lists would mean reading several blocks, one after the other. This is slow, obviously.


Understanding when to count key comparisons I understand that for something like Linear search, this would be the key comparison:

 if(itemToFind == a[i])
    return i;

If I put this method into another method, say a Sorting method, do I still count the linear key comparison plus the sorting key comparison? Or do I only care about the sorting key comparison?

Example:

 public class SortAndSearch{

 void QuickSortAndSearch(A, p, r){
      if(p<r)
         q = Partition(A,p,r)

      if(itemToFind == a[i])
    return i;
 }

I'll answer some other question first: Why do we count key comparisons?

When analysing the runtime of an algorithm it can be tedious to count all the operations (even more so, if we notice they don't all take the same time). So it is convenient to identify those operations that dominate the runtime and only analyse those.

In the case of searching the dominant operation are key comparisons, in the case of sorting, they are key comparisons and swaps. Furthermore, most sorting algorithms will only swap elements that they have compared just prior. Thus the number of comparisons gives an upper bound for the number of swaps as well. So we can get away with counting the number of comparisons in order to get an idea of how the (worst-case) runtime of an algorithm behaves.

Now to your actual question:

If key comparisons are the dominant operation, e.g. in an algorithm that combines sorting and searching, then it is useful to count all key comparisons, if we want to get an idea of the runtime.

If, on the other hand the key comparisons are dominated by some other operation, then it might make more sense to count those other operations and not count any key comparisons.

Or the key comparisons are one of several operations, neither of which dominates the others, then we count all of those. Or in one part of the program key comparisons are dominant, while in another part they are not. Or ...


How can I embed a Knowledge Graph in a vector space? I am interested in embedding a Knowledge Graph in a vector space jointly with logical rules.

Through Google, the best work I have found about that is Tim Rocktäschel's paper Injecting Logical Background Knowledge into Embeddings for Relation Extraction.

The problem is that there is no throughly explanation about the matrix factorization in the paper or in Tim Rocktäschel's thesis or lectures.

My question is: What is the meaning of the rows of the matrix P x k and the columnns of k x R?

I would encourage you to start with this survey paper by Nickel et al.: https://arxiv.org/abs/1503.00759

Recent notable models:

ComplEx-N3: Lacroix et al. Canonical Tensor Decomposition for Knowledge Base Completion. 2018.
HypER: Balazevic et al. Hypernetwork Knowledge Graph Embeddings. 2018.
TuckER: Balazevic et al. TuckER: Tensor Factorization for Knowledge Graph Completion. 2019.
M3GM: Pinter and Eisenstein. Predicting Semantic Relations using Global Graph Properties. 2018.

Regarding your particular question, the Pxk matrix contains k-dimensional row vectors, one for every entity-pair in the knowledge base (P many) and the kxR matrix contains k-dimensional column vectors, one for every binary relation in the knowledge base. Note though that the paper you referring to here is already an extension over traditional knowledge graph embedding methods in that it assumes additional first-order logic background knowledge.


Assigning books to boxes I am trying to model the following problem correctly as a min-cut network flow problem. I have $n$ books and 2 boxes. I also have books that I know must go in one of the two boxes. In addition, each book has a certain profit if I put it in the same box with another book. So for instance, if I pair book $i$ with book $j$ I might have a profit of 10 dollars so long as they're in the same box. If I have 3 books in one box, I'd have to sum the profit of 1 and 2, 2 and 3, and 1 and 3. I want to find the best way to assign the not-yet assigned books to either box 1 or 2 to maximize my profit. Formally:

2 boxes: $b_1$ and $b_2$
Set: $N$ of $1...n$ books
$S_1$ = set of all books that must go to box 1
$S_2$ = set of all books that must go to box 2
$p_{ij}$ = The profit by having books $i$ and $j$ in the same box
Objective (roughly): $max(\sum_{i=1}^{2}\sum p_{ij})$ (maximize the profit over all boxes)

My ideas so far:

Formulate the problem as a min-cut problem because we are trying to end up with two sets of books (one for box 1, one for box 2). Would it be correct to say that $-min(-\sum_{1}^{2}\sum p_{ij})$ is equivalent to our maximization above? I tried simplifying it further but I'm not sure how.

Make source node for box 1, node for each book not assigned (not in $S_1$ and not in $S_2$) and a sink node for box 2.

My question:

With the previous formulation in mind, I'm confused on what the edges would be like. I have edges from box 1 to the book nodes and then the book nodes to box 2 but I'm not sure if this makes sense, largely because I need to make sure my summation notation is correct and how to turn that into an appropriate graph. Could anyone offer advice on the minimization I wrote above and how to translate it to a graph correctly?

First, I assume that it doesn't matter which box a pair of books go into, e.g., the value of book 1 and 2 being in box 1 is the same as the value of book 1 and 2 being in box 2.
Now, denote $B_1, B_2$ as the books in boxes 1 and 2 respectively.  The value of this partitioning is precisely
$$ \sum_{{i,j} \in B_1:\ i<j} p_{ij}+ \sum_{{i,j} \in B_2:\ i<j} p_{ij}= \sum_{{i,j} \in N:\ i<j} p_{ij} - \sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$$
(in words, the value of the paired books in box 1 + the values of the paired books in box 2 = the value of all paired books - the value of the books that aren't paired)

Observe that $\sum_{{i,j} \in N:\ i<j} p_{ij}$ is constant regardless of how you place your books and therefore maximizing $\sum_{{i,j} \in B_1:\ i<j} p_{ij}+ \sum_{{i,j} \in B_2:\ i<j} p_{ij}$ is equivalent to minimizing $\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$ (as you've roughly stated).

Under this assumption (that the box doesn't matter), we now exactly have a min cut problem.

Let your set of vertices be $N$ (there is no need for a source node to identify which box is which).  We let the graph be complete (there is an edge between every pair of nodes) the value of the edge between $i$ and $j$ is $p_{ij}$.  A cut on this graph is a partitioning ${B_1,B_2}$.  The value of such a cut is $\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}$.  Hence, to find the maximum way to place your books, it suffices to find a minimum cut on this graph.

In the event you want a formulation with terminal nodes (sink/sources), you can add in dummy nodes s and t (denoting box 1 and box 2), connect edges from all books to these nodes with an arbitrary weight W. A partitioning that divides s, t has weight
\begin{align}\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+\sum_{j\in B_2}p_{sj}+\sum_{i\in B_1} p_{it}&=\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+|B_2|⋅W+|B_1|⋅W\\
&=\sum_{i \in B_1}\sum_{j\in B_2}p_{ij}+|N|⋅W.\end{align}

In this formulation, a valid cut is $\{s\},\{t,N\}$ with value $W\cdot |N|$ and therefore to ensure at least one book goes in each box, $W$ needs to be made large.

There is one final component of your problem we have not addressed, i.e., there is a set of books $S_1$ that MUST go into box 1 and a set $S_2$ that MUST go into box 2.

Off the top of my head, I do not see a way to fix this without incorporating a source and sink $s$ and $t$ (for box 1 and 2 respectively).  The formulation I've given above is almost sufficient.   If $j\in S_1$ (book j MUST go into box 1), make $p_{sj}$ arbitrarily large (much more than $W$).  This ensures an arbitrarily large cost will be charged if you try to but a book that must go into box 1 into box 2.  Similarly, if $i\in S_2$, make $p_{jt}$ arbitrarily large.

Assuming $S_1$, and $S_2$ are non-empty (that books are already forced into each box), $W$ can be taken as 0 (since a proper partition is enforced by $S_1,S_2$) and $p_{sj}=p_{it}$ for $j\in S_1, i\in S_2$ can be as little as $\sum_{{i,j} \in N:\ i<j} p_{ij}$ (assuming each $p_{ij}\geq 0$).


No compression algorithm can compress all input messages? I just started reading a book called Introduction to Data Compression, by Guy E. Blelloch. On page one, he states:

The truth is that if any one message is shortened by an algorithm, then some other message needs to be lengthened. You can verify this in practice by running GZIP on a GIF file. It is, in fact, possible to go further and show that for a set of input messages of fixed length, if one message is compressed, then the average length of the compressed messages over all possible inputs is always going to be longer than the original input messages.
Consider, for example, the 8 possible 3 bit messages. If one is compressed to two bits, it is not hard to convince yourself that two messages will have to expand to 4 bits, giving an average of 3 1/8 bits.

Really? I find it very hard to convince myself of that. In fact, here's a counter example. Consider the algorithm which accepts as input any 3-bit string, and maps to the following outputs:
000 -> 0
001 -> 001
010 -> 010
011 -> 011
100 -> 100
101 -> 101
110 -> 110
111 -> 111

So there you are - no input is mapped to a longer output. There are certainly no "two messages" that have expanded to 4 bits.
So what exactly is the author talking about? I suspect either there's some implicit caveat that just isn't obvious to me, or he's using language that's far too sweeping.
Disclaimer: I realize that if my algorithm is applied iteratively, you do indeed lose data. Try applying it twice to the input 110: 110 -> 000 -> 0, and now you don't know which of 110 and 000 was the original input. However, if you apply it only once, it seems lossless to me. Is that related to what the author's talking about?

What you are missing is that you need to consider all bits of size 3 or less. That is: if in a compression scheme for bits of size 3 or less we compress one of the 3-bit strings to a 2-bit string, then some string of size 3 or less will have to expand to 3 bits or more.

A losless compression scheme is a function $C$ from finite bit strings to finite bit strings which is injective, i.e., if $C(x) = C(y)$ then $x = y$, i.e., $C(x)$ uniquely determines $x$.

Consider an arbitrary compression scheme $C$ and let $S$ be a set of binary strings. We can express how well $C$ works on $S$ by computing the ratio
$$\text{CompressionRatio}(C,S) = \frac{\sum_{x \in S} \mathrm{length}(C(x))}{\sum_{x \in S} \mathrm{length}(x)}.$$
A small compression ratio is good. For example, if it is $1/2$ that means we can on average compress strings in $S$ by 50% using $C$.

If we try to compress all strings of length at most $n$ then we are in trouble:

  Theorem: Let $S$ be the set of all strings of length at most $n$ and $C$ any compression scheme. Then $\text{CompressionRatio}(C,S) \geq 1$.

So, the best compression scheme in the world is the identity function! Well, only if we want to compress random strings of bits. The bit strings which occur in practice are far from random and exhibit a lot of regularity. This is why it makes sense to compress data despite the above theorem.


Conditional Probabilities as Tensors? Is it proper to view conditional probabilities, such as the forms:

P(a|c)

P(a|c,d)

P(a, b|c, d)

...and so forth, as being tensors?

If so, does anyone know of a decent introductory text (online tutorial, workshop paper, book, etc) which develops tensors in that sense for computer scientists/machine learning practitioners?

I have found a number of papers, but those written at an introductory level are written for physicists, and those written for computer scientists are rather advanced.

This is definitely possible, although the tensor has of course certain additional structure (constraints).

If you consider the following conditional defined for a categorical response $Y$ on categorical predictors $X_i$:

$P(Y|X_1,\ldots,X_n)$

this correspond to a conditional probability tensor of size $d_0 \cdot d_1 \cdot \ldots \cdot d_n$. Here $Y$ (as a categorical response) takes $d_0$ levels.

Foremost the elements of the tensor have each to be nonnegative.

You can find papers on this, e.g. "Bayesian Conditional Tensor Factorizations for
High-Dimensional Classification" by Yang and Dunson (pdf, arxiv).

Of course, if the random variables concerned are not categorical variables, but either continuous random variables or taking an infinite number of values (or both), the mapping to finite tensors won't be so trivial. You'll need something like an infinite tensor (as an extension of an infinite matrix).


Median of distribution with memory constraint Task
I want to approximate the median of a given distribution $D$ that I can sample from.
A simple algorithm for this, using $n$ samples, is:
samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

However, I am looking for an algorithm that requires less than $O(n)$ space.
Ideas
I have looked into these algorithms:

Median of medians: Needs $O(n)$ space, so it does not work for me.
Randomized median: It seems like this could be easily generalized to an algorithm that uses $O(n^{3/4})$ space.

Are there any other algorithms that use less then $O(n)$ space that could solve my problem? In particular, I was thinking there may be an algorithm that uses $O(m)$ space by generating batches of samples from $D$ of size $m$...
Details

Ideally, I am looking for a reference to an algorithm that also includes analysis (success probability, expected runtime, etc).
Actually, I need an algorithm to estimate $D$'s $p$-th percentile for a given $p$, but I am hoping most median-finding algorithms can be generalized to that.
I would like to achieve the same accuracy as the simple algorithm shown above. One way to achieve this is by using an algorithm whose output distribution is the same as the sample algorithm (but maybe the new algorithm may fail in rare cases)

Sure, you can definitely achieve this using a bit more running time.  Here is a conceptually simple approach, which might not be optimal, but will get you started and is probably pretty good:
Use binary search to find an approximate median $m$.  How do you know whether is candidate $m$ is too large or too small?  Sample $n'$ times from the distribution, count how many times the samples are $\ge m$, and compare that count to $n'/2$. This can be done with $O(1)$ space.
Then the key question becomes: how do we choose $n'$, to control the probability of error?  A simple approach is to choose $n'$ to be sufficiently bigger than $n$ that the probability of error in each iteration of binary search is $t$ smaller than the probability of error when using $n$ samples, where $t$ is the number of iterations of binary search needed to achieve the desired accuracy.  Then, a union bound ensures that this will meet your accuracy conditions.
Unfortunately, your accuracy condition is a bit hard to work with, when we don't know anything about the distribution of data, as the accuracy of the sample median can be arbitrarily bad.  For instance, consider a distribution that outputs $0$ with probability $(1-\epsilon)/2$ and $100$ with probability $(1+\epsilon)/2$.  Then the sample median is about equally likely to be 0 or 100, whereas the distribution median is 100,
so the average error of the sample median is about 50 (unless you're drawing $\gg 1/\epsilon^2$ samples).  That's a particularly nasty distribution, and it's going to be hard to work with.  But if you assume the distribution is approximately Gaussian (say) with standard deviation $\sigma$, then the error of the sample median, with $n$ samples, is roughly $1.25 \sigma/\sqrt{n}$.  Thus, the above algorithm can be used where we set $t \approx \lg (\sqrt{n}/1.25)$ and we set $n' \approx n t^2$.
That's one simple approach.  You can probably do better.  You might like to look up streaming algorithms for computing the median, as they tackle the problem you're working with: given an unlimited number of samples from the distribution, but only a limited amount of space, what's the best estimate we can get for the median?  For instance, here is one simple algorithm: the first layer repeatedly takes three samples and outputs the median of those three; the second layer repeatedly takes three numbers from the first layer and outputs the median of those three; and so on.  After logarithmically number of layers, you get a reasonable approximation to the median.  There's an entire literature on this subject, and you should be able to find lots more.


How much does regularization prevent overfitting? I've been curious why machine learning algorithms with high VC dimension, such as XGBoost and deep learning, do well in practice.  The answer appears to be regularization significantly restricting the parameter space, but the only justifications I've seen are references to Occam's razor.

Is there quantitative/theoretical understanding of how much regularization can prevent overfitting in a model?

Background:
I've taken a course in machine learning and covered the theory behind regularization and a couple techniques, such as lasso and ridge regression.  I understand the principle that regularization can reduce the VC dimension by minimizing or zeroing weights in the model.

But, that principle does not clarify in my mind whether regularization is adequate to counteract the high VC dimension in models used by XGBoost and deep learning.

I am asking for some sort of quantitative theory that provides justification that even with high VC dimension regularization can reduce the dimensionality enough to provide a decent guarantee of generalization.

Alternatively, providing a method I can use to figure this out myself is also acceptable.

Moritz Hardt's excellent blog outlines extensive research into the idea that stability in machine learning methods is related to the idea of generalization. Interestingly, we find that regularization implies stability.

Formally, given observations $S = (z_1, \dotsc, z_n)$ and algorithm $A$, stability is defined as the expected difference between the risk and empirical risk $$\mathbb{E}[R - R_e] = \Delta,$$ where $R_e = \ell(z, S) = \frac{1}{n} \sum_i \ell(z_i, A(S))$ is the empirical risk and $R = \mathbb{E}_{z \sim D}[\ell(z, A(S))]$ is the risk.

The post details how to obtain bounds on $\Delta$ and its implications much better than I ever can. I highly recommend reading that post along with all of his other posts.

A much more practical argument is that regularization constrains the problem space to a very specific subset of models; namely, regularization methods can be recast as constrained optimization where $\|\beta\|_p \leq  c$ for some value of $p$. This is equivalent to using prior knowledge about the problem and forcing the solution to be within some constrained space.


Why theta(n^2) if m=floor(n/2) for Naive String-matching I’m reading CLRS(Introduction to Algorithm, 3rd edition). In the chapter 32.1 about the naive string-matching algorithm, the book says the worst case running time is $\Theta(n^2)$ if $m = \lfloor \frac n2\rfloor$. I get that when $m$ equals $\frac n2$, but I don’t see it when $m$ is less than $\frac n2$. Any hint or suggestion is very appreciated!  m is the length of the pattern string, n is the length of the text to be searched for the pattern. The book uses (n-m+1)m to calculate the running time.

Here is the relevant excerpt from Introduction to Algorithm by CLRS, 3rd edition.

  Procedure NAIVE-STRING-MATCHER takes time $O(n - m +1)m$, and this bound is tight in the worst case. For example, consider the text string $a^n$ (a string of $n$ a’s) and the pattern $a^m$. For each of the $n-m+1$ possible values of the shift $s$, the implicit loop on line 4 to compare corresponding characters must execute $m$ times to validate the shift. The worst-case running time is thus $\Theta((n-m+1)m)$, which is $\Theta(n^2)$ if $m=\lfloor n/2\rfloor$.

Proposition: Let $f(n,m)=\Theta((n-m+1)m)$ be the worst-case running time where $1\le m\le n$. If $m=\lfloor\frac n2\rfloor$, then $f(n,m)=\Theta(n^2)$.

Proof. There are constants $c_1, c_2\gt0$ such that for all $1\le m\le n$,
$$c_1((n-m+1)m)\le f(n,m)\le c_2((n-m+1)m).$$

Now let $m=\lfloor \frac n2\rfloor$. Since $1\le n+1-2\lfloor\frac n2\rfloor\le2$, for $n\ge2$,
$$ \begin{align}
\frac{n^2}4&\lt\left(\frac{n+1}2\right)^2-1\\
&\le \left(\frac{n+1}2\right)^2-\left(\frac{n+1-2m}2\right)^2=(n-m+1)m\\
&\le\left(\frac{n+1}2\right)^2-\frac14\lt n^2
\end{align}$$
So $$\frac{c_1}4n^2\lt f(n,m)\lt c_2 n^2,
$$
which says $f(n,m)\in \Theta(n^2)$.


What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not.

For example, consider the following two trees:

Example trees T and U are isomorphic.
An isomorphism (bijection) is described in the table below:

  T          U
  1          2
  2          4
  3          1
  4          5
  5          3
  "white"    "green"
  "blue"     "white"

Below are some things to know about the problem:

Nodes are colored
edges are not colored.
Nodes are free to be any
color. Adjacent nodes are allowed to be the same color.
which node is
the root node of each tree cannot be changed.
children are un-ordered.
the tree is not necessarily a binary tree. a node could have 3 children, 4 children, 5, etc...

Formally, a colored tree is a tuple (VS, ES, root, color_set, color_map) such that:

VS is the vertex set
ES is the edge set
(VS, ES) is a undirected tree
root is a element of VS
color_set is a set of objects called "colors"
color_map is a mapping from VS to color_set
every element of  color_set appears in the range of color_map at least once. That is, every color is applied to at least one node.

colored trees T and U are isomorphic if and only if there exists a bijection, PHI from the vertex set of T, VT, to the vertex set of U, VU such that:

the root of one tree is matched to the root of the other tree
for all nodes v, w in VT, {v, w} is an edge in tree T if and only if {PHI(v), PHI(w)} is an edge in tree U
for all nodes v, w in VT, v and w are the same color in tree T if and only if PHI(v), PHI(w) are the same color in tree U

Why should we even expect that there is such a polynomial-time algorithm? The comment

  Do you know how to solve this without the colors? That would be a good start. – Yuval Filmus Jun 15 '19 at 14:24

has an upvote, but it only hints implicitly that there is a (simple?) solution. Let me try to guess the (simple?) solution that is expected here. The AHU algorithm by Aho, Hopcroft and Ullman produces a canonical labeling of trees. Let's interpret the AHU algorithm as an efficient implementation of color refinement for rooted trees, and ask whether color refinement for "labeled trees" (isomorphism of "colored trees" would not allow to swap colors) would always be able to decide isomorphism. The answer is "no", because isomorphism of labeled trees is GI complete:

  From a graph G, construct a rooted labeled tree T by putting a node below the root of the tree for every vertex of G. For every edge of G, put two nodes with the same label on the next lower level. An edge has two endpoints, connect the corresponding vertices (or rather the tree nodes corresponding to them) each with one of the tree nodes corresponding to the edge.

The link above also makes it clear that this is well known by citing

    Theorem: Marked tree isomorphism is isomorphism complete

  from section 6.4 Marked Graphs and Marked Trees in Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo. They used the definition that “A marked graph is a graph together with a partition of its vertices. An isomorphism of marked graphs is an isomorphism of the underlying graphs which preserves the partitioning.”


Solving recurrence relation having square root T(n) = 2T(√n) + n.

I tried putting n=2^m

T(2^m) = 2T(2^(m/2)) + 2^m.

If I subsitute T(2^m) = S(m) then,

S(m) = 2S(m/2) + 2^m.

This is same as (1*2^m) + (2*2^(m/2)) + (4*2^(m/4)) + ...

Now I am stuck in this summation as it's not a GP.

Can someone please help?

The solution is $T(n) = \Theta(n)$. It is easy to see that $T(n) = \Omega(n)$ (indeed, $T(n) \geq n$), and you can prove $T(n) = O(n)$ by induction: choose some constant $C>0$. Suppose that you have shown that all small enough $n$ satisfy $T(n) \leq Cn$. Then for larger $n$,
$$ T(n) \leq 2T(\sqrt{n}) + n \leq 2C\sqrt{n} + n = \left(\frac{2C}{\sqrt{n}} + 1\right)n. $$
This is at most $Cn$ if $2C/\sqrt{n}+1 \leq C$, and in particular if $n \geq 16$ and $C \geq 1$. Therefore if we define $C = \max(1,T(1)/1,\ldots,T(15)/15)$ then the argument above shows that $T(n) \leq Cn$.


$\Theta(n^2 ) =\Theta(n^2 + 1)$ I'm reading The Algorithm Design Manual and this is one of the excersizes:

Prove or disprove the following statement:
$\Theta(n^2 ) = \Theta(n^2 + 1)$

I think this is untrue because the right side of the equation claims to have a multiple $c$ such that it is smaller than all the multiples of $n^2$, which is untrue.
But since the book doesn't have answers and I'm not really sure about this question I had to ask.
Thanks a lot :)

As we have on both sides of equality sets, then it should be prove correspondingly i.e we need to show, that $\Theta(n^2) \subset \Theta(n^2+1)$ and $ \Theta(n^2+1)\subset \Theta(n^2) $. Let's start with first:
Assume $f \in \Theta(n^2)$. This means, that for some constants $A_1, A_2 \gt 0$ holds
$$A_1 n^2 \leqslant f(n) \leqslant A_2 n^2$$.
To obtain inequalities for $\Theta(n^2+1)$ we need
$$B_1 (n^2+1) \leqslant f(n) \leqslant B_2 (n^2+1)$$
It's easy to see, that it's enough to take $B_2 = A_2$ for right hand and $0<B_1 \leqslant \frac{A_1}{2}\leqslant \frac{A_1 n^2}{n^2+1}$ for left hand,  as $A_2>0$.


Is boolean formula isomorphism NP-complete? Problem. Given 2 functions $f,~g$ of the same length $n$, decide if we can change variables in $f$ such that it will be identical to $g$. There are exponentially many non-isomorphical functions (as number of total assignments is bounded by exponent).

Example. $f=(x\land y\land z)\lor(\overline x\lor z)$. $g=(x\lor\overline y)\land(x\lor y\lor z)$.

Replacing $x$ and $y$ in $g$: $g = (\overline x\lor y)\land(x\lor y\lor z)$.

Replacing $y$ and $z$ in $g$: $g = (\overline x\lor z)\land(x\lor y\lor z)$. It became equal to $f$.

While this is considered not to be $\mathsf{NP}$-complete for 2SAT (we can compare their implication graphs and this is GI), is this problem $\mathsf{NP}$-complete for other variants of SAT (Horn3SAT, XOR3SAT, unambiguos 3SAT; if not, then at least 3SAT)?

Also there are two variations of problem:

All clauses in formula become equal (but in this case number of non-isomorphic functions is superexponential).
Number of satisfying assignments is equal (don't suspect to be in $\mathsf{NP}$ except for 2SAT; and it is $\mathsf{NP}$-hard for 3SAT).

Your problem is $\mathrm{co}$-$\mathrm{NP}$-hard so it may also be $\mathrm{NP}$-hard but very unlikely to be $\mathrm{NP}$-complete (i.e. to be in $\mathrm{NP}$).

We reduce from TAUT which is $\mathrm{co}$-$\mathrm{NP}$-hard. Given a TAUT instance $\varphi$ with variables $x_1,\dots x_n$, output $<\varphi, ((x_1 \lor \lnot x_1)\land\dots\land (x_n \lor \lnot x_n))>$. These two formulae are isomorphism iff. $\varphi$ is a tautology.


3-Col using each colour exactly $|V|/3$ times Is the following problem in P?

Does a graph $G$ have $3$-colouring, where each colour is used exactly $|V|/3$ times?

I believe it is as we are trying to sample three sets (one for each colour) of vertices without replacement, giving a running time of $O(|V|^5)$. The first set is for three colours, the second for two and third for one col.

No, the problem is still NP-complete.  Suppose you want to know if $G$ is 3-colourable (with no limits on how many vertices can be each colour). Just make a new graph $G^+$ by adding $2|V(G)|$ new vertices with no edges between them, so $|V(G^+)|=3|V(G)|$. If $G$ has a 3-colouring then you can get a "balanced" 3-colouring of $G^+$ by setting the colours of the new vertices appropriately; if $G$ has no 3-colouring, then $G^+$ also has no 3-colouring, so it has no balanced 3-colouring, either.


How much math background do you need to understand how category theory is applied to Haskell? Basically, how much math background do you need to understand how category theory is applied to Haskell? If you already have mathematical maturity, can you jump right into it, or should you be familiar with certain subjects in algebra?

The first step is to learn category theory without regards to Haskell (and if you don't have it, Haskell without regards to category theory). A book such as Lawvere's Conceptual Mathematics is a good start. Awodey is also recommended, and Leinster's recent Basic Category Theory.


Recursion problem involving head, tail and xor Consider a set of functions:

head(l) returns first bit from list l, e.g.

head([0,1,0]) = 0,
head([1]) = 1

tail(l) returns a list by removing first element from l, e.g.

tail([0,1,0]) = [1,0],
tail([1]) = []

a:l appends bit a to beginning of list l, e.g.

1:[0,1,0] = [1,0,1,0].

xor takes takes as input two bits and returns a bit.

xor(a,b)
if (a == b)
  return(0)
else
  return(1)
endif

f1 takes as input a list and returns another list.

f1(s)
if (s == []) then
  return([1])
else if (head(s) == 0) then
  return(1:tail(s))
else if (head(s) == 1) then
  return(0:f1(tail(s)))
endif

f2 takes as input a bit and a list and returns a bit.

f2(b,s)
if (s == []) then
  return(b)
else if (head(s) == 0) then
  return(f2(xor(b,1),tail(s)))
else if (head(s) == 1) then
  return(xor(b,1))
endif

g1 takes as input a nonnegative number and returns a list.

g1(n)
if (n == 0) then
  return([0])
else
  return f1(g1(n-1))
endif

g2 takes as input a nonnegative number and returns a bit.

g2(n)
if (n == 0) then
  return(0)
else
  return f2(g2(n-1),g1(n))
endif

Can anyone explain what the function g2() returns?

I am able to find out g1() returns a list in binary
for example

g1(1) = [1]
g1(2) = [01]
g1(3) = [11]
g1(4) = [001]

Hints:

g1(0) = [0] so you can see that f1 for [0] returns [1] and for [1] returns [0]. From here g1 must be clear.
f2 takes a bit and a list of one element and returns a bit so it is one of the boolean functions of 2 variables (they are only 16)
after you know that g2(0) = 0 and the above hints it is easier to calculate g2

I can propose you to post your answer or I will update my answer after some time to be sure that it was not for homework.


Grasshopper Optimization Algorithm I am currently reading a paper on a meta-heuristic called 'Grasshopper Optimization Algorithm'.
The main idea of the algorithm is to utilize the social behavior of grasshoppers in a swarm to solve optimization problems. The distance to other grasshoppers in the swarm is used to determine, if a grashopper is repelled (exploration) or attracted (exploitation) from grasshoppers in its proximity.
However I am not sure if I understood the first part of the proposed formula correctly:
$$X_i^d = c\left(\sum\limits_{j=1,j\neq i}^Nc\frac{ub_d-lb_d}{2}s\left(\lvert x_j^d-x_i^d\rvert\right)\frac{x_j-x_i}{d_{ij}}\right) + \widehat{T}_d$$
$X_i^d$ calculates the next position of a search agent (grasshopper) with respect to the postion of the other search agents and the best found solution so far. So the next position of a grasshopper depends on its own position, the positions of all other grasshoppers in the swarm and the best solution found so far.
$\widehat{T}_d$ denotes the best solution found so far.
$c$ is a decreasing coefficient that regulates if the search agents explore or exploit in the search space. With increasing iteration count  $c$ decreases and the search agents tend to exploitation.
$s\left(\lvert x_j^d-x_i^d\rvert\right)$
The part in brackets calculates the distance between grashoppers.
$s$ is a formula which takes this value and determines if the search agents should explore or exploit.
$\frac{x_j-x_i}{d_{ij}}$ is a unit vector, where $d_{ij}$ denotes the distance between two grasshoppers.
It states that $ub_d$ is the upper bound and $lb_d$ is the lower bound in the $d$-th dimension.
It further states that the part $c\frac{ub_d-lb_d}{2}$ linearly decreases the space that grasshoppers (search agents) should explore and exploit.
I dont undertsand what is meant with 'upper and lower bound in the $d$-th dimension'.
Upper and lower bound for what exactly?
Can somebody help?
Information extracted from this paper:
Grashopper Optimization Algorithm

I suspect they probably mean
$$ub_d = \max_i x_i^d$$
where $x_i^d$ is the $d$h coordinate of $x_i$; and similarly for $lb_d$, but using $\min$ instead of $\max$.  But I don't know -- I am just speculating based on context.


Swap space management during pure demand paging The following is a doubt that I came across while doing a OS home assignment - however, it seems more concept-based than a straightforward coding question, so IMHO I don't think the homework tag is appropriate for this.

In a pure demand paging scheme for multiple processes running at the same time, given a fixed amount of RAM and Swap memory, what happens in the following 2 cases w.r.t the swap space, when

A process encounters a page-fault, and there are no free frames available in the RAM, hence requiring one of the pages from the process' chunk of Kernel Frames to be written out to swap (for simplicity, I'm not considering the copy-on-write case). Explicitly, where in the Swap space would this frame be written, and what data structures need to be updated for that?
When a process needs to page-in a particular page, where does it look in the Swap memory, and how would it know if that particular page be present in Swap at all ?

As you can well imagine, I'm having difficulty understanding in what way to manage the Swap space during pure demand management scheme, and what data structures would be essential. It would be great if you could refer to any links in your answer (I searched in "Operating System Concepts - 8th edition by Silberschatz, I couldn't find an explicit answer for my question).

To answer this question I will visit some prerequisite understanding. Pure demand paging cannot be accomplished without hardware support. All modern computer architectures support paging, however many have different implementation details.

x86 processors use what is called a page table to keep track of virtual address spaces and page mappings, as well as bits about access privilages and, more relevant, whether or not that page is even present in physical memory. Violations trigger page faults which are trapped by the OS.

For more information on that, see this article.

In order to answer the question of page swapping, we must first visit the question of how the operating system keeps track of what pages are used by what process and how they are allocated. There are many different data structures that can be used for such. A flat bit array marking whether a frame is allocated or not is one way. Linked lists or stacks is another. With pure demand paging, allocated pages are not actually marked as present when they are allocated. This has the effect that no physical ram is set aside for a process until it actually writes to it. Once it does, the hardware throws a fault which the OS traps, and then the OS uses a swapping algorithm if there are no available physical pages to assign to the already allocated virtual page.

For more information on page frame allocation, see here. There you will see a general overview of some suitable datastructures.

Once a suitable algorithm for page allocation is implemented, another for allocating disk space for swapping must be chosen. Windows, as an example, has historically used a flat file in the filesystem for page swapping. I would imagine that for each node in the datastructure keeping track of allocated pages there is an assocated pointer to an offset in the file, indicating the position of the page in the disk. Unix-like operating systems have traditionally used separate partitions for page swapping which is arguably faster since there is no filesystem layer.

It is also possible to divorce the swapping algorithm datastructures from those of the allocation algorithm, however the two are related so this is probably not often done.

I hope that answers your question despite the relative brevity with which I have treated it. I found that the best way to learn about operating systems is to dive into the sometimes nasty architectural specific details that can be found in sites like wiki.osdev.org and  www.osdever.net which specifically deal with hobby OS making and provide excellent tutorials on such details.


Can the end-to-end principle be formalized? In the late 1990s, when I was in graduate school, the paper

  JH Saltzer; DP Reed; DD Clark: End-to-end arguments in system design. ACM Trans. Comput. Syst. 2(4):277-288, 1984. DOI=10.1145/357401.357402

was pretty much required reading in every operating systems class at every university, and it still seems to be one of the primary guiding principles underlying the design of the internet.  (See for example: J Kempf, R Austein (eds), and the IAB, "The Rise of the Middle and the Future of End-to-End: Reflections on the Evolution of the Internet Architecture," RFC 3724, March 2004.)

The end-to-end principle states (Saltzer et al., 1984):

  [If] the function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system, ..., providing that questioned function as a feature of the communication system itself is not possible. [Although] sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.

Or more briefly (from the abstract):

  The end-to-end argument suggests that functions placed at low levels of a system may be redundant or of little value when compared with the cost of providing them at that low level.

But I've had little success applying the end-to-end principle in my own experience (which is in computer architecture, not internet architecture).  Since the principle is stated as a "poem" (i.e., in English prose with a bunch of terms that are not mathematically defined) it is quite easy to fool oneself into thinking that "the function in question can completely and correctly be implemented only with the knowledge and help of the application."  But what is "the function in question," let alone "the knowledge and help" of an application?

Example: On-chip networks (unlike the internet) aren't allowed to drop packets, but have quite limited buffering, so you need to have some way of either avoiding or recovering from deadlock.  On the other hand, the application needs to make itself deadlock free as well, right?  So I might reason that I should make the common case (no deadlock) fast and push deadlock avoidance off on the app.  This is, in fact, what we tried on Alewife and Fugu (Mackenzie, et al., Exploiting Two-Case Delivery for Fast Protected Messaging, Int'l Symp High-Perf Comp Arch, (HPCA-4):231-242, 1998.  Or John Kubiatowicz's dissertation.)  It "worked," (by having the interconnect interrupt the processor when the buffers got filled and having the OS augment with software buffering) but I haven't seen anyone in academia or industry (including any of us that were authors on that HPCA paper) racing around trying to replicate the idea.  So apparently deadlock avoidance in a network is not the same "function in question" as application-level deadlock avoidance, or the end-to-end principle is wrong.

Is it possible to turn the end-to-end principle from a "poem" into a theorem?  Or at least, can it be stated in terms understandable to a computer architect?

I believe there may be two shortcomings in your application of the end-to-end (e2e) principle:

Firstly, in the sense that you apply it for performance. The end-to-end is a design principle such as to ensure architecture orthogonality, composability, regularity, one or all, provide primitives etc. Such principles have been outlined in related textbooks. Performance is not one of them. In fact, Clark et al, implies that strict end-to-end may result in worse performance so it uses such, as an exception to this principle.

So, if you still want to formalize:

"The end-to-end argument appeals to application requirements, and provides a rationale for moving function upward in a layered system" so you will need formalized application requirements and formalized layered system. Here is an attempt that might help taking it one step further:

Say you have Layer(i) requirements (Layer(0) is for the set of applications you expect to support now or in the future, the application layer) and
firm interfaces Interface(i,i+1) and Interface(i+1,i) (from Layer i to i+1 pre-assume no cross-layering here, easy to change and make it a requirement) and
functions Function(i,j) (Layer i, Function index j, assume data part of function to have it simpler)

Input: Layer(0) requirements (as we said these need to be formalized)

Output: everything else

END-TO-END Output is an Output such that:
For each L, Layer(L) accomplishes its requirements only by functions Function(L,j) (i.e. functions within the layer) and Interface(L,L+1), Interface(L+1,L)

For each Layer L and function Function(L,F) there is no set of Functions S in the output such that Function(L,F)=S (= means equivalent output and side-effects)

So, coming to the second possible shortcoming for the specific e2e principle application (and if I am reading correctly what is being attempted) one can claim that it does not follow the e2e principle at all, quite the contrary. You have your chips provide "some deadlock avoidance" and you have an Interface that is out-of-the-ordinary non-firm and specific to trigger (interrupt) more help from upper layers. This is arguably a cross-layer approach not an end-to-end approach. In other words you have a Function(1,x) not accomplishing its task completely and correctly with set Interfaces - if you want to use the draft formalization provided above (which of course is just a start useful to an extend to fully answer your question but likely not full in itself).


Lambda Calculus Type Inference I'm currently trying to learn how to infer most general types on lambda calculus, and due to the lack of information on the subject I could find on Google I'm forced to attempt what I think is logical and ask here if it's correct, it's most likely not, so please correct me!

Here's a couple exercises I've got, the idea is to reduce the redex and infer the most general type:

$(λf.λg.λx.g\space x(f\space x)) (λy.y)$
$λz.λx.((λy.λw.y w)x z)$

After I reduce them:

$λg.λx.(g x) x$
$λz.λx.x z$

And my attempt to infer the most general type:

Since $g \space x$ is applied to $x$ I assumed $g$ must be $g :: a\rightarrow (a \rightarrow b)$ while $x :: a$
Then $(λg.λx.(g\space x)\space x)$ must be of type $(a\rightarrow (a\rightarrow b))\rightarrow (a\rightarrow b)$
Since $x$ is applied to $z$, let's say $z :: a$ and $x :: a\rightarrow b$, therefor the function is $a\rightarrow (a\rightarrow b)\rightarrow b$

Let me assume that you are asking about basic type inference for $\lambda$-calculus with parametric polymorphism a la Hindley-Milner (it's not entirely clear from your question). I would recommend the Types and Programming Languages textbook by Benjamin Pierce as a general reference for this sort of thing. In there you can look up parametric polymorphism and Hindley-Milner type inference. These are the buzzwords you should be Googling. And when you do, it should be easy to find many resources.

P.S. You should not reduce before type inference. You should just do type inference on the original terms.

Supplemental: to find out whether you're correct, and since you're going to do Haskell in your course, why not ask Haskell about the types?

GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Prelude> :t \g -> \x -> (g x) x
\g -> \x -> (g x) x :: (t1 -> t1 -> t) -> t1 -> t
Prelude> :t \z -> \x -> x z
\z -> \x -> x z :: t1 -> (t1 -> t) -> t

Yup, you were correct.