Dijkstra’s shortest path algorithm I'm learning about single source shortest path algorithms and need to clarify few doubts-

Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers.
Does Dijkstra’s assumes that the graph searched by it is free of cycles.
Relaxing an edge is same as setting its weight to 0.
Does Dijkstra’s yields only costs of shortest paths, requiring lot of extra computation to find the intermediate vertices on shortest paths.
Dijkstra's useful only when edge weights are geographical distances along paths traversed on ground or water.

Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers?

Dijkstra’s shortest path algorithm works for non-negative numbers. The Bellman-Ford algorithm works in the general case, i.e. works for the negative numbers, too.

  Does Dijkstra’s assumes that the graph searched by it is free of cycles.

In an undirected graph, If there is no cycle, it is a Tree, not necessarily rooted. The paths are unique. Dijkstra’s algorithm can work with cycles.

You probably mean that free of negative cycles; If there is a negative cycle and the source can reach it, then the cost of path has not defined.

  Relaxing an edge is same as setting its weight to 0.

Relaxation is historical naming, the correct name is tighten. Relaxation tests an edge wheater in can improve the current estimate of a node.

  Does Dijkstra’s yields only costs of shortest paths, requiring lot of extra computation to find the intermediate vertices on shortest paths.

Actually, it yields the shortest paths tree with their values, the running time is $\mathcal{O}((V+E)\log V).$ If you look at the algorithm, it considers only the current neighbors while constructing the shortest path tree. The bottleneck is the extract-min operation on the Heap. For a theoretical speed up, one can use Fibonacci Heaps that yield $\mathcal{O}(V \log V + E)$

During the relaxation process, the predecessors updated only if there is a need for relaxation. When the Dijkstra's algorithm finishes, the shortest path tree is ready.

  Dijkstra's useful only when edge weights are geographical distances along paths traversed on ground or water.

Remember, Dijkstra's algorithm can find one-to-all shortest path if the Graph is weighted and directed. It doesn't care where the map is taken as long as it is modeled as a Graph. However, if the graph is an actual map and/or there is also a heuristic distance information one can achieve better than Dijkstra's algorithm, see A* and this comparison article Engineering Route Planning Algorithms.


Convolutional Neural Network for Insects I've recently started learning CNN's. I need a CNN that is specialized for insects detection. Dead insects will be put on a piece of paper / container, then images will be taken from a same distance, and are at same pixels.

I am expecting to prepare my own training datasets:
- Thousands of images of a particular insect, let's say a housefly
- Each image contains only one housefly
- Consistent lighting for the photos taken

Then, I will start to train the CNN, save the model and so on.
I'm not sure about the following:

During operation of the model, will it still be able to detect the housefly if there are other insects in the image? (not covering the housefly of course)
If I want my model to recognize housefly only, so the training datasets contain housefly only, true or false?
If later I want my model to recognize 2 types of insects, housefly and ant, what type of datasets I need to prepare?
I will eventually need to count the amount of houseflies in an image. Can anyone direct me to a correct path towards feasible methods?
Does anyone has useful resources that explain on how to determine the suitable amount of convolutional layers (CL) and fully-connected layers (FCL)? The default seems to be 2 CL and 2 FCL, but I am wondering why not more than that?

The training set needs to have the same distribution of images as whatever you will be applying your classifier to.  So, if you'll be running the classifier on some images of houseflies and some images of other insects (not house-flies), your training set needs to contain both kinds of images.  If there are many other kinds of non-housefly images you'll be running the classifier on, the training set should contain images of those same kinds of insects, in a similar frequency to the frequency they'll occur when you use the classifier.

I encourage you to read about object classification vs object recognition vs object detection.  See, e.g., https://stackoverflow.com/q/31750076/781723.  The simplest kind of classifier takes an image of a single insect and outputs "housefly" or "not housefly".  That kind of classifier will be trained on images of single insects -- and should only be expected to work correctly if you apply it to images of a single insect.  However, you can also find techniques in the computer vision literature for recognizing the location of the insect in the image and dealing with multiple insects; read about object recognition and detection.

I'm not sure where you got the idea that the default is 2 convolutional layers followed by 2 fully connected layers, but there is no such default and no such rule.  I'm not saying that's an unreasonable starting point, but there are no hard-and-fast rules that tell you how many layers to pick.  Instead, you'll probably need to try several different possibilities and see how well they work.  If you can find papers in the research literature that solve a similar problem, you can sometimes use them as guidance for a good network architecture, but if you're not aware of anything like that, you'll just have to experiment on your own.


Contingent sentences can always be true I have a question about contingent sentences. To my knowledge, contingent sentences are sentences that are neither tautologies nor contradictions.

In a textbook I read that a sentence might always be true and still be contingent.

The example given was as follows: If there never were a time when the universe contained fewer than seven things, it follows that the sentence "At least seven things exist" would always be true. Yet the sentence is contingent; its truth isn't a matter of logic. There is no contradiction in considering a possible world in which there are less than seven things.

Could someone please explain why this is the case? As well as explain the example to me?

In mathematical logic - the discipline of logic that has interested computer scientists the most - there is a difference between proof-theoretic truth and model-theoretic truth.

Beyond metaphor (of which we are by no means innocent), neither has anything to do with reality, experienced or imagined, and with the idea of truth that is dealt with by empirical scientists, natural philosophers and historians, to which you allude in your question.

Contingent is, to us, another name for a sentence that is satisfiable, but not a tautology. This has to do with its truth equivalence being dependent on the axioms and rules of inference available (proof-theoretic aspect), or on the valuation of its symbols (model-theoretic aspect).

Gödel showed us that these two aspects do not necessarily go together very well, though. Caution is advised.


Finding n0, asymptotic analysis I am attempting a textbook question about asymptotic analysis. The question goes:
**
The number of operations executed by algorithms A and B is 8nlogn and
2n^2, respectively. Determine n0 such that A is better than B for n ≥ n0.
**
So far my approach has been to draw a log-log graph with both lines and find the meeting point, I am thinking that this meeting point is at log(n0) so I can find n0 from it, the one that they are looking for, but things get strange here because the two lines never meet!
Here is the picture of my graph. https://drive.google.com/file/d/1eUFkawKXCWiRBV6BV34Acs5SK4mBHMN4/view?usp=sharing
Any help with this problem will be much appreciated.

In principle it could be that $2n^2 = 8n\log n$ could have several solutions. However, this doesn't matter much: the derivative of $n/\log n$ is
$$
\frac{\log n - 1}{\log^2 n},
$$
and so if $2N^2 \geq 8N\log N$ for some $N \geq e$, it follows that $2n^2 \geq 8n\log n$ for all $n \geq N$.
Plugging in small values of $N$, we see that $2N^2 > 8N\log N$ for $N = 9$.

Here is an alternative proof. We first prove that if $n = e^k$ and $k \geq 4$ is an integer, then $2n^2 \geq 8en(\log n + 1)$. You can calculate that it holds for the base case $k = 4$. Assuming that it holds for some $k \geq 4$, we prove it for $k + 1$. The induction hypothesis implies that
$$
2e^{2(k+1)} = e^2 \cdot 2e^{2k} \geq e^2 \cdot 8ee^k (k+1) = 8ee^{k+1} (k+2) \cdot e \cdot \frac{k+1}{k+2}.
$$
To complete the proof, it suffices to check that $e (k+1)/(k+2) \geq 1$, or equivalently, that $e \geq (k+2)/(k+1) = 1 + 1/(k+1)$, which trivially holds since $k \geq 4$.
Now let $n \geq e^4$ be arbitrary, and let $k = \lfloor \log n \rfloor$. Then
$$
2n^2 \geq 2(e^k)^2 \geq 2ee^k(k+1) > 2n\log n.
$$


Algorithm for building a suffix array in time $O(n \log^2 n)$ I've been working with suffix arrays lately, and I can't find an efficient algorithm for building a suffix array which is easy to understand.  I have seen in many sites that there is an $O(n \log^2 n)$ algorithm, but I can't understand it, as many important details are omitted.  There's an example at Top Coder.

Could someone introduce me an efficient algorithm for suffix array construction, which is easy to comprehend?

You can compute the suffix array in linear time with the DC-3 Algorithm. This is a super-cool fancy algorithm that can be implemented in 50 lines of readable C++ code - one of my all-time favorites. The source code is contained in the original paper. If you can compare two characters in constant time and the alphabet size is $n^{O(1)}$, then the DC3 algorithm runs in $O(n)$ time.

Notice that you can also get the suffix-tree in linear time when you have access to the suffix-array and the LCP-array. The LCP-array can be also constructed with the DC3-algorithm.


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

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

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

Descriptively

The standard convention is that

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

should really be interpreted as

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

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

By the same token, the standard convention is that

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

actually means

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

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

Or, in this case,

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

should be interpreted as

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

The same holds for $\Omega$, too.

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

Prescriptively

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


Algorithm to determine which vertices/edges would disconnect undirected graph if removed Is anyone aware of an algorithm to determine which vertices/edges would disconnect an undirected graph if removed? For all vertices/edges.

Of course I could run a BFS for each vertex and for each edge to test if the remaining graph would be connected. But is there anything more efficient?

In the end I would like to uniformly draw a vertex/edge out of those that would not disconnect the graph, to make simulations for fail-over routing in a computer network.

For vertices you could use articulation point algorithm that uses DFS and runs in $O(|V| + |E|)$ time. Similarly you could find bridges. Look here and here. But if there is no bridge and you are interested in cut-set (of edges) I guess you could use maximum flow minimum cut algorithm by assigning weight equal to 1 to each edge if they are not weighted. And finally if you are interested in subgraphs whose vertices are connected with each other (there is a path between each pair of vertices) then use an algorithm for computing strongly connected components.


Is there a relationship between "sound and complete" in logic and "type safety" in PLs? I've been wondering if there's a connection between "good logics" and "good programming languages". It seems that logics are shown to be "locally sound and complete" whereas programming languages are shown to be "type safe" (preservation and progress).

If there's a relationship could you please explain it and give some references so that I can follow up on it.

Soundness and completeness of logic are semantic notions which say that logic and its models fit together nicely. We can find similar theorems in the theory of programming languages but they are not necessarily about mathematical models of programming languages.
A general way to understand soundness is that "bad things do not happen" (logic does not prove invalid things). A general way to understand completeness is that "good things happen" (there are sufficiently many models).
A programming language typically has several kinds of semantics:

static semantics explains how to assign types to programs
dynamics (operational) semantics explains how to run programs, more or less
denotational semantics is more akin to models in logic and it explains how to map programs to mathematical objects.

There are theorems which relate these semantics. For instance:

Preservation: If a program p has type T and p evaluates to p' then p' has type T.

This is like soundness (bad things don't happen, namely a program will not become untyped). Another one is:

Progress: If a program p has type T then it is either a value (it's finished) or it has another step of execution.

This is like completeness (good things happen, namely a program will make the next step).
When we put these two together, we get safety.
Another kind of theorems relates denotational semantics to operational semantics. For instance:

Adequacy: if p and q are denoted by the same mathematical object then they are observationally equivalent.
Full abstraction: if p and q are observationally equivalent then they are denoted by the same mathematical object.

Adequacy says that the model is not too small and full abstraction that it is not too big. It makes a bit less sense to relate these two to soundness and completeness, but if I had to, I would say that full abstraction is like soundness and adequacy is like completeness.


Language Classification + AWS ML: what am I doing wrong? I'm evaluating Amazon's machine learning platform, and thought that I would give it a "simple" classification problem first.  As a disclaimer, I am quite new to machine learning (hence my interest in an ML platform).

The classification problem is language detection.  Given a list of 20k words, and their language (English, French, or Random), train a model to classify new words.

My data is structured in CSV format, with 2 rows:

dàagzj, random
tunisia, english
craindre, french
voters, english
religions, english
condition, french
...

I imported the data successfully into the platform, and all seems fine.

When I attempt to run train a model (using both the default settings and tweaking them) I get the same result.  English is selected as the language nearly 100% of the time.

I know this problem is possible to get reasonably accurate results with simple neural networks, however I'm not sure what is going wrong?

Do I need to perform any preprocessing operations on the text input, or is the plain string sufficient?  What data can be collected about a single word that may be a more effective input to a machine learning model?

There are probably multiple things wrong here.

Features

First, you don't tell us what features you have provided.  If the only input you have provided is the word itself (e.g., the string craindre), then most likely the machine learning algorithm has no idea how to use that information: all it knows is that this string is different from all the others you've provided, so it has no ability to generalize.

So, you need to derive some suitable features, to enable this to generalize.  For instance, maybe you'll have a feature vector of length $26^2=676$, one for each possible pair of letters, counting the number of times that pair of letters appears consecutively in the word.  Then, instead of asking the machine learning algorithm to predict the language from the word itself, ask it to predict the language from the feature vector.

You can certainly come up with much more sophisticated and effective features; this is just an example.  For instance, maybe you might have a feature that counts the fraction of letters that were vowels, or the fraction of letters that were consonants, or a feature that indicates what the last letter was, or a feature that indicates how many consecutive vowel-pairs the word had.  Basically, you want to pick features values that you think might be helpful at predicting the language or might tend to take different values for different languages.  If you want to build something that will be very accurate at predicting language, you'll probably need to get fairly sophisticated in designing features.  There's lots of research literature on language detection; you could try reading it to get some ideas for better features.  But if you just want to play around with this, my advice is to start with a small number of simple features.

Typically, machine learning algorithms are very smart about finding patterns in the feature vectors you provide -- but they don't do anything to automatically select features.  So, the division of labor is: you come up with the features; the ML algorithm looks for patterns that enable it to use those features to predict the answer.

Class imbalance

I suggest you read about "the class imbalance problem".  You have 3 classes (English, French, and random).  Your training set is imbalanced: you have twice as many examples with English as French/random.  In other words, you don't have an equal number of examples for each class.

This is not necessarily a problem, but in some cases it can be.  For instance, some machine learning algorithms behave poorly when the training set is imbalanced.  And every machine learning algorithm will work sub-optimally when the frequency of the classes in the training set doesn't match what you expect to see in practice.

In your case, it's probably not any of those complicated explanations; it's probably a much simpler reason.  Because you haven't given the ML algorithm any useful features, it basically has no information whatsoever that it can use to generalize or spot patterns.  In other words, it's trying to guess the language of a given word given no information about that word.  So what is the poor ML algorithm to do?  All it can do is guess based on the relative frequency of different languages.  In your case, your training set has told it that any given word is more likely to be English than to be French or random (about 2x as likely), so if you're forced to make a guess and pick one language, the smartest one to pick is 'English'.

In conclusion: it is no surprise that the ML algorithm is always outputting 'English', in your situation.

Once you add a suitable feature vector, if it still works poorly, you can read about the class imbalance problem and see whether it applies to you.


Complexity class NP and MA Is there any example of any natural problem which is known to be in MA, but not yet to known to be in NP?

I am aware that Graph Nonisomorphism (GNI) is known to be in AM which is considered a superset of MA. Can we construct a language (which may be non-natural) which is in MA, but not in NP?

The same hardness assumption that implies P=BPP also implies NP=MA (at least according to the complexity zoo).

Even if the hardness assumption is wrong, separating NP from MA would be a huge achievement, since it would imply that P is different from NP (as MA is in the polynomial hierarchy).


Big number of false positives in binary classification I am fine-tuning the inception-v3 network(pretrained on ILSVRC) of tensorflow in a binary classification problem. I want to recognize if an image contains food or not. My dataset is imbalanced, the non-food class contains 5 times more images than the food class. I read that in an imbalanced dataset, I should train the network with balanced batches to get right results. So I split the dominant class in 5 splits and when I have to train the network for 50000 iterations I am changing the split every 10000 iterations, so that the batches that are passed to the training are balanced with food and non-food. I am testing the network in a balanced test-set. From the first 5000 iterations I am getting high accuracy in the food images, but the non-food class gives me imbalanced accuracy. I can receive high accuracy in the beginning and then it will be low. By accuracy I mean (number of rightly predicted food) / (number of food) for the food class and respectively for the non-food. Generally the network learns the food characteristics because the softmax can output non-food for a food image, but the localization of food would be right using the weights of food (I made test). To sum up, the network is probably overfitted but I don't know yet. Any ideas of what might be happening?

It's hard to know, from just the information you've given us.  It could be any number of things: overfitting, insufficient training data, class imbalance, or something else.  The first step is probably to figure out the source of the problem, then you can explore the solutions.

There are standard diagnostics to check for overfitting (cross-validation, comparing accuracy on the validation set to accuracy on the training set, etc.). I'd suggest you use them to diagnose whether the network seems to be overfitting.  There are many ways to combat overfitting: regularization, early-stop training, dropout, etc.

There are also ways to check if the problem is that you just don't have enough training data.  For instance, you can take different-size subsets of your training set (10K, 20K, 30K, 40K, 50K) and plot how accuracy depends on the size of the training set.  If accuracy seems to be gradually improving as training set size increases and doesn't appear to have reached a plateau yet, that's a suggestion that obtaining more training data might be useful.

Finally, class imbalance might be a factor.  When you have 5 times as many non-food instances as food instances, that's call class imbalance.  There's lots written on that subject and many techniques (undersampling the minority class, oversampling the majority class, using class weights, adjusting the threshold for classification, and more).  I suggest you do some reading about that topic.  It's not necessarily true that you need to train on a training set with balanced classes; that's one strategy, but it's not the only one, and it may not be optimal.

Hopefully this will help you narrow down what might be going on and then ask a more focused question.


Minimum Clique Cover - Mixed Integer Programming I have a general (undirected) graph with a set of nodes, a set of edges, and a weight for each edge. I want to find a minimum clique cover of the vertices of the graph, that is, a partition of the graph into the smallest number of cliques. A clique is a set of nodes such that each pair of nodes is connected. I also want to maximize the sum of edge weights over the cliques. I want to use an integer programming approach for this problem.

Can any one give me some hints or some references that use mixed integer linear programming for the (maximum weight) minimum clique partition?

Thank you very much.

I think I have some suggestions.
You can make a binary variable $e_{ij}$ per edge corresponding to if those two vertices are in a clique together or not. Being in a clique is a transitive property. $e_{ij} \wedge e_{jk} = e_{ik}$. This "and" constraint is expressible as a MIP. This can be achieved with the constraint $e_{ik} <= e_{ij}$, $e_{ik} <= e_{jk}$, $
e_{ij} + e_{jk} - 1 <= e_{ik}$ link. This is the polytope generated by the truth table vertices (0,0,0) (0,1,0) (1,0,0) (1,1,1).  This makes only vertex clique covers feasible. For maximizing edge weights you're good to go.

I don't have an elegant way to minimize the total number of cliques. Just maximizing the sum of all edges is a reasonable heuristic if heuristics are acceptable.
Another possibility is to take the sum of all the edges coming out of a vertex. This is the size of the clique it belongs to and is bounded by the total number of edges connected to that vertex.
$\sum_j e_{ij} = c_i - 1$, where $c_i$ is the size of the clique vertex $i$ belongs to. The sum over all vertices $\sum_j \frac{1}{c_i} = C$ is the total number of cliques $C$.
I don't have a good way to perform this inversion, except by MIP brute force.

This can be done by generating as many binary variables $a_{in}$ per vertex as it has neighbors, setting $\sum_n n a_{ni}=c_i$, enforcing that only one $a_{ni}$ is nonzero $\sum_n a_{ni} = 1$, and then making the objective $\sum_{jn}\frac{1}{n}a_{nj}$. This is rather dissatisfying to me and I hope there is a better way.


What is a logical approach to developing an algorithm which can find the optimal parameters for a function which make it best fit a given data set? Consider the highlighted columns in the following table:

Starting with 100,000 newborns, $l_{x+2}$ denotes the number of individuals in the sample still alive at age $x+2$. If we consider Makeham's law of mortality, defined by the function
$$
S_0(x) = \exp \left( -Ax - \frac{Bc^x - 1}{\log (c)} \right)
$$
we find that for the correct parameters $A, B$ and $c$ this formula very closely models the actual number of deaths.

So my question is this, given a data set and a model with unknown parameters, what computational method may be used to approximate the optimal parameters for the model (which most closely fit the given data set)?

As a more simple example, suppose we are given the data set
$$
X = \left\{ 1, 3, 5.1, 7, 9 \right\}
$$
and are required to find the optimal parameters $A$ and $B$ such that the model
$$
f(x) = Ax + B
$$
most closely fits this data set. As humans, it is clear to see that the optimal parameters are $A = 2$ and $B = 1$. How might a computer deduce these values?

The answer depends on what is your notion of "optimal parameters", and on the specific model you have in mind.

Suppose your model is $f(x,\overline{p})$, where $p$ is the parameters vector, and you wish to find the vector $\overline{p}$ which minimizes $
\sum\limits_{i=1}^n\left( y_i-f(x_i,\overline{p})\right)^2$. This problem is known as least squares fitting, and if your model $f(x,\overline{p})$ is linear, then the optimal value of $\overline{p}$ is given by ${(x^Tx)^{-1}x^Ty}$. For more complicated models, the solution might not be so easy to find analytically, and one might need to settle for approximations. One option is to use iterative methods, such as the Gauss-Newton algorithm.

There is no general way to deal with any type of error function. If for example your cost function does not allow any mistake, and your model $f$ is polynomial in the parameters, then the task reduces to solving a system of polynomial equations. Different types of error functions can take you to different areas in optimization, or even in mathematics in general.


What are lattices used for? Wikipedia says:

  Complete lattices appear in many applications in mathematics and computer science

Is it just referring to the fact that the standard Boolean algebra used in computation is a complete lattice? Is there anything we gain by working at the abstract level of lattices instead of with Boolean logic specifically?

A google search doesn't find much on the subject, but I'm probably using the wrong keywords.

See for instance this book: Lattice Theory with Applications, Vijay K. Garg, which starts off as follows:

  Partial order and lattice theory now play an important role in many disciplines of computer science
  and engineering. For example, they have applications in distributed computing (vector clocks,
  global predicate detection), concurrency theory (pomsets, occurrence nets), programming language
  semantics (fixed-point semantics), and data mining (concept analysis). They are also useful in other
  disciplines of mathematics such as combinatorics, number theory and group theory. In this book,
  I introduce important results in partial order theory along with their applications in computer
  science. The bias of the book is on computational aspects of lattice theory (algorithms) and on applications (esp. distributed systems).

The book doesn't seem to mention recursion theory (theory of computable sets), but from Wikipedia's article on Computability theory, we see:

  When Post defined the notion of a simple set as an r.e. set with an infinite complement not containing any infinite r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. This lattice became a well-studied structure. Recursive sets can be defined in this structure by the basic result that a set is recursive if and only if the set and its complement are both recursively enumerable. Infinite r.e. sets have always infinite recursive subsets; but on the other hand, simple sets exist but do not have a coinfinite recursive superset. Post (1944) introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are r.e. sets such that every r.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the recursive sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; Harrington and Soare (1991) found eventually such a property.

Further reading, see the blog post Lattice Theory for Programmers and Non Computer Scientists.


guillotine cuts versus general cuts Cutting problems are problems where a certain large object should be cut to several small objects. For example, imagine you have a factory that works with large sheets of raw glass, of width $W$ and length $L$. There are several buyers, each of which wants an unbounded number of small glass sheets. Buyer $i$ wants sheets of length $l_i$ and width $w_i$. Your goal is to cut small sheets from the large one, such that the total used is maximized and the waste is minimized (there are also other types of cutting and packing problems).

One common restriction in cutting problems is that the cuts must be guillotine cuts, i.e., each existing rectangle can be cut only to two smaller rectangles; it is impossible to make L-shapes etc. Obviously, the maximum used area with guillotine cuts might be smaller than the maximum used area without restriction.

My question is: Are there upper and lower bounds on the ratio between the optimal guillotine cut and the optimal general cut?

Related work: Song et al. (2009) describe an algorithm that uses a restricted type of guillotine cuts – twice-guillotine cuts. They prove, using geometric constraints, that the ratio between the maximum twice-guillotine cut to the maximum guillotine cut is bounded by $\frac{6}{7}$. I am looking for a comparable result about the ratio between the maximum guillotine cut to the maximum general cut.

Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts.

Let us start with the upper bound and assume we are given a square piece of glass with a side length of $2$. Furthermore, we have exactly one buyer who is interested in rectangular glass sheets of width $1-\varepsilon$ and length $1+\varepsilon$. Using general cuts, the optimal solution looks something like the following picture, with four of the desired rectangles placed around a little square of side length $\varepsilon$ in the middle.

It is easy to see that this cutting pattern can not be achieved via guillotine cuts. In fact, any cutting pattern using guillotine cuts can fit at most 3 of the desired rectangles into the original square. As a result, the worst ratio between guillotine cuts and general cuts is at least $3/4$.

Next, we have a look at the lower bound. Let $W$ and $L$ be the side lengths of the original sheet of glass. Without loss of generality, we can assume that there exists a buyer $i$ such that $w_i \leq W$ and $l_i \leq L$. Otherwise, the original sheet would be unusable, no matter if we use guillotine cuts or general cuts.  However, using guillotine cuts, we can always cut out at least one quarter of the original sheet by simply aligning the rectangles desired by buyer $i$, as shown in the following picture.

Notice that the red rectangle corresponds to one quarter of the whole sheet and is completely covered by the gray rectangles buyer $i$ desires. On the other hand, even if we use general cuts, we cannot use more than the whole sheet, which gives us a lower bound of $1/4$.

I am aware that the lower bound is quite weak and it can probably be improved with a bit more work. But it is a start.


What are the concequences of the unit type and the unit value being the same? What are the practical and theoretical implications of the unit type and the unit value being the same or different entities?

For example, in Haskell the unit type and unit value are both spelled (). In ML, the unit type is spelled unit and it's value is ().

Are there any problems that arise from either option? Are there any significant benefits perhaps to the soundness of the type-system or the ability to reason about programs?

You have been confused by Haskell's notation. The unit type and unit value are of course different, and it just happens that Haskell uses the same notation for both.

As for the consequences: there are none. Notation is irrelevant here. You can call the unit type Dog or BauwnNuYwvb (i.e., nonsense), and it won't change the type system.


Convert scientific notation decimal number to binary I'm given the number:
$$8.881784197001252 \cdot 10^{-16}$$
I know it is $2^{-50}$ but suppose I didn't know. I need to convert it to binary.

One way is to apply the school taught algorithm on the fractional part. That'd be:

$.881784197001252\cdot2=1.763568394 \to 1$

$.763568394 \cdot 2=1.527136788 \to 1$

$.527136788 \cdot 2=1.054273576 \to 1$

$.054273576 \cdot 2= 0.108547152 \to 0$

$.108547152 \cdot 2=0.217094304 \to 0$

$...$

It may go on forever so I'd need to determine when to stop.

I then thought I could write the number as:
$$8881784197001252 \cdot 10^{-31}$$
Now the number is an integer and I can precisely convert it. It's:
$$11111100011011110111110001000000010001011000000100100$$
The problem is that I don't know how to convert the base and its exponent from base 10 to base 2. I can approximate it after some attempts. It should be between $2^{-100}$ and $2^{-99}$.

So what I'm asking is: what is the correct approach to convert that number? And, if different from the former, what method does the computer use?

There is more than one correct approach to convert the number.  The former is a correct algorithm for the problem.  This kind of base conversion would usually be implemented in a library for the programming language you are using.  There might be many such implementations out there, and I don't know what all of them are doing.

I would not recommend the latter approach, as I expect computing $2^\alpha$ where $\alpha=31 \log_2 10$ will be painful.

See also The math behind converting from any base to any base without going through base 10? and https://math.stackexchange.com/q/48968/14578 and https://en.wikipedia.org/wiki/Positional_notation#Base_conversion and https://en.wikipedia.org/wiki/Binary_number#Conversion_to_and_from_other_numeral_systems.


Rank of root in AVL tree Find a function that bounds from above and below (asymptotic) the rank of the root r in an AVL tree,
i.e. find a function $f(n)$ so there exists a constant $c>0$ that for every AVL tree with $n$ nodes so
$c * f(n)\le rank(r)\le n-c*f(n) $.

$rank(r)$ gets his maximum value when his sub-left tree contains maximal number of nodes and because it's an AVL tree, for tree with height $h$ the sub left tree will be with height of $h-1$ and the number of nodes will be maximal when the sub tree is a full tree with $2^{h-2}-1$ nodes hence we get:
$rank(r)\leq 2^{h-2}-1+1=2^{h-2}$

On the other hand, $rank(r)$ gets his minimal value when his sub left tree contains a minimal number of nodes and it happens when the sub left tree is a fibonacci tree with height of $h-2$, therefore
  $rank(r) \geq \phi ^{h-2}+1$.

Now I need to find f as a function of the number of nodes $n$ and not the height $h$.
Am I in the right direction?
  Would apricciate any help how to continue, Thanks.

First of all, it's not $2^{h-2}$, it's $2^h$.

The number of nodes $n$ in a full binary tree, is at most $n=2^{h+1}-1$, where $h$ is the height of the tree. A tree consisting of only a root node has a height of 0.

Straight outta wiki https://en.wikipedia.org/wiki/AVL_tree


Responsive input sliders - is there a better way? I am building an app where a user controls inputs via multiple sliders each with discrete steps. The app then uses the combination of slider values to run some calculations and returns back an output value.

The sliders are meant to be highly responsive, so the user can immediately see the impact of their input combination on the output value -so I have resorted to eagerly calculating ALL possible combinations of sliders and letting the client query the results in the browser itself for faster response times.

The problem is that the number of possible combinations can seriously explode. If I have 6 inputs each with 10 steps, that is 10^6 = a million possible combinations! That's way too expensive to calculate eagerly.

Is there a better way to do this? I could try to restrict the number of sliders that can be moved at any point, to lower the solution space...but wondering if there's a better solution out there.

I like John L's suggestion.  Have the app compute the view for the current position of all sliders.  Also, for each of the 6 other sliders, for each other 9 positions of that slider, precompute the view obtained from that.  In other words, you precompute all views that can be obtained by changing the position of a single slider.  That involves precomputing 6*9 = 54 other views.  Now, when the user clicks on a slider and changes its position, you'll be able to immediately display that view, and you can start precomputing 54 more views (for all combinations of changing one other slider to a different position).  As long as you can compute 54 views in the it takes for a user to move their mouse from one slider to another, you'll be able to keep up in a responsive way.


Best random permutation employing only one random number The ideal random permutation algorithm of Fisher and Yates (Algorithm P in Knuth vol.2) for a sequence of $n$ objects requires $n-1$ random numbers.

In some card games one first does a "cut" and then a riffle shuffle. The cutting point is a random value, the subsequent shuffling could be considered as deterministic. That is, only one random number is being used to generate the permutation, which understandably can't be ideal. On the other hand, theoretical perfection isn't always necessary in practice. I like hence to know whether, if one keeps the constraint of using one random number in a run, the quality of randomness of the permutation obtained couldn't eventually be improved through certain appropriate modifications of the procedure commonly employed in card games, if one is willing to take the trade-off of more work/time, inconvenience, etc. Such trade-offs may not be acceptable for real games, but I suppose there may be other practical applications that could advantageously exploit the same idea, thus without being required to acquire, e.g. via a chosen PRNG, the larger number of random numbers needed for executing the algorithm of Fisher and Yates.

Regardless of the algorithm you use, if you have $i$ bits of random data, you can generate a maximum of $2^i$ possible permutations. If $i$ is smaller than $log_2(n!)$, then there will be some permutations which cannot be produced, and you will have, in effect, decided which permutations those are when you encode your algorithm. (You may not be able to predict which permutations they are, but you have nonetheless determined that fact.) [1]

$log_2{52!}$ is about 225.6, so with a single 64-bit random number, you can only generate one out of every 4372488437452686306097090522819848184377442426979 permutations. With four 64-bit random numbers, you'd have no trouble generating all of them. $log_2{64!}$ is just under 296, so it would require five 64-bit numbers.

Since your permutation-generator is deterministic, you cannot invent more possibilities by manipulating the algorithm. The best you can do is to ensure that it is a homomorphism; that every random number is mapped onto a different permutation. Beyond that, you could investigate whether the one-in-4372488437452686306097090522819848184377442426979 sample of the universe of permutations exhibits any biases. For example, is each individual permutation position in the same evenly distributed? Is there a correlation between two (or more) positions? I sincerely doubt that trying to emulate a physical shuffle will improve these statistics more than the simple mathematical approach outlined below.

As xkcd reminds us, there is no such thing as an intrinsically random value. The only meaningful question we can answer is whether a sequence of pseudorandomly generated values is "random-like".

So let's first figure out how to transform the $i$ bits of randomness into $2^i$ distinct permutations. The following generic procedure should work:

Predefine some function $f$ which maps $[0, 2^i)$ onto $[0, n!)$.
For each permutation, given a random number $x$, compute ${q_0,...,q_{n-1}}$ and
${r_0,...,r_{n-1}}$ as follows:

$q_0 = f(x)$
$r_i = q_i \mod (n-i)$
$q_{i+1} = {{q_i - r_i}\over{n - i}}$

Perform a Fisher-Yates shuffle using ${r_0,...,r_{n-1}}$ as the "random numbers".

(Aside from expanding the initial seed into the range $[0,n!)$, this is precisely the solution proposed by Yuval, just written out in more detail.)

Then you could start to measure the "randomness" of a proposed function $f$ by measuring the distribution of the values of each $r_i$ over the range of $f$. The next step might be to look at the distribution of $<r_i, r_j>$ for each pair $0 <= i < j < n$

One really simple definition of $f$ is:

$$f(x)=\lfloor x * {n!\over2^i} \rfloor$$

Assuming you calculate this with precise rational arithmetic, this gives a surprisingly reasonable set of individual $r_i$ distributions for a 52-shuffle given a 64-bit random number. [2] You'll have to decide whether that's good enough for you. If it turns out to not be, there are other possible transformations which might do better. Another simple one would be replacing the above with:

$$f(x)=\lfloor x * {n!\over2^i} \rfloor + p \mod n!$$

where $p$ is some large prime.

[1] This information-theoretic argument is based on the permutation-generation algorithm being stateless. If each random number is in some way combined with all previously generated random numbers without losing (too much) information, then the universe of possible permutations could be much larger. (This condition is not satisfied by simply combining the two random numbers with some arithmetic or bitwise operation whose value has the same number of bits as each of the arguments.) I think that's a reasonable assumption because the original question was cast in the context of a client-server architecture; in such systems maintaining co-ordinated state between the disconnect components is generally more complicated than exchanging a few more bits in each transaction.

[2] I didn't do much more than look at some histograms and a couple of correlations and a chi-square or two, but it was all really simple python, so I'm sure you could reproduce my limited research in a few minutes.


Why do programming languages use call-by-value over call-by-name? I am reading Software Engineering 1: Abstraction and Modelling by Dines Bjørner. One of the chapters talks a little bit about call-by-value vs call-by-name. In it, the author states that most programming languages use call-by-value, rather than call-by-name. But from what I have read in the chapter, it seems that call-by-name is a much safer method of calling functions.
For example, say we have a function like f(x, y) = y * 3, and we call it somewhere like f(infinteLoop(), 6), where infinteLoop() is some function which never terminates. If we use call-by-name, we never have to call infiniteLoop() because x is never used in the body of f. But if we use call-by-value, we need to evaluate infinteLoop(), even though it will never be used in the body of f. This will cause the program not to terminate, of course.
It seems to me that call-by-name is both safer and more efficient (since we do not need to evaluate unused expressions). So for what reason do most (or any for that matter) programming languages use call-by-value instead of call-by-name?

There's a couple of factors which come into place. There can be performance costs to call-by-name, as well as difficulty with understandability in the presence of effects.
First of all, call-by-name can use exponentially more time than call-by-value, since it may have to evaluate an expression multiple times. Imagine calling f(x) = x + x when x takes a while to compute. In true call-by-name, the entire expression for x needs to be evaluated twice inside the body of f.
So in practice, instead of call-by-name, we likely would prefer call-by-need. We can instead cache the result of evaluating x, so that we don't have to compute it multiple times. This is what the programming language Haskell does (preceded by Miranda, Lazy ML). This solves the time complexity problem (as you may have intuited above, the time complexity is no worse than call-by-value), but it can also use much more space. This is because it may need large closures in order to delay evaluation. A machine integer uses a finite amount of space, but a Haskell Int could use arbitrarily large amounts, by accumulating a closure of computation that needs to be run. In the Glasgow Haskell Compiler, the garbage collector has special rules to specifically find and eliminate certain kinds of "space leaks" where we use excessive space via closures.
Even putting the theoretical aside, there are practical difficulties for implementing a call-by-name or call-by-need language on a traditional machine. Many programmers are used to using side effects in their program, such as input and output, and having their expressions run sequentially. In a call-by-name programming language, this is no longer the case, effects could be latent anywhere within an unevaluated expression, and only take effect when that data is examined. It took many years for the discovery that mathematical monads could be used as a sequencing interface. Prior methods for controlling input/output were difficult to use.
Call-by-value languages tend to also be able to be performant much more easily than call-by-name/call-by-need. Haskell has taken extensive optimization effort to run quickly, largely by being able to carefully introduce strictness to eliminate overhead of laziness. With laziness, a value of any type could be a closure: a complex allocated object and a pointer to remote code to run. This can require more allocations and more indirection to manipulate than machine integers and simple objects.
So, while we can't answer definitively why such languages aren't more popular, we can see that there has been plenty of complexity and research necessary to tackle, and so languages which used call-by-value have long had a head start.


Efficient algorithm for sorting objects by key that values are range from 0 to 100 Can you help me with sorting algorithm implementation for objects of Student type by rating field. This field (rating) value can be any number from 0 to 100. Can I do the sort in-place?

Let $A[0 \dots, n-1]$ be the elements to be sorted.
A possible strategy that requires $O(n)$ time and $O(1)$ additional memory is:

count, for each possible key $k$, the number of elements in $A$ with key $k$, in $O(n)$ time;
for each $k$ compute the intervals of indices of $A$ in which elements with key $k$ must lie (in $O(1)$ time);
Scan the input array a place each element in the correct interval. This can be done by swapping the considered element with any element that was already in that interval, taking care to not swap that element back.

A possible implementation is the following:

Initialize an array $C[0, \dots, 100]$. Initially all entries of $C$ are $0$.
For each $i=0, \dots, n-1$: increment $C[k]$ where $k$ is the key of $A[i]$.
For $k=0, \dots, 101$, let $P[k]=\sum_{j=0}^{k-1} C[j]$; At this point we know that an element with key $k$ needs to end up in some $A[i]$ with $P[k] \le i < P[k+1]$. Notice that, for $k>0$, $P[k] = P[k-1] + C[k-1]$.
Let $i=0$.
While $i<n$:

Let $k$ be the key of $A[i]$.
If $i \not\in [P[k], P[k+1])$

Decrement $C[k]$
Swap $A[i]$ with $A[P[k]+C[k]]$

Else

Increment $i$


Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a formula $\varphi$ with at most $O(n)$ clauses within time at most $p(n)$ for some polynomial $p(n)$?

Since Cook Levin Theorem shows a reduction that proves 3SAT is NPC, almost all of the literature deals only with reductions from 3SAT, and only rarely one can find in the literature reductions to 3SAT.

After searching the web I found this and other cites that have the other direction of reduction (from 3SAT to dHamPath).

Referring to some source would be highly appreciated.

I don't know of a reference, but there's a standard reduction from Hamiltonian paths/cycles to SAT which is fairly well-known. The reduction from SAT to 3SAT is then done by introducing additional variables to break up clauses, e.g.:

$$v_1 \vee \neg v_2 \vee v_3 \vee \neg v_4 \Rightarrow \left( v_1 \vee \neg v_2 \vee X\right) \wedge \left( v_3 \vee \neg v_4 \vee  \neg X\right)$$

Let $n$ be the number of nodes in the graph. Then define variables $x_{i,j}$ where $i,j \in \left\{1 \ldots n\right\}$, where $x_{i,j}$ is true if node $i$ appears in position $j$ in the Hamiltonian path.

Every node must appear somewhere on the path:

$$\bigwedge_{i} \left( \bigvee_{j} x_{i,j}\right)$$

Every position in the path must be occupied:

$$\bigwedge_{i} \left( \bigvee_{j} x_{j,i}\right)$$

No node appears on the path more than once:

$$\bigwedge_{i} \bigwedge_{j \ne k} \left( \neg x_{i,j} \vee \neg x_{i,k} \right)$$

No two distinct nodes occupy the same position:

$$\bigwedge_{i} \bigwedge_{j \ne k} \left( \neg x_{j,i} \vee \neg x_{k,i} \right)$$

Nonadjacent nodes cannot be adjacent on the path. If $E \subseteq N \times N$ is the set of edges:

$$\bigwedge_{k \ne \left|N\right|}\bigwedge_{(i,j) \not\in E} \left( \neg x_{k,i} \vee \neg x_{k+1,j}\right)$$

You can modify this in the obvious way if you're trying to find a Hamiltonian cycle.

On that, as a practical matter, if you are trying to find a Hamiltonian cycle and you intend to feed this to a SAT solver, you would normally assert a start node as another clause, e.g. $x_{1,1}$, to reduce the search space. Obviously for Hamiltonian paths, you don't do that.


What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element? Consider the recursive quick sort with random pivoting i.e. each time a random pivot element is chosen uniformly. When this randomized algorithm is being applied to an array with n distinct element, what is the probability that the smallest and the greatest element will be compared during run of the algorithm.

It is $2/N$ : the probability of picking the smallest or the biggest as pivot.
If you choose one of them, they will be compared.
If you choose any other, then the smallest and the biggest elements will be put in different partitions, and thus will not be compared.


How does a nondeterministic Turing machine work? What is differences between deterministic and nondeterministic Turing machines? Different but equivalent models of NDTM. In particular, what is this frequently used phrase "nondeterministically guess"? How to use it right, and examples of wrong usage. My goal is to create a reference question.

Here are several ways of thinking about non-determinism (copied from this answer).

The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the machine to do, it will always reject.

Hints. The machine computes a bivariate function. The first input is a word $w$, and the second input is a "hint" $x$. Whenever the machine faces a non-deterministic choice, it consults the next hint symbol, and operates accordingly. We are promised the following:

Completeness: if $w \in L$ then there is some hint $x$ which causes the machine to accept.
Soundness: if $w \notin L$ then the machine rejects on all hints.

Accepting computations. An accepting computation is a legal computation (one in which the machine always operates according to one of the choices it is faced with) which ends at an accepting state. A word is in the language iff it has an accepting computation.

We can formalize the notion of accepting computation using configurations. A configuration is an instantaneous description of the entire state of the machine. We can define a relation $\sigma \vdash \sigma'$, where $\sigma,\sigma'$ are configurations, which holds when $\sigma$ can lead to $\sigma'$ in one step. In a deterministic machine, there is at most one $\sigma'$ per each $\sigma$, whereas in a nondeterministic machine, there could be more than one. An accepting computation for a word $w$ is one which starts at the initial configuration (the tape contains $w$, the head points at the start of $w$, the state is the initial state) and ends at an accepting configuration.

Another equivalent description is in terms of reachability. Consider a directed graph in which vertices are configurations and there is an edge from $\sigma$ to $\sigma'$ if $\sigma \vdash \sigma'$. An accepting computation is a path from the initial configuration to an accepting configuration.


Closure of a CFL under specific operation Consider the following operation on language $L$:
$\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$
I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and proved it by guesing when $y^R$ starts and running it on the inverse DFA. However, if $L$ is a CFL, then $\mathrm{inv}(L)$ is not, and I don't understand why. Can't we just also guess when $y^R$ starts, insert all of it into the stack, then simulate the DFA of $L$ on each item we take out, then continue on $z$ when it's empty?
thanks.

You are right, regular languages are closed under inversion $\mathrm{inv}$, using some proper guesses, or see my answer to a relevant question here.

Context-free languages are not closed under $\mathrm{inv}$. Your intuition does not work. We cannot push $y$ on the stack because it will make the 'real' stack below it inaccessible for the simulation.

Here is a possible counter example. Consider $L = \{ a^nb^nc^md^m \mid m,n\ge 1 \}$. Then try $\mathrm{inv}(L) \cap a^*c^*b^*d^* $.


Complexity guess and induction proof I was trying to prove by induction that
$$
T(n) =      \begin{cases}
       1 &\quad\text{if } n\leq 1\\
       T\left(\lfloor\frac{n}{2}\rfloor\right) + n &\quad\text{if } n\gt1 \\
     \end{cases}
$$
is $\Omega(n)$ implying that $\exists c>0, \exists m\geq 0\,\,|\,\,T(n) \geq cn \,\,\forall n\geq m$

Base case : $T(1) \geq c1 \implies c \leq 1$

Now we shall assume that $T(k) = \Omega(k) \implies T(k) \geq ck \,\,\forall k < n$ and prove that $T(n) = \Omega(n)$.
$$
T(n) = T(\lfloor{\frac{n}{2}}\rfloor) + n \geq c\lfloor{\frac{n}{2}}\rfloor + n \geq c \frac{n}{2} -1 + n \geq n\left(\frac{c}{2} - \frac{1}{n} + 1\right) \geq^{?} cn\\
c \leq 2 - \frac{2}{n}
$$
So we have proved that $T(n) \geq c n$ in :

1) The base case for $c \leq 1$

2) The inductive step for $c \leq 2 - \frac{2}{n}$

Yet we have to find a value that satisfies them both for all $n\geq 1$, the book suggest such value is $c = 1$ which to me is not true since :

$$
1 \leq 1\\1\leq2 - \frac{2}{n}\implies 1 \leq 0 \text{  for n = 1}
$$
My guess would be $0$ but is not an acceptable value; So we just say its $\Omega(n)$ but for $n \gt 1$?Or how can we deal with it?

You're overthinking. $T(\lfloor\frac{n}{2})\rfloor \ge 1 \Rightarrow T(n) = T(\lfloor\frac{n}{2})\rfloor + n > n \Rightarrow T(n) = \Omega(n)$


How to count all integers less than a given integer and having two contigous digits as $y$? Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits but xxx11 < 54432 should hold.

What is count of all the numbers of form x11xx and x11xx < 54432 ?

How to solve this in general and fast way i.e any number other than 1 , say y and arbitrary position of two contiguous digits as y and count of all such numbers less than a given integer.

can we solve this problem using strings ?

Like for 54411 , total count is 545 . Just remove 11 part and add 1.
for 54112 ,total count is 543 , just remove 11 part .

So say you want to count all numbers of the form $x_1\cdot ab\cdot x_2$ less than $n$, where $x_1$ and $x_2$ are numbers with a fixed number of digits, and $ab$ are two contiguous digits.

Cut $n$ in the same positions as your $x_1\cdot ab \cdot x_2$ pattern to get $n_1\cdot pq\cdot n_2$.

Now when is $x_1\cdot ab\cdot x_2 < n_1\cdot pq\cdot n_2$?

Either $x_1 < n_1$, then any choice for $x_2$ goes. I.e., $10^{\text{number-of-digits}(x_2)}$ choices for $x_2$ whenever $x_1<n_1$. In total you get $n_1\times10^{\text{number-of-digits}(x_2)}$ choices for this case, or $(n_1-10^{\text{number-of-digits}(x_1)-1})\times10^{\text{number-of-digits}(x_2)}$ choices if you don't allow for leading zeros.
Or $x_1=n_1$, in which case it depends on $ab$ and $pq$.

If $ab<pq$ then any choice for $x_2$ goes, so you get an additional $10^{\text{number-of-digits}(x_2)}$ choices.
If $ab=pq$ then you have to have $x_2<n_2$ which gives you an additional $n_2$ choices.
If $ab>pq$ then no choice of $x_2$ will work.

In short, with leading zeros allowed:

If $ab<pq$ :
$$n_1\times10^{\text{number-of-digits}(x_2)} + 10^{\text{number-of-digits}(x_2)}$$
If $ab=pq$ :
$$n_1\times10^{\text{number-of-digits}(x_2)} + n_2$$
If $ab>pq$ :
$$n_1\times10^{\text{number-of-digits}(x_2)}$$

For example with $x11xx$ and $54432$ you get:
$$5\times 10^2 + 10^2 = 600$$


Efficient computation of traces of all primitive elements in field extensions of GF(2) Let $n > 1$ and let $\mathbb{F}_{2^n}$ be the finite field with $2^n$ elements. The trace function $T(x) = x + x^2 + x^{2^2} + \cdots + x^{2^{n-1}}$ is an onto linear transformation from $\mathbb{F}_{2^n}$ to $\mathbb{F}_2$. There are $\phi(2^n-1)$ primitive elements in $\mathbb{F}_{2^n}$ (generators of the cyclic multiplicative subgroup of the field) where $\phi$ is  Euler's totient function.

I am interested in computing the traces of all the primitive elements in $\mathbb{F}_{2^n}$ efficiently. Note that all the primitive elements are given by $\alpha^k$ where $\alpha$ is one of the primitive elements, and $\gcd(k, 2^n-1) = 1$. Moreover two primitive elements $\alpha^k$, $\alpha^s$ have the same trace if and only if $k \equiv s\cdot 2^i \pmod{2^n-1}$ for some $i$ with $0 \leq i \leq n-1$. This means we need to compute $\phi(2^n-1)/n$ traces.

Is there an efficient algorithm to do this?

It's straightforward to solve this problem in time $\phi(2^n-1)$ field operations, and there's no hope to do significantly better than this.

Computing the trace of a single element can be done in $n$ field operations (just by applying the definition).  So, we can simply compute the trace for each of the $\phi(2^n-1)/n$ elements with distinct trace.  The running time will be $n \times \phi(2^n-1)/n = \phi(2^n-1)$.

There is no hope to do significantly better than this.  There are $\phi(2^n-1)$ primitive elements in the field.  If you want an algorithm to output the trace of all of those values, the length of the output from the algorithm has to be at least $\phi(2^n-1)$.  It follows that the running time of any such algorithm has to be at least $\Theta(\phi(2^n-1))$.  So, you can't do asymptotically better than the straightforward algorithm.

Finally let me point out that $\phi(2^n-1)$ is exponentially large in $n$ (in general).  This means that any algorithm for your problem will have running time that is exponential in $n$.  This means that no algorithm can possibly be efficient for anything except very small values of $n$.


That algorithm doesn't do any pivoting. It requires non-zero elements on the diagonal of A to work, otherwise you divide by zero. Note the check:

if (L[j][j] == 0) {
    printf("det(L) close to 0!\n Can't divide by 0...\n");
    exit(EXIT_FAILURE);
}


Revolutions in Computer Science TL;DR

What revolutions have there been in computer science, which entirely changed our view about the subject, due to 'one way of thinking' being replaced by 'a new (incompatible) way of thinking' (such as Einsteinian physics replacing Newtonian physics).

To explain a bit further:

I was trying to think about revolutions in computer science, and which one there have been.
To clarify on what I mean by scientific revolutions:

  "Those non-cumulative developmental episodes in which an older
  paradigm is replaced on whole or part by an incompatible new one"
  (Kuhn, 1970 p.92)

To give perhaps the most famous example. Einstein's theories of relativity have shown that Newtonian physics is incorrect (it makes metaphysical assumptions, which turned out to be wrong). The paradigm in which General Relativity operates is incompatible with the Newtonian mechanics. Which then led to the reconstruction of science (Vienna circle).

A friend of mine (I believe correctly) pointed out that Quantum Computing could be one such revolution in computer science. But it has not actually happened yet.

As a software engineer myself, every time I thought of something that I'd consider a revolution, I became unsure if it really was a revolution as the 'paradigms' (methodologies) are not actually replaced and often even compatible with older ways of doing things. And some are pure technological advances (Functional programming after OO, or OO after procedural). Perhaps the application of Lambda Calculus in computer science (programming languages, type theory, ..?)

(Sure VCS was kind of a technological revolution, so if possible, let's keep the answers in computer science theory and not the applications in software engineering)

PS: I could not really find a suitable tag :-(

Computer science is, at its core, the study of algorithms. What can we compute, and how fast can we compute it? Its sub-fields, such as image processing, AI, Operating Systems, Programming Languages, numerical computing, etc. can be viewed as answering these questions for specific types of problems.

With that in mind, I think the most major revolution is:

Godel/Turing and Undecidability

The mathematician Hilbert posed a series of problems to the mathematical community. One was to find an algorithm for the Decision problem: that is, to look at any theorem, and state whether it was true or false.

In different ways, Godel and Turing each proved that this was impossible. This revolutionized the way we thought about computation, because for the first time, we had a definitive proof that something could not be computed. No amount of human cleverness could completely solve the problem.

Directly related to this, Turing Machines and the Church-Turing thesis were developed. This formalized what it meant to compute, turned algorithms from things humans talked about into mathematical objects that could be reasoned about, have theorems proved about them. And it established that the two extreme ways of thinking of computation, namely as functions and as transformation of an infinite memory, were equivalent.


Term clarification: Establishing a domination In the book "Approximation Algorithms" by Vazirani (legally available online), part of the hint to Exercise 9.6 (on page 77 of the book, page 95 of the PDF) says "Establish a domination". I've never heard this terminology before in the context of computer science/approximation algorithms/bin packing (I'm not so sure what the correct context is).

Perhaps someone here has familiarity with this terminology. If so, I'd love to hear the definition of "Domination" in this context.

We say that $A$ dominates $B$ if $A \geq B$ (or, more generally, if $A \succeq B$ in some partial order). To establish a domination means to establish that something dominates something else. I'll let you figure out which domination is meant in your context.


Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete How to show that the shortest simple path problem between two vertices $s$ and $t$ (finding a minimum weight path between $s$ and $t$) in a graph is NP-complete? I saw the following proof in a combinatorial optimization lecture, which I didn't understood (I stressed the moment that I didn't understand).
Let $P_1$ be the Hamiltonian path problem:

The Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. From Wikipedia.

Does it exists an Hamiltonian path in $G$?
Let $P_2$ be the shortest path problem in a directed graph.
If $G$ is the graph within which we search such a Hamiltonian path, we transform $G$ into $\hat G$, replacing each edge $(i,j)$ with two edges $(i,j)$ and $(j,i)$.
For each edge $\{i,j\}$ in $G$, we erase $(i,j)$ and $(j,i)$ from $\hat{G}$, give a weight of $-1$ to all remaining edges, and calculate the shortest (simple) path from $i$ to $j$. If the path length is $-(n-1)$, then this is a Hamiltonian path in $G$. If we found no such path going over all edges, then $G$ has no Hamiltonian path.

Why is is the case that if the path has length $-(n-1)$ then it constitutes a Hamiltonian path in $G$?
Why if not such path has length $-(n-1)$ then $G$ has no Hamiltonian path?

Maybe if you were kind to help me understand with a visual example I would better understand?
Last but not least, how did we proves that Hamiltonian path is NP-complete?

In fact, it does not prove NP-completeness (see a list of our related reference questions).

For the shortest path problem (SPP)  to be NP-complete, it is crucial you allow negative edge weights. Then, there is a simple polynomial-time reduction from the Hamiltonian path problem to SPP. In other words, you take an arbitrary instance $I$ of the Hamiltonian path problem, and construct an instance $I'$ of SPP such that $I$ has a solution if and only if $I'$ has a solution. To make the reduction work, you only need to set up the edge weights in $I'$ suitably.


Minimum number of edges to add such that there are no bridges on a tree Any edge of a tree is a bridge. What is the minimum number of edges that I will need to add so that there are no more bridges in a tree? I have seen the solution from the internet the answer is $\frac{|V|}{2}$, where $|V|$ is the number of vertices in the tree. How can I prove it?

Let me describe the following algorithm. The basic idea is to add edges such that for any pair of vertices $v_i$ and $v_j$ there is at least two different simple paths between $v_i$ and $v_j$.

Initially all edges are unmarked
Select a simple path $v_i\dots v_j$ containing at least two unmarked edges such as $(v_i,v_j) \notin E$ (vertices $v_i$ and $v_j$ are not connected). If there is no path containing two unmarked edges, then select a path containing one unmarked edge (this means we are done)
Connect $v_i$ and $v_j$ (thereby creating a cycle).
Mark all edges of the (newly created) cycle $v_i\dots v_j$
If there is unmarked edge then go to step 2
Halt

Claim 1: The algorithm adds at most $\frac{|V|}{2}$ edges.
Proof: At step 2 we select a path whose length is at least $2$ (i.e. has at least two edges) containing at least two unmarked edges. Such path exists as long as we have two unmarked edges since there is always a simple path between any two vertices $v_i$ and $v_j$ in a connected tree. So, at each step 2 we decrease the number of unmarked edges by $2$. Since the tree initially has $|V|-1$ unmarked edges, the algorithm adds at most $\big\lceil{\frac{|V|-1}{2}}\big\rceil$ edges. But $\big\lceil{\frac{|V|-1}{2}}\big\rceil \leq \big\lfloor\frac{|V|}{2}\big\rfloor \leq \frac{|V|}{2}$.

Claim 2: The resulting graph created by the algorithm has no bridges.
Proof: Consider a partition $(V',V- V')$. Let $v_i \in V'$ and $v_j \in V-V'$ such that $(v_i, v_j)$ is an edge of the initial tree. Such edge obviously exists since the tree is connected. At some point the algorithm selects a path containing the edge $(v_i, v_j)$ and creates a simple cycle which includes the edge $(v_i, v_j)$. So, there are two different paths between vertices $v_i$ and $v_j$, and hence there are at least two paths (or edges) connecting the partitions $V'$ and $V-V'$.

This algorithm does not compute the optimal number of edges for all possible input instances. For example for a tree which is a path it is enough to add a single edge connecting two end points to transform the tree into a bridgeless graph. My goal is to establish the least upper bound for the number of edges required to add to a tree to transform it into a bridgless graph. For example a star-like tree with even number of vertices is a worst case in which case we need exactly $\frac{|V|}{2}$ edges.


Efficient way to count number of intersections of line segments On my computer science course's exam I was given the following task:
You are given $n$ segments that lies on the same line: $i$-th segment starts at coordinate $from_i$ and ends at $to_i$. Your task is for each segment count number of other segments that intersects it.
EXAMPLE INPUT:
5
7 8
8 9
0 3
2 7
10 15
EXAMPLE OUTPUT:
2 1 1 2 0
I've implemented the naive algorithm:
def count_intersections(i):
    counter = 0
    for j in range(len(data)):
        if i != j:
            if data[i][0] <= data[j][0]:
                left = data[i]
                right = data[j]
            else:
                left = data[j]
                right = data[i]

            if right[0] <= left[1] <= right[1]:
                counter += 1
            elif left[0] <= right[0] <= left[1]:
                counter += 1

    return counter

n = int(input())
data = []
for i in range(n):
    data.append(tuple(map(int, input().split())))

for i in range(n):
    print(count_intersections(i), end = ' ')

As you can see, I just iterate through eacher other segment and increment counter if it intersect the given one. Time complexity of my solution is $O(n^2)$. And because of this I got Tme Limit Error.
Do you know more efficient solution? Maybe some extraordinal Data Structure?

Let's first assume there is no common boundaries between all segments.
Create the list of tuples ($pos$, $ind$) with a value ($pos$) for each boundary of every segment (thus $2n$ values) and $ind$ the index of the segment, sorted by $pos$. Sorting is achieved in $O(n \log(n)).$
Keep two counters, $open$, the number of opened segments and $close$, the number of closed segments. Both are initially at 0.
$E[i]$ will be an array of the segment $i$ state, where 0 means not opened yet, 1 otherwise.
$A[i]$ will be the $n$-element array to output, which are 0s initially.
Then loop through the list,
for tuple (pos, i),
    if E[i] == 0, then A[i] = close, open += 1, E[i] = 1
    else A[i] = open-A[i]-1, close += 1

The "-1" stands for a segment not counting himself.
This achieves $O(n)$, then still driven by the sorting $O(n \log(n))$.
Now, how to treat common boundaries ? In your exemple, I understand that segments are closed and for example [2, 7] does intersect [7, 8]. A simple way to do it (clearly not the most efficient but still $O(n)$), is to loop 3 times on the tuples at the same position:

first, you only count the opening segments in $open$
then, you only update $E[i]$ and $A[i]$ for both opening and closing segments
finally, you only count the closing segments in $close$ (that now have $E[i] = 2$)


Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$ I am trying to find a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$, which has the hint of it having "some similarity" to $L=\{a^ib^j|i<j\}$
This last one is quite easy to get ($S\to aSb | Sb | b$), but still I am unsure on how to proceed.
I expect to manipulate the language by differentiating cases, and for example I found that if $n>m$, I will have to solve $a^{m+k}b^mc^rd^s, k\ge1$, and if $n<m$, I will have to solve $a^nb^{n+k}c^rd^s, k\ge1$, but, still I don't see the recursivity.

Any word $w$ in $L$ can be split into two words $w$ and $w'$ such that $w \in \{a^n b^m c^r d^s \mid n + m = r+ s \}$, $w' \in \{c^r d^s \mid r+s > 0\}$ and if the last symbol of $w$ exists and is $d$, then the first symbol of $w$ is $d$.
On the other hand, every choice of $w$ and $w'$ that satisfies the above constrains induces a word $w w' \in L$.
In the following grammar the first two productions take care of generating $w'$, while the other productions generate $w$. In particular the nonterminal $X_\alpha^\beta$ with $\alpha \in \{a,b\}$ and $\beta \in \{cd\}$ will generate all the words in $w \in \{a^n b^m c^r d^s \mid n + m = r+ s \}$ such that (i) if $\alpha=b$: then $n=0$ and (ii) if $\beta=c$ then $s=0$.
$$
\begin{align*}
S &\to Sd \mid X_a^dd \mid Yc \mid X_a^cc \\
Y &\to Yc \mid X_a^cc \\
X_a^d &\to aX_a^d d \mid X_a^c \mid X_b^d \\
X_a^c & \to aX_a^cc \mid X_b^c \\
X_b^d &\to b X_b^d d \mid X_b^c \\
X_b^c &\to bX_b^cc \mid \varepsilon
\end{align*}
$$


pda: transformation between acceptance by empty stack and final states I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state with a new start stack symbol, and another state after the original final states for emptying the stack. I understand the new state for emptying the stack, but why do we need a new start state and a new start stack symbol? Assume the the old pda has start state q0, start stack symbol Z0, when it goes to a final state qf, you may/may not expose Z0 on the stack. To make it into a pda accepting empty stack, can't we just create another state qe with an edge from qf->qe, at qe you can pop off any stack symbol until it becomes empty. What's wrong with my thoughts?

If I am understanding this correctly, you want to transform a PDA with final state acceptance into one that accepts by empty stack.

First point is, like you mention, when entering an "old" final state to go into a special state where the stack is emptied.

Second point is that we do not want to reach an empty stack at another moment during the computation. Note in that case the old automaton does not accept, but the new one accidentally does! The solution is (indeed) to add a new bottom symbol that can not be removed except at the special state. In that way accidental accepts are avoided. (And this what I understand is the extra part of the construction.)


Can a perfect matching always be found by a picking sequence? There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference graph (encoding the "like" relation).

In some cases, this may be done using a picking sequence: order the people in a queue and let each person in turn pick a single item he likes. For example, suppose that:

$A$ likes $\{1,2\}$
$B$ likes $\{2,3\}$
$C$ likes $\{3\}$

Then, $\langle C,B,A\rangle$ is a good picking sequence, since $C$ necessarily picks $3$, then $B$ picks $2$, then $A$ picks $1$ and we get a perfect matching. On the other hand, $\langle C,A,B\rangle$ is not a good picking sequence, since after $C$ picks $3$, it is possible that $A$ will pick $2$, and then $B$ will remain without an item.

So, my question is: If a perfect matching exists, can it always be found by a picking sequence?

Yes, it can. This can be proved by mathematical induction on $n$.

Denote by $U$ the set of people. For a subset of people $P$, denote by $N(P)$ the neighborhood of $P$, that is the set of items that at least one person in $P$ likes. By Hall's marriage theorem, $|P|\le |N(P)|$ for all $P$.

If $|P|< |N(P)|$ for all $P\subsetneq U$, then we can let an arbitrary person pick first. After his picking, $N(P)$ is decreased by at most 1 for all $P$, so $|P|\le |N(P)|$ holds for all $P$ in the remaining graph. Therefore there is still a perfect matching in the remaining graph by Hall's marriage theorem, and there is a valid picking sequence by inductive assumption.

If there exists $P\subsetneq U$ such that $|P|=|N(P)|$, then there is a perfect matching in the subgraph induced by $P\cup N(P)$, and by inductive assumption there is a valid picking sequence for people in $P$ in this subgraph. We can apply this picking sequence in our orignial graph first, and the result is the same, that is, exactly all items in $N(P)$ are picked. Note there is still a perfect matching in the remaining graph, so we can again use the inductive assumption to complete the picking sequence.


Swap elements using integer addition and multiplication gates I need to swap two integers using only integer addition and multiplication gates.
I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap operation swaps only if the integers being compared are in wrong order. I've to implement this operation using just integer addition and multiplication as the atomic operations. I've figured out the comparing bit, but I need to efficiently swap integers.
Is there an efficient solution (minimum multiplication gates) to this problem?

P.S: I have integers in the form of binary vectors, but I can't apply mod 2 operations on them. I can only use integer addition and multiplication.

Let's say we have inputs $x, y$ and $c$, where $c$ is either 0 or 1, 0 = no swap, 1 = swap. We can make a conditional swap function like this:

notc = 1 + (-1)*c
x' = notc*x + c*y
y' = c*x + notc*y

Even if you have no negative integers, as long as your integers are modulo $2^n$, you can use $-1 \equiv 2^n - 1 \mod 2^n$ and everything works out.


How can I formalize key value stores with set theory? I'm currently developing a simple key-value NoSQL store and want to build its formal model. I found article about key value formalisation with category theory, but I'm interested are there some works about formalisation of key-value stores except category theory (I know we can use it for all, but...)? I want to use some more simple and lightweight mathematics for mathematical description of key-value stores. And I feel that set theory will be enough for this, but couldn't find any helpful articles.

One simple way to model a key-value store is as a map $f:K \to V$ where $K$ is the set of possible keys and $V$ is the set of possible values.

Often, each value $v \in V$ will itself be a tuple or record.  You can represent a tuple as a Cartesian cross-product, e.g., $V = V_1 \times V_2 \times \dots \times V_k$.  You can represent a record as either a tuple (if the set of attributes is finite and known in advance), or as a function from attribute names to values.

Modelling languages like Alloy can represent such maps natively.  Some modeling languages will use the notation $k.f$ instead of $f(k)$ (i.e., object field access notation instead of function evaluation), but the two are equivalent.

If you don't want to use functions, but want to stick to just sets, that is also feasible.  You can model any function $f: K \to V$ as a binary relation, i.e., a set $S \subseteq K \times V$ with the additional property that if $(k_1,v_1) \in S$ and $(k_2,v_2) \in S$ and $k_1=k_2$, then $v_1=v_2$.  However this may be less natural.

This gives you a way to model the state of the store.  You will then need to model the effect of each operation that can be performed on the store, in these mathematical terms.


Is the following statement about turing machines true? Here's the statement:

  Take a set of finite inputs from some alphabet. If for any two turing machines:

  All inputs in the set produce the same output for both machines
  In both machines, the following is true: every state transition (i.e. every row in the state table) occurs at least once for at least one of the inputs in the set before halting

  Then both machines will produce the same output as each other for any input.

This is an informal statement, it probably needs a bit of refining. But for now the question is, is this true?

This is an interesting statement, but it is not true. I'll give a proof sketch and leave the construction of the actual machines to you (read as: I am too lazy :) ). For example, take two functions

$f : \mathbb{N} \setminus \{0\} \to \mathbb{N}, n \mapsto n^2$

$g : \mathbb{N}\setminus \{0\} \to \mathbb{N}, n \mapsto 2^n$

and two turing machines $M_f, M_g$ which compute $f$ and $g$, respectively. Without loss of generality, we may exclude $0$ because I think it might require special handling in $M_g$, but this depends on the actual construction of the turing machine - it does not matter this way.

It is safe to assume that minimal turing machines for $f$ and $g$ would need each of its transitions for any value bigger than $1$ since they both have to implement some kind of looping scheme. This comes from the fact that $f$ and $g$ can be defined primitive-recursively, where $0$ and/or $1$ are the recursion base cases (depending on your exact definition). Now if we look at the values of these two functions:

$\begin{align}
n&:& &1,& &2,& &3,& &4,& &5,& ... \\
f(n)&:& &1,& &\color{green}{4},& &9,& &\color{green}{16},& &25,& ... \\
g(n)&:& &2,& &\color{green}{4},& &8,& &\color{green}{16},& &32,& ... \\
\end{align}$

We see that for an input set $I = \{ 2, 4 \}$, then $M_f$ and $M_g$ compute the same value for all input values, and since $\forall n \in I : n > 1$, they would also need all of their transitions. Still for any input value $n \geq 1, n \notin I$, they would differ.

To generalize: Take any two sequences of numbers which are recursively defined and computable and also equal in at least two places, then the statement does not hold.

I overcame my laziness and did one turing machine for the calculation of $2^n$ in unary. The code can be executed on this turing machine simulator to check that for inputs $11$ and $1111$, every state transition is required.

; Compute 2^n in unary
; First go to the end of the input string and write a single 1.
; The tape content is then <input>01
 0 1 1 r 0 ; Move right until we are at the end of the input string.
0 _ 0 r 1 ; Write 0 separator
1 _ 1 l 2 ; Write an initial 1, since this is the value of 2^0.

; Then rewind to the beginning
2 1 1 l 2 ; Keep moving left without altering 1s
2 0 0 l 2 ; Keep moving left without altering 0s
2 _ _ r 3 ; We move back to the start.

; Now we double the string after the separating zero until
; there are no more 1s in the beginning (= decrement counter until 0)
3 1 _ r 4 ; Remove the first 1, this is equal to decrementing the counter
3 0 _ r halt ; if there are no more 1s, we are finished.
4 1 1 r 4
4 0 0 r 5 ; Move right till the separator is found
5 1 1 r 5 ; Move to the end of the result string
5 _ _ l 6
6 1 _ r 7 ; And replace the last 1 with a blank, the initial position marker.
7 _ 1 l 8

; Now comes the actual doubling
8 1 1 l 8 ; Move left until the blank marker is found
8 _ 1 l 9 ; Move left until the blank marker is found
9 1 _ r 10 ; Shift the blank marker to the left
10 1 1 r 10 ; Move to the end of the string...
10 _ 1 l 8 ; ... and write a 1.
9 0 0 l 11 ; Once we hit 0, we are finished doubling

; And again rewind to the beginning
11 1 1 l 11 ; Keep moving left without altering 1s
11 _ _ r 3 ; We move back to the start.

The computation of $n^2$ is similar, except that for doubling the output $n$ times, you add $n$ to $n$ exactly $n$ times.


What is standardization in computer science? I was reading about the differences  standards and specifications for C.
I understood that programming languages are usually stadardized and I learnt that there are different approches to stadardization.
Anyway I did not understand yet what this terms refer to.
If I think to C, I believe it refers to a standard API, the API of the C standard Library (libc).
 This seems to make sense to me, as if someone told me "Look these are the only functions, types, Macros....etc you can use", because they're the only thing you "see" after you downloaded the library and they make your code portable.
 Anyway, I don't know if my idea of standardization is in some-ways correct, if it's totally wrong or if it's a simplified version, so here I am.

A standard for a programming language is a document defining the syntax and semantics for that language. Usually, for real-world languages, this document involves a (hopefully) precise description in intuitive terms, rather than a formal semantics, written in mathematical terms.

Still, this document acts as a contract between the programmer and the language implementation (usually a compiler/interpreter, plus some "standard libraries").

The programmer knows that, if they stick to what the standard mandates, they will get back the intended result from the implementation. Vice versa, the implementor of the language can assume that the programmer used no other features than those mandated. Often, the implementor will also provide non-standard features (additional APIs, additional language constructs, OS-specific libraries, etc.).

Note that the standard does not only involve describing the APIs in the standard library. In the case of the C language, as mentioned by the OP, the standard defines among others: the syntax, the type system, the memory model, the statements, the variable declarations, etc.

For instance, what happens if we write int *x; *x=0;? The ISO standard answers that: an implementation printing mooo! on screen is perfectly conforming (as any other implementation is).

So, summing up, a standard is the authoritative document which answers questions like "is running code C guaranteed to have behavior B?".

Most standards are written by a committee made of the most prominent organizations which developed / are developing the most widespread implementations. They vote on which features should be in or out, until they reach an agreement on what should be the standard definition. Some languages are revised every few years, so to include more features.


Multiple post-fix expressions for an in-fix expression Today I was learning to convert post-fix expressions to in-fix expressions and vice versa. What I want to know is whether a post-fix expression can have more than one infix representations.

For example, if I consider the following in-fix expression:

A+B-D/X

I get these post-fix expressions:

ABDX/-+

and

AB+DX/-

I didn't use the stack table method for solving these. I did these conceptually and both these expressions evaluate to

A+B-D/X

post-fix expression. I even verified my result with this site and both the post-fix expressions evaluate to:

A+B-D/X

(A+b)-c and a+(b-c) are not the same. Not with integers (one expression might overflow while the other one doesn’t), not with floating-point numbers ( different rounding errors).

Only the second postfix expression is correct.


Why isn't an edge-map graph implementation used in practice? Wikipedia states that three different graph implementations that are used in practice:

Adjacency Lists
Adjacency Matrix
Incidence Matrix

While I was learning about these structures, another implementation occurred to me that seems to have better asymptotic properties than Wikipedia's. My idea is to create a hash map where the keys are (vertex, vertex) pairs and the values are the cost of their edge.

Given that inserting into and querying from a hash map is $O(1)$, I believe the time complexity would be the following:

Store graph: $O(E)$
Add vertex: $O(1)$
Add edge: $O(1)$
Remove vertex: $O(V)$
Remove edge: $O(1)$
Query cost between vertices: $O(1)$

Since this implementation has strictly better time and space complexity then all three options listed, I'm confused as to why this option isn't.

Why isn't this implementation used in practice?

Assume we are dealing with the representation of a weighted graph. I will use Python as the programming language to illustrate the points, which will remain true largely if another programming language is used.
Let us call the graph representation raised in the question "hashmap from edges to their weights" or "edge-weight hashmap". I would agree that an edge-weight hashmap is seldom used to represent a weighted graph.
One overwhelming reason is that compared to edge-weigh hashmap, it is usually preferred to use the following popular variation of adjacency list, which I will call "adjacent hashmaps" or "nested hashmaps". The entire graph is represented by a big hashmap $g$, a.k.a. the outer hashmap, which is a collection of $(v, g[v])$ pairs, where $v$ is a vertex and $g[v]$ is a smaller hashmap, a.k.a. the inner hashmap. $g[v]$ is a collection of of $(u, w)$ pairs, where each vertex $u$ is a vertex that is adjacent to $v$ and $w$ is the weight of edge $(v,u)$.
An example

$\begin{array}{c|c}
 \text{Nested Hashmap} & \text{Edge-weight Hashmap} \\\hline
  \begin{array}{l@{}l@{}l@{}lll}
\{\\
\quad1: &\{2:2,&4:5\},\\
\quad2: &\{1:2, &3:14, &4:5, &5:4\},\\
\quad3: &\{2:14,&5:34\},\\
\quad 4: &\{1:5, &2:5, &5:58\},\\
\quad 5: &\{2:4, &3:34, &4:58\}\\
\}\end{array}                &
\begin{array}{lllll}
\{\\
\quad(1,2):2,           &(1,4):5,\\
\quad(2,1):2, &(2,3):14,&(2,4):5,&(2,5):5,\\
\quad(3,2):14,&(3,5):34,\\
\quad(4,1):5, &(4,2):5, &(4,5):58,\\
\quad(5,2):4, &(5,3):34,&(5,4):58\\
\}\end{array} \\
\end{array}$
The alignment of data entries above is meant for easy reading of Python code. By the general nature of hashmap, the actual storage locations of the entries in a hashmap are sort of unpredictable.

Comparison of complexity between nested hashmaps and edge-weight hashmap
$\begin{array}{|l|c|c|}\hline
&\text{Nested Hashmap} & \text{Edge-weight Hashmap}\\\hline
\text{Store graph} &O(|E|) &O(|E|)\\\hline
\text{Add vertex} &O(1) &O(1)\\\hline
\text{Add edge} &O(1) &O(1)\\\hline
\text{Remove vertex} &O(|V|)&O(|V|)\\\hline
\text{Remove edge} &O(1) &O(1)\\\hline
\text{Check if two vertices are adjacent} &O(1) &O(1)\\\hline
\text{List neighborhood of a vertex }&O(|V|) &?\ O(|E| )\ ?\\\hline
\end{array}$
The entry "$?\ O(|E| )\ ?$" entry on the column of "edge-weight hashmap" means that it is not clear how to list neighborhood of a given vertex $v$ efficiently. $O(|E|)$ refers to the time-complexity of the natural way, which goes over all the edges, keeping only the edges that contain $v$.
So both implementations have the same asymptotic time-complexity and space-complexity for all operations, except for listing the neighborhood of a vertex, arguably the most popular iteration on a graph, for which nested hashmaps are significantly faster. In practice, nested hashmaps should also exhibit better cache-friendliness.
Comparison of programming friendliness
Here are the code that does the basic iterations over a graph represented in variable $g$ using nested hashmap or edge-weight hashmap.
$\begin{array}{|l|l|c|}\hline
&\text{Nested Hashmap} & \text{Edge-weight Hashmap}\\\hline
\text{Iterate over all vertices} &\text{for v in g:} &???\\\hline
\text{Iterate over the neighborhood of vertex u} &\text{for v in g[u]:} &???\\\hline
\text{Iterate over all edges} &\begin{array}{c}\text{for u in g:}\quad\quad\\\text{ for v in g[u]:}\end{array} &\text{for e in g:}\\\hline
\end{array}$
The "???" entries on the column of "edge-weight hashmap" means that it seems rather clumsy to write that piece of code in Python or other programming languages, assuming their generally-available implementations of hashmap.
Nested hashmaps are far more programmer-friendly than edge-weight hashmap.
Summary
Although the time-complexity of the most basic operations using edge-weight hashmap are very good, it does not support the basic iterations well. It should be replaced by nested hashmaps in general.
Exercises
Exercise 1. Verify that this answer is applicable for weighted directed graph after slight adaptation. Verify that this answer is applicable for (unweighted) directed or undirected graph as well.
Exercise 2. Compare edge-weight hashmap with adjacent-weight list in detail. An adjacent-weight list for the graph above in Python can be $g=[[], [(2,2), (4,2)],$ $[(1,2), (3,14), (4,5), (5,5)],$ $[(2,14), (5, 34)],$ $[(1,5), (2,5), (5,58)],$ $[(2,4), (3,34), (4,58)]]$, where $g[v]$ is a list of $(u,w)$ pairs for vertex $v=1,2,3,4,5$ (g[0] is ignored since 0 is not a vertex), where $w$ is the weight of edge $(v,u)$.


How to efficiently find line-segment intersections between two sets? So I'm building this iterative simulation of a surface (composed of line segments) that cannot self-intersect, which means I have to check intersections at the end of a timestep. The thing is, I know, at the beginning of every timestep, that no intersections exist within the set of all line segments that constitute the surface, and at every timestep, a fixed number of nodes is altered (if this produces intersections, the simulation resets). Let's call the set of all lines after an alteration N and the lines that have been altered K. I then know that I should only look for intersections within K and between K and {N - K}, because I know there can be no intersections within {N - K}. This is equivalent to wanting to find intersections between K and N.

When I first tackled this problem, I just implemented sweepline, but now I realize that it finds intersections within a set. As far as I can tell, adapting the algorithm to find intersections between segments in a set X and segments in a set Y is quite tricky; I haven't been able to work that out. The only things I thought of is doing brute force (which amounts to |K| * |N|) and just ignoring K and applying sweepline, which is |N|lg|N|. If there's a way to combine the best of both approaches,I'd expect there to be a big difference in the performance of my code. Is there such a way?

The problem you describe is known as the red-blue intersection problem. Here, we have a red set of $n_1$ segments and a blue set of $n_2$ segments and we know that there are only intersections between segments of different colour.  Although this special case has been extensively studied, the $O(n\log n + k)$ algorithm, with $n=n_1+n_2$ is still optimal1 when if we have no further information.

In particular, we cannot easily combine the two approaches. To get some intuition on why adapting the sweepline algorithm in particular doesn't simply work, consider the case where $n_1=1$ and $n_2 = 1000$ and take a large blue segment such that the rectangle that has this segment as a diagonal contains all endpoints of the red segments. In this case, all red segments could be intersecting the single blue segment, so the sweepline has to consider all points in $n_2$ as event points and hence it is possible we have to spend at least $\Omega(n_2\log n_2)$ time on our sweepline algorithm.

There is one special case in which we can be faster. A planar subdivision is simply connected when each closed path over the edges within the same region of a subdivision can be topologically contracted to a point, i.e. a region cannot contain another region (similar to a simply connected space). If the two sets of segments form two simply connected planar subdivisions, we can use the algorithm by U. Finke and K. Hinrichs. to find all intersections in $O(n+k)$ time.

1. Optimal if $n_1\approx n_2$. Of course, if $n_2 \ll\log n_1$, we can do better with the naive algorithm, but that is rarely the case.


Are colored graphs and red-black trees related? I've come across the concepts of colored graphs (register allocation) and red-black trees. They both seem to have this notion of "coloring", but I've never seen them being connected conceptually.
Do they have anything to do with each other?

No.  They don't have anything to do with each other.


What is meant by a language have a "finite specification"? I'm studying my notes for a formal language course and it them it states

  The vast majority of languages over a finite alphabet cannot be
  represented by a finite specification.

I don't understand this. What is meant by "specification"? It then goes on to show why this is true by showing some sets of the alphabet are countably infinite and others are uncountably infinite.

A specification in this sense is any description of the language that allows you to determine exactly what strings are in the language and what strings are not. We're usually quite vague about what exactly constitutes a specification since, ultimately, it doesn't matter. A specification must be describable by some finite string of characters, whether those characters represent English words ("The set of all strings consisting of some number of $a$s followed by the same number of $b$s"), mathematics ("$\{a^nb^n\mid n\geq 0\}$") or somethign else. As your notes go on to say, whatever reasonable meaning you give to "finite specification", there will only be countably many of them, whereas there are uncountably many languages.