Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.

The total value of $n$ gifts is $W$. The most fair division will be to give all of them gifts of the total value $W/3$.

Suppose $W_1, W_2, W_3$ are the total values of the gifts of the first, second and third person.

We want to minimize: $\max(W_1, W_2, W_3) - \min(W_1, W_2, W_3)$.

Using the knapsack problem. Assign to the first knapsack the "weight" $W/3$ and the same for the second knapsack $W/3$. Use double knapsack algorithm and get the for each knapsack the gifts that maximizes the total value but obeys the $W_{i \in {1,2}} \le W/3$ property. Then the remaining gifts give to the third person.

The question is if such kind of algorithm is correct? If so why? If no can you provide your own solution to the problem?

Say your best answer so far has a difference D, and you can give w/3 - a to the first person. The best result you can have is w/3 + a/2 to the other two, giving a difference of 3a/2, so you only proceed if 3a < 2D (actually, you will distinguish cases depending on w modulo 3 if all sizes are integers).

Then you pick items for the second person. If you can give them w/3 - b, b ≥ a, then diff = a + 2b, so you need a + 2b < D, or b < (D - a) / 2; only if a ≤ D/3. If you can give them w/3 - b, 0 ≤ b ≤ a, then diff = 2a + b, so you need b ≤ D - 2a, only if a ≤ D/2. You analyse the case w/3 + b for the second person as well, so you find a range for how much goes to the second person.

Problem is that you waste a lot of time with sets for the first person that are not particularly close to w/3. Based on the number of items and their values I'd make an estimate how good the best solution would be (how much the smallest D will be) and only look for items for the first person that might give a result < 2D, then extending to 4D, 8D etc. if nothing is found.

And you should check the case where one item is > w/3 first, or you might waste a lot of time.

What if having empty basket for each person, keep tracking on sum of items in each basket. So we always know which basket has the minimum value. Then we can go over list of items and put the new one, in the basket with minimum total value. The complexity of this hypothesis is $O(n \log(n))$.


What is the difference between an embedded system and dedicated system? To my understanding,

a dedicated system is a computer system capable of performing 1 specific task
an embedded system is a computer system within a larger system that performs a specific task

Is there a difference that i'm missing or is dedicated system just a more generic term for referring to things like 'file server'.

Thanks

An embedded system is embedded in some larger device/system. For example, a computer used to control a car is embedded, or the microprocessor controlling e.g. a washing machine.

A dedicated system is one which is used for one task only, like file serving or running a database.

Most embedded systems are dedicated (to their specific task(s)). There isn't a clear cut definition.

An embedded system, is like a microprocessor, not to be confused with a CPU. It requires no extra software to work.


Reduction from Vertex Cover The city council would like to place trash bins around the city and has a list of suitable spots (street crossroads, supermarkets etc.) but the number of these spots is greater than the number of available bins. The council's goal is to place the limited number of bins so that the distance from each house to a bin is at most 100 m. Prove that the problem k containers are sufficient is NP-hard using reduction from a known NP-hard problem.

I came up with vertex cover (could we alternatively use dominating set?). We then need to transform an instance of vertex cover $(V, E, k)$ to an instance of this problem. It's not clear to me how. This is how I thought I would represent the k containers are sufficient problem by a graph:

My first step would be to create a graph where the set of nodes contains both the spots for containers and all the houses. I would then connect each spot node with all the house nodes that it is close enough to (100 m). This seems quite close to vertex cover except that there are 2 types of nodes:

The house nodes cannot be used as a part of the vertex cover set since bins cannot be placed in front of houses but they need to be covered by the vertex cover set.
The bin spots can be used as a part of the vertex cover set but do need to be covered at all by it.

How could I deal with this in the reduction? I thought about using some vertex to edge transformation to represent these relationships but came up short.

This is known as the $k$-center problem or the planar minmax Euclidean facility location problem.  It is a special case of the minimax facility location problem for the Euclidean metric.

The $k$-center problem is known to be NP-hard.  Wikipedia has references to the literature, where you should be able to find an explicit reduction.

The special case where $k=1$ can be solved in polynomial time.

I have come up with the following solution:

We transform an instance of vertex cover $(V, E,k)$ to a specific instance of k containers are sufficient in which the the available spots for containers are equivalent to the set $V$ and in which the set of houses that have to be near containers is exactly equal to $V$ (the available spots for containers are exactly where the houses are located). The edges connect houses-spots which are within 100 ms of each other.

It shouldn't then be difficult to see (since the k containers are sufficient problem formulated in this way is basically identical to vertex cover) that the graph $G=(V,E)$ has a vertex cover of size $k$ exactly when $k$ containers suffices to serve all the houses.


Can we say DFA is more efficient than NFA? I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it has only one outgoing edge & there will be no ambiguity. But in case of NFA we have to check all possible cases & that surely takes time. So can we say DFA is more efficient than NFA ?

But, my other part of brain is also thinking that NFA exists only in theory, so we cannot compare it's efficiency with DFA.

There are two answers, depending on how you define efficient.

Compactness of representation

Telling more with less: NFAs are more efficient.

Converting a DFA to an NFA is straightforward and does not increase the size of the representation.

However, there are regular languages for which the smallest DFA is exponentially bigger than the smallest NFA. A typical example is $(a|b)^*b(a|b)^k$ for $k$ fixed.

Computation

Running it fast: DFAs are more efficient.

The computers we use today are deterministic in nature. That makes them bad at dealing with non-determinism. There are two common ways of dealing deterministically with NFAs: backtracking on one side, which is rather costly, or keeping track of the active states, which means each transition will take up to $N$ times longer (where $N$ is the size of the NFA).

As we know about Automata i.e machine which can perform any action without any man power or without direct participation of man. eg: washing machine.
Finite Automata means we know the sate of performing task by machine like 1 press ON 2 press OFF so there is only 2 states i.e called finite automata.
Now come to DFA i.e deterministic Finite automata. formally mean we can easily determine states there is no ambiguity and informally it need only 1 transition allowed on 1 symbol.
NFA: non deterministic finite automata. there is need more time to compute actual state and there is ambiguity andd informally says there is multiple allowed transition on 1 symbol.
in the case of time to reach the destination NFA takes more time than DFA but NFA can load more data than DFA.
* DFA and NFA has same power to recognize the string.
thank you..
Deepali kaushik


Find out the largest LCM of the partitions of n I want to find out an algorithm to find out the largest least common multiple (LCM) of the partitions of an integer $n$.

Example:  $5 = 1 + 4$, $5 = 2 + 3$, since $\mathrm{LCM}(1,4) < \mathrm{LCM}(2,3) = 6$, the largest LCM of the partitions of $5$ is 6.

The definition of "partition" is the standard definition of it. In order to make the problem more clearly, I will take n = 10 as an example. The largest LCM if the partitions of 10 is 30, since 10 = 2 + 3 + 5.
More examples(Let g(n) be the answer that I want to get):
g(11) = 30
g(12) = 60
g(13) = 60

I want to find out an algorithm that can get the largest LCM in 1 second with the n less or equal to 250.

It seems that this a competition problem. Your best bet is to pre-calculate maximum values for all numbers(250 isn't very big) and store it into an array. That would be the best bet as this can give you timing near to zero.

For partitioning into two numbers the product is maximized when the two variables are closest to one another:
$$g(n) \equiv \mathrm{max} \{ xy : x + y = n\} = \left\{ \begin{array}{clll}
\frac{n}{2}\cdot \frac{n}{2} &=& \frac{n^2}{4} & \text{even} \\
\frac{ n-1}{2 }\cdot \frac{ n+1}{2 } &=& \frac{ n^2-1}{4 }& \text{odd}
\end{array}\right. $$ This is called convexity.

Since we are looking for LCM and not product, call that result $f(n)$.

In the even case, we should be careful that $\mathrm{LCM}(n,n) = n$ so we need to find the next best one:
$$\left(\frac{n}{2} -1 \right)\cdot \left(\frac{n}{2} +1\right)= \frac{n^2}{4}-1$$
Two consecutive numbers will have an LCM of at most 2.

In the odd case, two consecutive numbers will be relatively prime.

f(9) = 4*5 = 20
f(8) = 3*5 = 15
f(10) = 3*7 = 21

Here's a draft answer:

$$f(n) \equiv \mathrm{max} \{ xy : x + y = n\} = \left\{ \begin{array}{cr}
\frac{n^2}{4}-1 & 0 \mod 4 \\
\frac{n^2}{4}-4 & 2 \mod 4 \\
\frac{ n^2-1}{4 }& 1,3 \mod 4 \end{array}\right. $$

Because the integers are discrete, and the irregularities of the LCM, you have to make all sorts of corrections.

for small $n$ this is certainly wrong
the answer seems to depend on the factors of $\frac{n}{2}$ for even values of $n$

You may not want to follow this logic to several variables - and there may be a slicker totally different way.  At least we can see some of the continuity of the numbers you are generating.


Does our PC work as Turing Machine? Does our PC work as Turing Machine?  The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have 256^30128000000 states and thus, it has finite states.

I know that we can write a type of program that, if during execution we run out of memory, will request to swap memory disk with empty memory disk and resume execution.

But what if we don’t swap memory disk, in this case is it right to consider PC as FA?

You're right that physical computers have finite memory and so are not Turing-complete. There are other ways in which computability theory is not a good model for computing - it doesn't take into account time and memory constraints. Complexity theory was invented (perhaps) as a more realistic depiction of computing, but IMHO suffers from similar (but subtler) problems.

On the other hand, in order to mathematically study the capabilities and limits of computing, we need to use some abstraction which is unconstrained. That makes the analysis possible. Similarly, in statistical mechanics we assume that the number of elements (atoms or molecules) is so large, that the behaviour is close to the limit (that is, we let the number of elements tend to infinity). Studying computing from an asymptotic perspective has similar advantages, but sometimes is misleading. Here are some examples of the latter:

In cryptography, exponential algorithms are sometimes feasible. If we choose the wrong security parameters, our encryption might be insecure even though it's "provably secure".
Polynomial-time algorithms are supposed to represent efficient and feasible computing, but many of them aren't feasible. As an example, most sophisticated matrix multiplication algorithms aren't used in practice.
Modern complexity theory is obsessed with worst-case performance, and cannot analyze heuristic algorithms which are used in practice. NP-hard problems are considered infeasible, yet they are being solved in practice all the time.

A separate issue is that real computers don't work like Turing machines at all. They work like RAM machines, which are a better abstraction for actual computing.

A modern computer is Turing complete, generally this term is used with the exception of infinite storage device. In practice, the memory can be quite long. For example, along with being universal function approximators, recurrent neural networks with memory (and running repeatedly) are said to be Turing complete. Indeed, Neural Turing Machines take this idea to a stage further inferring simple algorithms.


Minimizing the SUM algorithm We are given $2n$ positive integers $a_1,a_2\ldots,a_n$ and and $$b_1,b_2,\ldots,b_n$$ as input.

The question is to find a permutation $O$ on $\{1,2,\ldots,n\}$
that minimizes $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right).$$

For example, take $n = 3$, $a_1 = 10, a_2 = 1, a_3 = 100, b_1 = 10, b_2 = 100$, and $b_3 = 1$.
  If we take $O$ so that $O(1) = 1, O(2) = 3$, and $O(3) = 2$, we have $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 1311.$$

The desired output is $O(1) = 3, O(2) = 1$, and $O(3) = 2$, which yields $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 321.$$

Trying all possibility is exponential.
How can I find an optimal permutation $O$?

Did you check what's the class of your problem? I'd try a reduction to a scheduling problem.

If you want to have something so you solve it today, use Branch and Bound. Bounds should be easy to find.


If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$? If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$

I saw a proof where they have proved  If $f(n)=O(g(n))$ and $h(n)=\theta (g(n))$ then this implies $f(n).g(n)=O(g(n).h(n))$.

So I thought may this should also hold. I have taken some examples and the formula holds on all of them. However I can't be sure. There can be a contradicting case.

I have got the answer. It's easy.

Since $f(n)= \Omega g(n)$

$cg(n)\le f(n)$

Multiplying both sides by h(n)

$cg(n).h(n)<=f(n).h(n)$

$f(n).g(n)=\Omega(g(n).h(n))$


Buying as many items for as much money I cant find a way to implement a certain solution. Let me flesh out the problem.

Somebody gives you X amount of money and sends you to the shop to buy Y amount of items. You must spend as much money as you can and buy as many items as you can. You cant have more money they X. You cant buy more than Y amount of items. Some money can left afterwards, but as little as it can. You can buy less than Y items, but only if there is no other option. You cant buy same item more than once - items are unique.

Examples:

You have 15£, and need to buy 2 items. There are 4 items for 10£, 5£, 4£ and 3£. You buy 10£ and 5£ items. Perfect scenario - 15£ spend, 2 items aquired.

You have 15£ and have to buy 3 items. There are 4 items for 4£, 3£, 2£, 1£. You buy 4£, 3£ and 2£ items. 9£ and 3 items aquired.

You have 15£ and have to buy 2 items. There are 4 items for 20£, 19£ and 14£. You buy only 14£ item.

I think you understand by now how it works.

Implementation(Javascript):

var arrayOfItems = [];
arrayOfItems[0] = {"name":"Sandwich","price":15};
arrayOfItems[1] = {"name":"Water","price":10};
arrayOfItems[2] = {"name":"Cookie","price":5};

function getItems(moneyAmount,itemsAmount){
    //your code here....
}

var items1 = getItems(21,2); //returns [0,2]
var items2 = getItems(25,2); //returns [0,1]
var items3 = getItems(14,2); //returns [1]

I need to invent the inside of getItems() function. Can you lead me how to do this?

Thank you for help.

This is a classic Knapsack problem  some examples: Knapsack.java, JS example

Here is a pseudo code from Introduction to Algorithms, MIT:


What is the difference between expected cost and average cost of an algorithm? While going through probabilistic/average analysis of an algorithm, I found written somewhere that average cost and expected cost are same. Can anyone please tell me what does exactly expected cost stands for.I think we take care of likelihood of an event while finding expected cost unlike average cost.

In short, the average is the expected value of the uniform distribution.

If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the expected runtime for input size $n$ is

$\qquad\displaystyle \mathbb{E}[T(X) \mid |X| = n] = \sum_{x\in\mathcal{X}_n} \operatorname{Pr}[X=x \mid |X| = n] \cdot T(x)$

given some random distribution for random variable $X$.

Average runtime is more specific and corresponds to

$\qquad\displaystyle \overline{T}(n) = \frac{1}{|\mathcal{X}_n|} \cdot \sum_{x\in\mathcal{X}_n} T(x)$

or, in other words, the expected runtime given a uniform distribution over inputs of the same size.

Since we usually use the uniform distribution the terms are often used interchangeably in algorithm analysis.

Strictly speaking, expectation is a property of a probability distribution whereas an average is a simple function computed from a set of numbers (typically, their mean).

However, in typical CS language, these terms are often confused. The "average running time" can either refer to the expected runtime when considering a random input, or in the case of randomized algorithms, it could mean the expected runtime given a specific input. In the latter case, the expectation is computed over all possible coin flips that the algorithm tosses.


Turing Machine-Like Formalism for The Actor Model Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.

The Actor Model is sometimes mentioned as a more powerful computational-model than Turing machines (not in what it can compute, but in other aspects).

Is The Actor Model a full fledged Turning machine alternative as a computational model?
Does The Actor Model also have such a symbol-based formal computation description akin to the Turing machine?
Are the actors assumed to be Turing machine equivalent - since each message is processed sequentially (and atomically)?

There are many theoretical results based on Turing machines, e.g. the halting problem, decidability, relation to Gödel's incompleteness theorem etc.

Can these proofs be formally generalize to the Actor Model? Has this been done?

computer scientists generally are of the consensus that the Church Turing thesis[1] is correct and definitive, ie that Turing machines describe computation, and that more powerful forms do not really exist, and take assertions that some model is "more powerful" than Turing machines with extreme skepticism, even near hostility.[2] neophytes to the field who dont fully understand the concept are prey to near-marketing slogans of some theory as "more powerful" than Turing machines but those claims are rarely made by mainstream/reputable computer scientists.

but as a flip side to this, many models of computation are Turing complete.
therefore in CS there is in practice mostly a tolerant, "live and let live" attitude with many different models of computation proliferating depending on what is most relevant and convenient for the problem studied. most basic programming models are Turing complete with basic structures such as memory, conditionals, and loops, subroutines etcetera. so more reasonable claims are, "model [x] is better suited to study [y] because [z]". the Actor model focuses on message passing, communication, concurrency & some security.

nevertheless there is some mostly philosophical debate in CS about some models being "more powerful".

[1] Church Turing thesis

[2] Interactive models of computing vs Church Turing thesis


Weak hashing function for memorable IPv6 addresses IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4.

There have been attempts to mitigate this, making IPv6 addresses somehow more memorable.

Is there an intentionally-weak hashing function which could be reversed to find that the phrase, say, "This is relatively benign and easy to spot if the phrase is bent so as to be not worth paying" would hash to a target IPv6 address?  The hash would, of course, have many colliding inputs to choose from, and a potentially more memorable sentence, such as this example phrase, could be automatically offered.

I guess there are two parts: First a weak hash with good distribution in both directions.  Second is an algorithm for selecting memorable phrases from among the many collisions (short, consisting of words from a specified language, perhaps even following a simplified grammar).

Although the hash function would need to be weak, I don't doubt that the effort is still significant - however, once the phrase is known, the computation of the hash to the target address is very quick.

EDIT

I found this related idea, Piphilology, for memorizing some digits of π:

  How I wish a drink, alcoholic of course, after the heavy lectures involving quantum mechanics!

Take the IP address and a wordlist. Then turn the IP address into a list of words from the wordlist based on the digits of the address, base {length of wordlist}.

So, for instance, taking the diceware wordlist and your example, I get: 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 -> mew hades cup viii 72 grit photo pick raid dey (or potentially the other way around, and/or padded on the other end).

Note this isn't lossy. Although you can relatively easily apply any lossy techniques to this. You may just wish to truncate the IP address, or only select every second bit or something before running it through this mapping.

It sounds like you have two use cases:

Given a phrase, it will hash to a unique IPv6 address
Given an IPv6 address, multiple phrases can hash to it (colliding inputs). Corollary: Given an IPv6 address, general multiple memorable phrases, which the user can choose from.

I believe you would have to roll your own solution here. IPv6 addresses are long enough that you probably have to use a function like SHA1 to be able to cover the address space.

To maximize the number of colliding phrases, you could try ignoring vowels, or the hundred most common words.


What is meant by the term 'state' in a finite-state machine? What is meant by the term 'state' in a finite-state machine?

I have not seen a proper definition on the web and am looking for a university-level answer.

Thank you in advance.

A state is simply an assignment of all possible variables of a system to values. A state transition then means a transition from one possible set of values of variables to another set of values.

To see how this might be useful, imagine a set of two switches $S$ and a light bulb $B$ that are connected to emulate some unknown logical gate. If you want to find out what that gate is, you can use a state machine model:

Say $I = \{S,B\} $

Initial State: $I = \{\{0,0\},0\}$

State transitions:

$\{\{0,0\},0\} \rightarrow \{\{1,0\},1\} \rightarrow \{\{0,1\},1\} \rightarrow \{\{1,1\},0\} $

It is evident that every state is just a set of different possible values of $I.$

By looking at the values of $B$ for a set of values of $S$, You can easily deduce that the system emulates a XOR gate.

If you have done some programming in some language , then the current executing instruction can be considered as the state in automata,

Like if you consider this python code :

print('Hello') - (A)
print('World') - (B)

then it simply going from A->B which will be giving you the output of "Hello World" on your console.

So you are going from one state to another on some input or terminating the automation if nothing is left to consume.


Good reference for average-case runtime analysis of QuickSort I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. Now, I need a good source from which I can read it and find the materials which I can include in my presentation. As for my existing knowledge on algorithms, one can assume that I almost know nothing except for "just codes" and nothing at all about their analysis. Any book or materials having rigorous proofs will also do. Any help will be greatly appreciated!

Given your stats background, you will find the "indicator variable" analysis easier than the solution via recurrence equations.
It is based on computing the probability that two elements of given ranks are compared to each other.

The idea is described on the wikipedia page
and in more detail in Section 7.4 of Cormen et al. Introduction to Algorithms 3rd edition.

Here's a cheat sheet for numerous algorithm implementations and their Average, Best, Worst case notations for Time/Space complexity for future reference. More so implementation of QS.


Encoding of graphs as an input to neural nets Given a directed graph $G=(V,E)$ with a node labelling function $l:V\rightarrow L$, how would you encode this best for a neural network?

If it simplifies the problem, we can add the following assumptions about $G$:

$|V|$ is of fixed size $n$.
Every node $v$ in $V$ has exactly two successors.
$l:V\rightarrow L$ is injective; in particular, instead of using node labels, a total ordering of the nodes would be good enough to "infer" the original graph labels.

What I'm trying to learn is a successor selection for every node $v$ in $V$; in other words, a map $m:V \rightarrow V$ with $m$ subset $E$.

Taking all assumptions into consideration, we more or less only have to encode $E$. Obviously, we could use a "two hot encoding" for every node $v$, resulting in a quadratic number of inputs, but is this the preferred way of going about it?

Thanks!

So I ask myself this question:

  Suppose 2 encoding contains the same amount of information, that is,
  all the information about the graph. What factor would make one
  encoding better than the other in terms of performance of neural nets
  (trained with the same number of iterations, etc)

The my personal answer to that is:

Trained neural net (in its simplest version) is just a linear function of its input. So, do you suspect that the function you want to learn can be expressed as a linear function of the input? And this is where the choice of encoding makes a difference.

My stance on these kind of algorithm is that. Ultimately, if you want it to perform well, you need to have a good hypothesis on what kind of function your answer should actually be.


What is the difference between a Neural Network, a Deep Learning System and a Deep Belief Network? What is the difference between a Neural Network, a Deep Learning System and a Deep Belief Network?

As I recall your basic neural network is a 3 layers kinda thing,
and I have had Deep Belief Systems described as being neural networks stacked on top of each other.

I've not til recently heard of a Deep Learning Systems, but i strongly suspect it is a synonym for Deep Belief System. Can anyone confirm this?

Artificial neural networks is a class of algorithms that include a lot of different kinds of algorithms based on graphs, so I won't detail here beyond what you asked because there's too much to say, since there are so many kinds of ANNs.

The first kind of artificial neural networks, the famous McCulloch-Pitts neurons, were linear, meaning that they could only solve linear decision problems (ie, datasets that could be linearly separable by drawing a line). Over time, this linear neural network model became known as the Perceptron or Adaline (depending on how you compute weights update).

Linear neural networks are just composed of a bipartite graph, where the left side nodes are the inputs and the right side nodes the output. Only the weights of the edges between these nodes are learnt (the nodes activation threshold can also be adjusted but this is rarely done).

A big step was taken when shallow neural networks were invented: instead of having only a bipartite graph, we use a 3partite graph: the input "layer", the output "layer", and one "hidden layer" between them. Thank's to the hidden layer, the network can now take non-linear decisions, and solve problems such as the canonical XOR.

Note that the "shallow" term was coined retrospectively when deep neural network (also called n-layers neural networks) were invented. This is to oppose neural networks with only one hidden layer, with deep neural networks with n hidden layers. As you can guess, using more hidden layers allow to decide on more complex datasets since there are more layers to modulate the decision (ie, in other words you're increasing the dimensionality of your decision boundary, which can lead to overfitting).

You may ask: why did no-one try to use multi-layered (deep) neural networks before? In fact, they did, as early as 1975 by Fukushima with the Cognitron and Neocognitron (which is in fact a convolutional neural network, but that's another story). However, the issue was that noone knew how to efficiently learn such networks, the big issue being the regularization. Hinton's AutoEncoders opened the way, and later the Rectified Linear Units of LeCun fixed the issue for good.

What about Deep Beliefs Networks (DBN)? They are just multi-layered semi-restricted Boltzmann machines. So they are a kind of deep neural network, but with a different basic network pattern (ie: the layer, this is the pattern that is repeated): Boltzmann machines are different from other networks in that they are generative, meaning that they are usually used to learn from your data to reproduce it ("generate" it), while usual deep neural networks are used to separate your data (by drawing a "decision boundary").

In other words, DNN are great to classify/predict a value from your dataset, while DBN are great to "repair" a corrupted data (when I say repair, it's not only from corrupted data, it can also be on a perfectly fine data that you just want to fix a little to be more stereotypical as to more easily recognize with another neural network, such as hand-written digits).

In fact, to neatly summarize, you can say that AutoEncoders are a simpler form of Deep Belief Network. Here is an example of a DBN trained to recognize faces but NOT numbers, the numbers are automatically faded away (this is the "fixing" effect of DBN):

So in the end, DBN and DNN are not opposite: they are complementary. For example, you can imagine a system to recognize hand-written characters that will first feed a character's image to a DBN to make it more stereotypical and then feed the stereotyped image to a DNN that will then output which character the image represents.

A last note: Deep Belief Nets are very close to Deep Boltzmann Machines: Deep Boltzmann Machines use layers of Boltzmann Machines (which are bidirectional neural networks, also called recurrent neural networks), while Deep Belief Nets use semi-restricted Boltzmann Machines (semi-restricted means that they are changed to unidirectional, thus it allows to use backpropagation to learn the network which is way more efficient than learning a reccurent network). Both networks are used for the same purpose (regenerating the dataset), but the computational cost is different (Deep Boltzmann Machines are significantly more costly to learn because of its recurrent nature: it is harder to "stabilize" the weights).

Bonus: about Convolutional Neural Networks (CNN), you will find a lot of contradictory and confusing claims, and usually you'll find that they are just deep neural networks. However, it seems the consensus is to use the original definition of Fukushima's Neocognitron: a CNN is a DNN that is forced to extract different features at different hierarchical levels by imposing a convolution before the activation (which a DNN can naturally do, but forcing it by setting a different convolution/activation function on different layers of the network may yield better result, at least that's the bet of CNN):

And finally, for a more rigorous timeline of Artificial Intelligence, see here.

Neural networks are normally implemented where hidden layers and quadratic equations are required.where as deep learning and deep belief networks are utilized where multiple hidden layers are required for manipulation of data just like deep Boltzmann networks.


Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences Given inorder and preorder (or postorder) traversal sequences of a

binary tree
balanced binary tree
binary search tree

of n nodes, what is the time complexity of creating the respective unique tree.

Assuming inorder and preorder sequences are given -

1. For binary tree : Starting with the root node, traverse the preorder sequence and for each node, binary search on the given inorder sequence, separating the left and right subtrees. Recurse on the next node with the new piece of the inorder sequence. Time complexity in worst case : T(n) = T(1) + T(n-1) + O(logn) = O(nlogn)

2. For balanced binary tree : Follow the same procedure as in 1. But, since the tree is balanced, the time complexity in worst case is different: T(n) = 2T(n/2) + O(logn) = O(n)

3. For binary search tree : Traverse the preorder sequence and at each node, keep a flag (=key of the parent node). If the next node in the sequence is less than the flag, then the node gets to be the left or right child of the current node. Else, we go back to the parent recursively and apply the same procedure to it. Time complexity = O(n) since we are creating nodes in the preorder sequence.


Why is the unit of image size not Pixel²? If you calculate the area of a rectangle, you just multiply the height and the width and get back the unit squared.
Example:
5cm * 10cm = 50cm²

In contrast, if you calculate the size of an image, you also multiply the height and the width, but you get back the unit - Pixel - just as it was the unit of the height and width before multiplying.
Example:
What you actually calculate is the following:
3840 Pixel * 2160 Pixel = 8294400 Pixel

What I would expect is:
3840 Pixel * 2160 Pixel = 8294400 Pixel²

Why is that the unit at multiplying Pixels is not being squared?

Because "pixel" isn't a unit of measurement: it's an object. So, just like a wall that's 30 bricks wide by 10 bricks tall contains 300 bricks (not bricks-squared), an image that's 30 pixels wide by 10 pixels tall contains 300 pixels (not pixels-squared).

It happens when you multiply units. Pixel is not a unit. You can do that with Pixel per Inch etc. but not with the pixel alone.


Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions? I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says :

  In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations $...$ These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path

Assume we have a Non-deterministic algorithm for (SAT), does that mean the algorithm will show some computational paths leading to incorrect solutions (Non Satisfying Assignments) and other computational paths leading to correct solutions (Satisfying Assignment) ?

Or it is supposed to show only the correct solutions ?

Usually, when one develops an algorithm, there is a proof of correctness. From what I know, "nondeterministic" means the algorithm may or may not give you the correct answer, but it will definitely not give you an incorrect one.


Who converts binary/machine code to electrical signals and how? I went through lots of blogs and posts but could not exactly figure out how the machine code is converted to electrical signals?

Any software program is compiled to machine code which is nothing but lots of 1s and 0s.
1 means high voltage e.g 5V and 0 means comparatively low voltage e.g. 0V or ground, what's the component which understands that okay I got 1(one) so I need to step up up the voltage to 5V and for 0(zero) I need to step down to lower voltage level and how it does that?

In old computer you actually had a row of switches on the front panel
that would allow entering 1s and 0s directly by hand in the registers
of the machines. But this is no longer done.

You never have 1s and 0s, unless you ask the machine to print its
internal information as a sequence of 1s and 0s. All information is
already in the machine encoded as voltage, or magnetic orientation, or
hole in a physical substrate, or some other physical form. Various
devices can perform the translation between these form: magnetic
heads, laser beams, electro-mechanical devices, electronic
circuits,etc.

Some form are better adapted at memorizing or transmission by various
means, while other (electrical signal notably) are better adapted at
processing, usually by complex systems of logical gates (and, or, not,
xor ...) and micro-memories (registers).

In general, binary/machine code is no longer entered by human beings,
but produced by a program (usually a compiler) by the computer itself,
or by another computer and then imported on some memory support or by
network. However, human beings can ask to have it printed as 1s and 0s
to check what the computer is using or producing. However this
requires transforming the single bit 0 or 1 in the computer as a
stream of bits to be interpreted by the printer as a request to print
an actual drawing (on screen or paper) od the symbol representing a 0
or a 1.

It is hard to give more details without your being more specific
regarding the source form and target form of the conversion. But it is
most often from binary to binary, with a different physical
representation.

Every thing you write on a text editor, first, it is stored in a memory (electric signals generated from the keybord) no matter in which code (ascii,...). From memory, those signals are fed into the computer monitor and you can see the source code you are typing. Then, you run your compiler (or assembler) that reads the source code in memory (electric signals) and converts it to machine code, storing those transformed electric signals in another region of the memory (electric signals again). When the cpu reads the machine code, what it sees are electric signals. There is no logic levels, so there is no need to convert logic level in voltage level.


Bridge theorems for group theory and formal languages Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines?

I am looking for references/applications. However note that I am aware of the link between semigroups and CS languages (namely via finite automata). (Does this literature on semiautomata ever look at "group-automata"?)

I have seen one paper many years ago that might come close, that converts TM transition tables into a binary operation, possibly sometimes a group in some cases, conceivably based on some kind of symmetry in the TM state table. It didn't explore that in particular, but also didn't rule it out.

Also, in particular, regarding the large body of math research on classification of finite groups, does or could it have any meaning or interpretation in TCS? What is the "algorithmic lens" view of this massive edifice of mathematical research? What is it "saying" about a possible hidden structure in computation?

This question is partly inspired by some other notes e.g.:

Use of algebraic structures in TCS
RJ Lipton on Gromov's theorem

Let me first answer your subquestion: Does the literature on semiautomata ever look at "group-automata"?. The answer is yes. In his book (Automata, languages, and machines. Vol. B, Academic Press), S. Eilenberg gave a characterization of the regular languages recognized by finite commutative groups and $p$-groups. Similar results are known for finite nilpotent groups, soluble groups and supersoluble groups.

Finite groups also play an important role in the problem of finding a complete set of identities for regular expressions. An infinite complete set was proposed by John Conway and this conjecture was ultimately proved by D. Krob. There is a finite number of "basic" identities, plus an identity for each finite simple group. See my answer to this question for references.

In the opposite direction, finite automata theory lead to an elementary proof of basic results on combinatorial group theory, like the Schreier formula. Based on Stallings's seminal paper Topology of Finite Graphs.

Also in the opposite direction, automatic groups are defined in terms of finite automata.

Profinite groups also play an important role in automata theory. An example is the characterization of the regular languages recognized by transition-reversible automata with
possibly several initial and final states.

For a very nice connection between context-free languages, groups and logic, see the article
by David E. Muller and Paul E. Schupp, Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems.

With Google, I found the paper Relatively free profinite monoids: an introduction and ex-
amples, in Semigroups, Formal Languages and Groups by Jorge Almeida (English translation in Journal of Mathematical Sciences, 144(2):3881–3903, 2007) on this subject.


Conceptual overview: Self-information, Mutual information, uncertainty, entropy I would like to have a compact conceptual explanation that allows me to gain some feeling with the concepts. The following list uses $x_i, y_i$  as events of experiments $X, Y$.

Self-information, denoted as $I(x_i)$
Mutual information, denoted as $I(x_i; y_i)$
Uncertainty (which is closely related to self-information and/or mutual information, I believe).
Average mutual information, denoted as $I(X, Y)$.
Entropy, denoted as $H(X)$, which is average self-information, I believe.

Next, there are a couple of "conditional ..." defined.

Can you sketch a compact overview of these concepts and how they relate, all intuitively?

Trying to answer the question myself, with my textbook at hand. So far, I am here:

Self-information of an event: uncertainty of an event.
$$I(x_i) = \log \frac{1}{P(x_i)} = -\log P(x_i)$$
Self information of a vector event:
$$I(x_i y_i) = -\log P(x_i,~y_i)$$
Mutual information between two events: the information one event (experiment outcome) gives us about the other event:
$$I(x_i;y_i) = \log \frac{P(x_i,~y_i)}{P(x_i) P(y_i)}$$
$$I(x_i y_i) = I(x_i) + I(y_i) - I(x_i; y_i)$$
Uncertainty: the formula of it is the same as self-information of an event. So I'll assume they are the same.
Average mutual information: The information one gives about the other when observer the former. Clumsy notation:
$$I(X; Y) = E[I(x_i; y_i)]$$
Entropy: the average amount of information that is revealed by observing an event. (I know the relationship to Huffman coding here.) Clumsy notation:
$$H(X) = E[I(x_i)]$$
Conditional entropy: the amount of information (about $X$) that is left to be discovered after observing the given ($Y$).
$$H(X|Y) = H(X) - I(Y;Y)$$

\begin{align}
I(X; Y) &= H(X) - H(X | Y) \\
\text{mutual} &= \text{a priori} - \text{a posteriori}
\end{align}

Conditional self-information: the information that is contained within the outcome of a certain event ($x_i$), after already knowing the outcome of another event ($y_i$).
$$I(x_i | y_i) = -\log P(x_i | y_i)$$
Relations:
$$I(x_i | y_i) = I(x_i) - I(x_i; y_i)$$
\begin{align}
I(x_i; y_i) &= I(x_i) - I(x_i | y_i) \\
\text{mutual} &= \text{a priori} - \text{a posteriori}
\end{align}

conditional self information is the modified version of self information in which we see the amount of information carried out by X(i) in the presence of Y(i)

                      I[x(i)|y(i)]=  -log[x(i)|y(i)]


Origins of the Segment tree data structure I'm interested in the first appearance in the CS literature of the data structure described here which is used to answer Range Queries. Although I have come across the same data structure many times with the name segment tree (mostly in algorithmic competition sites), it seems that the same name is also used for this data structure which is quite different from the first one and has application in computational geometry.

I'd like to know who introduced the data structure described in the TopCoder tutorial and if another name was initially used as there seems to be a confusion between the two data structures that go by the same name.

It seems to me that the Segment tree in the Wikipedia article is exactly the same as the segment tree you're used to hear about.

Segment trees as used in programming competitions can be generalized as working over any data type which forms a Semigroup (that is, any data type over which some binary associative operation can be defined on). As a reference, I've been implementing them in Haskell, the source code can be found here.

In this particular case, you'd have to notice that the power set of a set forms a commutative monoid with union, and monoids are, in particular, semigroups. Hence, the particular case described in Wikipedia is a segment tree where the data type is an Interval, and the associative operation is the union operation!.

Segment trees are a form of binary trees. So to clarify your question, the data structures in both links are the same. They might be used in different ways or for different operations but they are in fact the same. I do not know who introduced the "segment tree" use of binary trees, but I hope this helps.


Is it NP-hard to fill up bins with minimum moves? There are $n$ bins and $m$ type of balls.
The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$.

You start with $b_j$ balls of type $j$. Each ball of type $j$ has weight $w_j$, and want to put the balls into the bins such that bin $i$ has weight $c_i$. A distribution of balls such that previous condition holds is called a feasible solution.

Consider a feasible solution with $x_{i,j}$ balls of type $j$ in bin $i$, then the cost is $\sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}|$. We want to find a minimum cost feasible solution.

This problem is clearly NP-hard if there is no restriction on $\{w_j\}$. The subset sum problem reduces to the existence of a feasible solution.

However, if we add the condition that $w_j$ divides $w_{j+1}$ for every $j$, then the subset sum reduction no longer works, so it's not clear whether the resulting problem remains NP-hard. Checking for the existence of a feasible solution takes only $O(n\,m)$ time (attached at the end of the question), but this does not give us the minimum-cost feasible solution.

The problem has an equivalent integer program formulation.
Given $a_{i,j},c_i,b_j,w_j$ for $1\leq i\leq n,1\leq j\leq m$:
\begin{align*}
\text{Minimize:} & \sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}| \\
\text{subject to:} & \sum_{j=1}^m x_{i,j}w_j = c_i \text{ for all } 1\leq i\leq n\\
& \sum_{i=1}^n x_{i,j} \leq b_j \text{ for all } 1\leq j \leq m\\
& x_{i,j}\geq 0 \text{ for all } 1 \leq i\leq n, 1\leq j \leq m\\
\end{align*}

My question is,

  Is the above integer program NP-hard when $w_j$ divides $w_{j+1}$ for all
  $j$?

An algorithm to decide if there is a feasible solution in $O(n\,m)$ time:

Define $w_{m+1}=w_m(\max_{j} c_j + 1)$ and $d_j = w_{j+1}/w_j$. Let $a\%b$ be the remainer when $a$ is divided by $b$.

If there exists a $c_i$ that's not divisible by $w_1$, return "no feasible solution". (the invariant $c_i$ divides $w_j$ will always be maintained in the following loop)
for $j$ from $1$ to $m$:

$k \gets \sum_{i=1}^n (c_i/w_j)\%d_j$. (the minimum of balls of weight $w_j$ required)
If $b_j<k$, return "no feasible solution".
$c_i \gets c_i - ((c_i/w_j)\% d_j)$ for all $i$. (remove the minimum number of required balls of weight $w_j$)
$b_{j+1} \gets \lfloor (b_j-k)/d_j \rfloor$. (group smaller balls into a larger ball)

return "there is a feasible solution".

A polynomial time solution to the special case where $n=1$, and $w_j$ are power of $2$s

It is known that if $n=1$ and all $w_j$ are powers of $2$, then this special case can be solved in polynomial time.
\begin{align*}
\text{Minimize:} & \sum_{j=1}^m |a_j-x_j| \\
\text{subject to:} & \sum_{j=1}^m w_j x_j = c\\
& 0 \leq x_j \leq b_j \text{ for all } 1\leq j \leq m\\
\end{align*}

The solution was hinted at by Yuzhou Gu, and a write up may be found here.

Some background.  The above problem is the knapsack problem with restrictions.  The most efficient knapsack problem solution with or without restrictions can be solved in pseudopolynomial time, still NP-Hard.  For some variations, see https://en.wikipedia.org/wiki/Knapsack_problem#Definition.  The first restriction in this variation is that the value of items (balls) to be placed in the knapsack (bins) does not matter.  The problem is then restricted to the amount of time it takes to put the items in the knapsack.  The original problem requires the most valuable items to be placed in as short amount of time possible.  Another restriction with this version is that the weights and all other arguments are integers.  And the restriction of interest is that the weights $w_j$ divide $w_{j+1}$ for all $j$.  Note: the fractional knapsack problem can be solved in polynomial time, but does not present the most practical solutions to the original problem.  This problem uses integers that divide evenly (no rational solutions).  Perhaps see What's the big deal with the knapsack problem?.

The main question perhaps should be "is this problem still NP-Hard when $w_j$ is unbounded by a polynomial corresponding to $i$, as the problem is less complex (in P) when it is bounded?  The reason I say this is because the problem can be shown to be in P when $w_j$ is bounded and NP-Hard when $w_j$ does not necessarily divide $w_{j+1}$ evenly (the weights are simply random), all restrictions limit the complexity of this problem to these two conditions.  These conditions (1. the random weight knapsack problem without the item-value restriction and 2. divisible weight knapsack problem without the item-value restriction) negate each other in terms of reducing complexity, as the quotients of the weights may be random themselves (especially when unbounded), thus imposing exponential time calculations (this will be shown in the example below).  Additionally, because $w_j$ divides $w_{j+1}$, $w_j$ increases in size exponentially for each $j$.  This is because instead of using random weighted items (balls whose unit weight may all be limited to unit weights under 100 or 50 or even 10), the restriction instead causes the time complexity to depend on the number of digits of $w_j$, the same as trial division, which is exponential.

So yes, the above integer program remains NP-hard even when $w_j$ divides $w_{j+1}$ for all $j$.  And this is easily observed.

Example 1: let $n = 1$ and $w_p$ be powers of two.  Because of constant two, the entire problem is solved in quadratic time, as your example shows.  The weights are not random and therefore the calculation is solved efficiently.

Example 2: let $w_{j+1}$ be defined as $w_j * p$, where $p$ is the prime number corresponding to $j$, such that $p=2, j=1: p=3, j=2, p=5, j=3, p=7, j=4,...,P, J$.  This is applicable, as $w_j$ divides $w_{j+1}$ for all $j$.  We get each $w_j$ is the product of all the primes up to $j$.  The values of the unit weights increase as such: $1, 2, 6, 30, 210, 2310, 30030, ...$.  Since there is a bound ($p_j$ ~ $j log (j)$, via the prime number theorem), as the quotients are all primes, we get the complexity NP-Intermediate.

Example 3: let $w_{j+1}$ be defined as $w_j * R_p$, where $R_p$ is a randomly chosen prime number from two to infinity, corresponding to $j$.  This is applicable to this problem, as $w_j$ divides $w_{j+1}$ for all $j$.  We get the first 5 quotients (randomly falling from two to infinity), as $101, 2657, 7, 3169, 2$.  We see that even at the 5th ball, the weight has eleven digits.  Fortunately, the fifth quotient was two and not a prime in the order of $10^{100}$ or larger.

Example three above is what happens when $w_j$ is not bounded (random weights) by a polynomial corresponding to $i$.  The time complexity is exponential, NP-Hard.  For some perspective, just add up all the weights, see if they fit. But there isn’t a solution to solving it significantly faster by making the weights divisible than trying each subset to see if it works. After a few dozen balls, you are still entering the realm of even the trillions of subsets or trillions of digits.


Is it possible to prove that this algorithm is big Omega $n^2logn$ time complexity? Considering the following recursive algorithm:
$ T(n)= T(\frac{n}{2})+c_1(\frac {n}{2})^2+c_2n$.
I was able to prove that this algorithm is $O(n^2 logn)$
I was trying to understand whether it is a tight bound or not, yet I was unable to prove that $ T(n)\in \Omega(n^2logn)$
Is it possible or maybe the algorithm's lower bound is $n^2$ ?
Any assistance would help a lot as I am trying to crack this for a while now.

Your recurrence can be written as:
$
T(n) = T(n/2) + f(n)
$, where $f(n) \in \Theta(n^2)$.
Then, by case 3 of the Master theorem, you have $T(n)=\Theta(n^2)$. This means that you won't be able to prove a lower bound of $\Omega(n^2 \log n)$.

Your “algorithm” runs in O(log n) time. The function that it calculates is O(n^2).


How can a computer deal with real numbers Computers are an exceptionally powerful tool for various computations, but they don't excel at storing decimal numbers. However, people have managed to overcome these issues: not storing the number in a decimal format, which is limited to very few decimal places, but as an integer instead, while keeping track of the number's precision.
Still, how can a computer simplify computations just like humans do? Take a look at this basic  example
$$\sqrt{3} \times (\frac{4}{\sqrt{3}} - \sqrt{3}) = \sqrt{3} \times \frac{4}{\sqrt{3}} - \sqrt{3} \times \sqrt{3}  = 4 - 3 = 1$$
That's how a human would solve it. Meanwhile, a computer would have a fun time calculating the square root of 3, diving 4 by it, subtracting the square root of 3 from the result and multiplying everything again by the square root of 3.
It would surely defeat a human in terms of speed, but it would lack in terms of accuracy. The result will be really close to 1, but not 1 exactly. A computer has no idea that, for instance, $\sqrt{3} \times{\sqrt{3}}$ is equal to $3$. This is only one of the uncountable examples out there.
Did people already find a solution, as it seems elementary for mathematics and computations? If they didn't, is this because it didn't serve any purpose in the real world?

Sage is an open source computer algebra system. Let's see if it can handle your basic example:

sage: sqrt(3) * (4/sqrt(3) - sqrt(3))
1

What is happening under the hood? Sage is storing everything as a symbolic expression, which it is able to manipulate and simplify using some basic rules.
Here is another example:

sage: 1 + exp(pi*i)
0

So sage can also handle complex numbers.
Computers never handle real numbers, since real numbers cannot be represented exactly on a computer. Instead, they either handle approximate representations of real numbers (usually floating point numbers but sometimes fixed point numbers), or they represent real numbers symbolically, as in the example above. Sage can convert between the two representations (in one direction!), and it can handle floating point numbers of arbitrary accuracy. For example,

sage: RealField(100)(pi^2/6 - sum(1/n^2 for n in range(1,10001)))
0.000099995000166666666333333336072

This computes $\pi^2/6 - \sum_{n=1}^{10^4} 1/n^2$ to 100 bits of accuracy (in the mantissa).
Another approach worth mentioning is interval arithmetic, which is a way of computing expressions with a guaranteed level of accuracy, using provable error brackets. Interval arithmetic is used in computational geometry, together with exact representation of rational numbers.
In theoretical computer science there are several other notions of real computation, but they are mostly of theoretical interest. See the answers to this question.

Most people use a compiler, which creates operations with floating point numbers (which are not real numbers).
There are specialised tools that will try to manipulate formulas in symbolic form, and they can do exactly what a human can do. You can even do it yourself to sum degree, in any OOP language you can create objects that represent a number as the sum of rational numbers times square roots of integers for example, implement +, -, *, / and you will get exactly what you are asking for.
In principle, question like yours can always be answered by saying "either the designer of the processor adds hardware that does what you want, or some software developer creates software to do it". (Or nobody is bothered doing it, sometimes because it is too difficult, and in some cases it's impossible, but those impossible problems are impossible for humans as well).


Why are there so many programming languages? I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with the scripting capabilities of awk/sed/perl.

But why are there so many different programming languages ? I'm guessing all these languages can do the same things, so why not just stick to one language and use that for programming computers ? In particular, is there any reason I should know a functional language as a computer programmer ?

Some related reading:

Why new programming languages succeed -- or fail ?
is there still research to be done in programming languages?

Programming languages evolve and are improved with time (innovation).

People take ideas from different languages and combine them into new languages. Some features are improved (inheritance mechanisms, type systems), some are added (garbage collection, exception handling), some are removed (goto statements, low-level pointer manipulations).

Programmers start using a language in a particular way that is not supported by any language constructs. Language designers identify such usage patterns and introduce new abstractions/language constructs to support such usage patterns. There were no procedures in assembly language. No classes in C. No exception handling in (early) C++. No safe way of loading new modules in early languages (easy in Java). No built-in threads (easy-peasy in Java).

Researchers think about alternative ways of expressing computations. This led to Lisp and the functional language branch of the language tree, Prolog and the logic programming branch, Erlang and other actor-based programming models, among others.

Over time, language designers/researchers come to better understand all of these constructs, and how they interact, and design languages to include many of the popular constructs, all designed to work seamlessly together. This results in wonderful languages such as Scala, which has objects and classes (expressed using traits instead of single or multiple inheritance), functional programming features, algebraic data types integrated nicely with the class system and pattern matching, and actor-based concurrency.

Researchers who believe in static type systems strive to improve their expressiveness, allowing things such as typed generic classes in Java (and all of the wonderful things in Haskell), so that a programmer gets more guarantees before running a program that things are not going to go wrong. Static type systems often impose a large burden on the programmer (typing in the types), so research has gone into alleviating that burden. Languages such as Haskell and ML allow the programmer to omit all of the type annotations (unless they are doing something tricky). Scala allows the programmer to omit the types within the body of methods, to simplify the programmer's job. The compiler infers all the missing types and informs the programmer of possible errors.

Finally, some languages are designed to support particular domains. Examples include SQL, R, Makefiles, the Graphviz input language, Mathmatica, LaTeX. Integrating what these languages' functionalities into general purpose languages (directly) would be quite cumbersome. These languages are based on abstractions specific to their particular domain.

Without evolution in programming language design, we'd all still be using assembly language or C++.

As for knowing a functional programming language: functional languages allow you to express computations differently, often more concisely than using other programming languages. Consider about the difference between C++ and Python and multiply it by 4. More seriously, as already mentioned in another answer, functional programming gives you a different way of thinking about problems. This applies to all other paradigms; some a better suited to some problems, and some are not. This is why multi-paradigm languages are becoming more popular: you can use constructs from a different paradigm if you need to, without changing language, and, more challengingly, you can mix paradigms within one piece of software.

They weren't, it's just a marketing gimmick-- if you make the language kinda sorta look like "C", then that lowers the apparent barrier to entry.

Some that have no C influence at all:  SQL, Pascal, Delphi, FORTRAN, COBOL, Ada,  PowerBuilder, HyperTalk, Lisp, Simula, FOCAL, BASIC, PL/I, Algol, Algol-68, SNOBOL, Modula,  Visual BASIC,  Tutor, logo, Forth, DIBOL, Helix, AppleScript, Python, Erlang, Ruby, Pick, English, RPG, PL/SQL, ASP, Prolog, SmallTalk, Perl, bash, Wand BASIC, REXX, DOS batch language.

Those that kinda LOOK like C, but have very little in common with it:  JavaScript, Java, C#, (arguably) Objective-C.

It's all marketing, Java, C++, and JavaScript kinda looks like C, but could hardly be more different under the covers.


Can a petri net fire only one transition at a single moment? After reading several articles about petri nets, I am confused on how firing works. Can Petri net system fire only one transition out of all active (fire-able transitions) at a single moment? Or are multiple transitions allowed to fire at a single moment?

Both.

Only one transition being able to fire at a time is known as interleaving semantics. Multiple transitions firing simultaneously is known as step semantics. Some people doing concurrency theory only call the latter real concurrency, and they care deeply about the difference; I'm sure the difference has consequences, but I've worked with Petri nets and I've never run into a situation where it mattered.

In a Petri net editor I used to work on, durations could be assigned to transitions - so these "transitions" represent tasks or processes that take a certain time. Once that is possible, clearly it makes a great difference whether two of them can be firing at the same time or not. But I would say such "timed transitions" really aren't transitions; rather, they are shorthands for a transition (start), a place (executing), and another transition (termination).

How many transitions fire at once depends on the interpretation assigned to the Petri Net.

If you want more than one transition to fire at once, you should consider:

1. Will the transitions fire using one processor?

This is fine. A Petri Net can handle this type of firing because the transitions actually fire one at a time. Consider the Petri Net in the following diagram:

Let m0 be the mark in place P0. Consider the firing rule for T1: m0 = m0 - 1,and the firing rule for T2: m0 = m - 1. It is easy to check if a transition is enabled before firing the transition.

2. Will each of the transition to fire use a different processor?

This is probably not fine. Using the same example above, consider a processor is responsible for firing T0 and another processor is responsible for firing T2. Each processor checks if its transition is enabled. If it is enabled, the processor fires the transition. Each check may indicate that the transition is enabled. So each processor will proceed to fire the transition. Depending on when each processor reads m0  and writes the computed value of m0, the value of m0 may be 0 or -1.

Postscript

A PDF version of the original answer may be found at http://www.aespen.ca/AEnswers/1416178160.pdf (and the equations are much better to look at). The modifier answer may be found at http://www.aespen.ca/AEnswers/1416975962.pdf.


Why does a Turing machine recognise exactly one language? I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?

The language recognized by a Turing machine is, by definition, the set of strings it accepts. When an input is given to the machine, it is either accepted or not. Any particular input to that machine is either always accepted (in the language) or always not accepted (not in the language). So there's no mechanism by which a single Turing machine even could accept more than one langauge.

no other answers point out the existence of the Universal Turing Machine(s) as first described/ discovered by Turing in his halting proof. yes a TM accepts a single recursively enumerable language, but the UTM can recognize any recursively enumerable language if it is encoded on the input along with the input string. so the question has some zenlike quality. TMs both accept only a single language and all possible encodable languages.


(Non) Context Free language? In an exam question it is asked to identify if the given language is Context-Free, Non Context Free or Regular.
This is the question :

In my opinion this language is not a CFL since w doesn't belong to L', meaning that it belongs to not(L') which is all words (a^n b^n c^n) which is not CFL.

Apparently my answer is not right and I really don't understand why... Is this question a "trap" because i,j,k > 0 and not >= ? Meaning that a word (b^n c^n) is in L ? Looks like I'm lost !

I really need your help and explantions.

Thanks in advance.

It helps to think of $L$ as having two parts.

First part: $L_1$ is all strings not in the form $a^i b^j c^k$. We can write this with the regular expression $\neg [a^* b^* c^*]$, so it's regular.

(I've been informed this notation isn't universal, so to spell it out: it's the complement of the regular language $a^* b^* c^*$, and the complement of a regular language is regular.)

Second part: $L_2$ is all strings in the form $a^i b^j c^k$ such that the given conditions on $i, j, k$ are not fulfilled.

The given conditions are that $i, j, k$ are all different. So how can those conditions be violated? Either $i=j$, or $j=k$, or $i=k$. We can call these three options $L_{2a}$, $L_{2b}$, and $L_{2c}$ if you want.

Let's take just one of them as an example; the others work the same way. $L_{2a}$ is all strings of the form $a^i b^i c^k$. Can you write a regular expression for this? How about a CFG? (The answers are no, and yes: in fact, this is one of the classic examples for what a CFG can do that a regular expression can't.)

Now, since $L_{2a}$, $L_{2b}$, and $L_{2c}$ are all context-free, their union ($L_2$) is also context-free. And since $L_1$ is regular, it's also context-free. So $L$, as the union of two context-free languages, is context-free.

Not L' isn't just all words a^nb^nc^n, it also contains words that don't fit the a^nb^mc^k pattern, like "cab" or "bac", etc. It also contains the words a^nb^nc^m, etc. Try writing a CFG for it.


Symbolic Evaluation for Type Inference in a Dynamic Language Say I have the following contrived example code:

a(1)

function a(x) {
  var n = b(x)
  var m = c(x)
  return n + m
}

function b(x) {
  var n = d(x / 2)
  var m = e(x)
  return n - m
}

function c(x) {
  var n = d(x)
  var m = e(x)
  return n * m
}

function d(x) {
  return x + 2
}

function e(x) {
  return x + 3
}

Then, I am analyzing the method d(x). From just analyzing it by itself, we can infer that x must be some sort of number. We do this by what seems like simulating x + 2, and realizing that for that to be satisfied x must be a number. Not quite sure how to implement the type inference here, not sure if it uses symbolic evaluation too.

But then we get to the function call a(1). In this case to do typechecking / type inference on d(x), we have to somehow traverse down the tree of functions, simulating how x is transformed along the way. It finds out that it is divided by 2 somewhere in there, so it goes from integer to float. So we check based on our original assumption that d(x) is a number, and agree that it will be valid.

That is just me roughly trying to figure out how to do type checking / type inference.

I'm wondering two things:

If you need to do some sort of symbolic evaluation to do type checking / inference. If so, any suggestions on resources or places/ways to better understand that.
Say we have a gigantic app with millions of lines of code. Say between a(x) and d(x) there were 500 function calls, doing all sorts of things to x. Wondering if we have to simulate that entire process to figure out if x will be a valid type, or if we can somehow limit the scope and do some sort of shortcut. If we had to traverse the 100's of functions for every variable, that would be a ton of evaluation and would be slow. So wondering how to limit the scope of the search somehow, to do type checking / inference.

Basically I am figuring out how to do type checking / inference. The resources are mostly on the lambda calculus from what I've found, which I am not too familiar with and works differently I would imagine than an imperative program.

For example, they seem to be mentioning that here:

  (1) 3.2 Type Graph

  After each method has been converted into its intermediate
  representation, zscript gradually builds a type graph by each
  method called by the program.
  The CPA is non-iterative. Only the methods that could
  potentially be called are processed, and (except for templates)
  they are only processed one time only.
  In our implementation of the algorithm, we use a work list. First,
  the constructor of the class containing the main method, and the
  main method itself is added to the work list. Then, while the
  work list is not empty, the methods of the work list are
  processed. During the processing of a method, more methods
  may be added to the work list. The algorithm terminates when no
  more methods remain to be analyzed.

I am not sure you actually understand the terms you use here.

Symbolic execution has nothing to do with type inference

Symbolic execution is used for static analysis of programs, and is a special case of abstract interpretation. The symbolic executor provides an symbolic input value and traces the program execution given that symbolic input value.

Type inference is much simpler: it involves automatically deducing the type of programs. Nowhere is symbolic execution of the program involved.

Type inference is usually undecidable

For a dynamic typed language, type inference is not decidable. Moreover, even we have a static type system, type inference is usually still undecidable.

The only (?) type system we know of that has decidable type inference is the Hindley-Milner type system, i.e. System F with only Rank-1 types (plus a few conservative extensions). It is known that H-M can type imperative programs (such as Standard ML), as long as you can give good typing rules. When I was an undergraduate, we did an exercise in which we implemented H-M type inference for a restricted, strongly-typed version of Scheme (which was imperative). It was a lot of fun, but it also proves that
type inference is possible for imperative programs.

Update: oh, how could I have left out the canonical reference for polymorphic, inferable typing of imperative programs? The canonical reference would be Xavier Leroy's PhD thesis, Typage polymorphe d'un langage algorithmique (translated into English as Polymorphic typing of an algorithmic language).

I suggest that you start reading on Hindley-Milner and Algorithm W, as a first step (see, e.g., Chapter 22 of Types and Programming Languages by Benjamin C. Pierce). I also suggest that you do more basic reading and learning before asking on CS.SE, as that would make this site work much better. The theory of programming languages is not like coding and must be studied systematically if you want to have a solid grasp of it :-)

First, let us assume the + operator is actually a function.

Secondly, suppose there are one and only one definition for the + function, and its type signature is (Number , Number) -> Number, i.e. the + function will 2 Number as input and return a Number as output.

Based on all this assumption, whenever we see an invocation for + , let say x + 2, then we can properly infer that x is type of Number, since there are only one definition for +.

However, if we have 2 definitions for + , as seen in the function table below:

|=====|================|============================|==========================|
| No. | Representation | Type signature             | Usage                    |
|=====|================|============================|==========================|
|  1  | `+`            | (Number, Number) -> Number | For addition             |
|=====|================|============================|==========================|
|  2  | `+`            | (Number, String) -> String | For string concatenation |
|=====|================|============================|==========================|

In this case, it would still be possible to identify the type of x in the expression x + 2, because the first argument for every definition of + is always Number.

But, if the expression is 2 + x, it would be impossible to accurately determine the type of x, as it maybe Number or String, if the language support union type, then the type of x can be inferred as Number|String.

Hope that helps :)


Why don't modern SAT solvers use the notion of a "watched clause", in the same way they use the notion of a "watched literal"? Modern SAT solvers use the notion of "watched literals": when a value is chosen for a literal $l$, the solver only checks whether that falsifies clauses with $l$ in them if $l$ is one of the watched literals in the clause. This prevents checking every clause for every newly assigned literal.

The correctness of the scheme comes from the fact that clauses are disjunctions and will only be false if all literals in it are false. So we know it is not false until at least the watched literal is false, and we only need to check when that happens.

I am wondering why the dual idea of a "watched clause" is not used as well. This is how it would work: the overall formula is a CNF, that is, a conjunction of clauses. The watched literal scheme already checks very fast whether the CNF has become false. However, it would also be useful to detect when it becomes true: no further search would be needed then. A conjunction is only true if all clauses in it are true. So we choose one "watched clause" $C$ and, if a literal in $C$ is assigned a value, we check to see if $C$ has turned true. If so, we mark that clause as now irrelevant, and pick another clause not yet satisfied. If we cannot find a not-yet-satisfied clause, all clauses are satisfied and the problem is satisfiable.

I realize this would require keeping track of more information; assigning to literals would now not only require checking if they are watched literals, but also if they are in the watched clause. More importantly, looking for a new watched clause requires checking if other clauses are not yet satisfied, which means checking all their literals. Depending on the structure of the problem instance, this could be much slower. However, for some instances (for example, problems with small clauses) this would be much faster because satisfaction would be detected much sooner.

So my question is whether this is not used simply for empirical reasons (say, it would be slower for most benchmarks), or if there is a deeper flaw about it that I am missing.

A secondary question is: if this is a merely empirical issue, then is there some simple argument predicting this from the description of the technique alone, or is it something that would need to be observed in practice? Or, in other words, if this is a bad idea, is it so in principle, or just empirically?

Addendum:

It has been suggested by an answer that the notion of watched literals implies the use of DPLL which implies tracking which clauses have been satisfied, and that therefore the question does not make sense. It is true that watched literals are used in the context of DPLL, but it is not true that this means tracking satisfied clauses.

The paper on Chaff, which defined watched literals, describes DPLL in pseudo-code as

while (true) {
    if (!decide()) // if no unassigned vars
        return(satisifiable);
    while (!bcp()) {
        if (!resolveConflict())
            return(not satisfiable);
    }
}

This shows that satisfiability is decided as positive only when all variables are assigned, not when all clauses are satisfied (which could happen much earlier). Chaff and zChaff have been the basis for many of modern SAT solvers, including the very prominent MiniSAT.

The same idea is described in detail in Filip Maric's paper "Formalization and Implementation of Modern SAT Solvers", which describes this approach as the basis for many of the most prominent SAT solvers today.

A typical SAT solver notices that a satisfying assignment has been found when there are no more variables to assign.  So the only time that a SAT solver would save by early notification is the time it would take to assign values to any remaining unassigned variables.  This is a one-time cost linear in the number of variables in the formula.  It's linear because there can be no backtracking once the formula is solved.

Meanwhile, to maintain your watched clause pointer you must do a search to find a new unsatisfied clause each time your watched clause is satisfied.  That search is linear in the number of clauses in the formula.  These searches will be triggered during the exponential part of the search and so you will probably do many of them on your way to finding a satisfying assignment.

The net result is that you will waste more time than you will save trying to immediately notice when all clauses are satisfied.

Note that if you're adapting a traditional SAT solver to count solutions, then your idea has more merit.  Noticing that all clauses are satisfied while there are still unassigned variables means you have found $2^n$ solutions to the formula, where $n$ is the number of unassigned variables.  This provides an exponential speedup over finding these solutions one by one, so the lazy clause tracking could potentially pay for itself.  However, an alternative would be to notice a satisfying assignment in the usual way and then undo assignments in reverse order until a clause is left unsatisfied.  You would have the same $2^n$ speedup without the clause tracking overhead.

the question/ setup/ premise does not seem to describe the "watched literals" concept accurately/ correctly. here is a summary from a SAT survey paper 2008, Satisfiability Solvers Gomes, Kautz, Sabharwal, Selman p94

  The watched literals scheme of Moskewicz et al. [170], introduced in their solver zChaff, is now a standard method used by most SAT solvers for efficient constraint propagation. This technique falls in the category of lazy data structures introduced earlier by Zhang [236] in the solver Sato. The key idea behind the watched literals scheme, as the name suggests, is to maintain and “watch” two special literals for each active (i.e., not yet satisfied) clause that are not FALSE under the current partial assignment; these literals could either be set to TRUE or be as yet unassigned. Recall that empty clauses halt the DPLL process and unit clauses are immediately satisfied. Hence, one can always find such watched literals in all active clauses.

the description earlier of DPLL in the chapter has the same mechanism/ terminology; "active" clauses are those not yet satisfied. (afaik) virtually every SAT technique keeps track of "active" clauses vs those that are currently unsatisfied under the current partial assignment. the "watched literal" concept is already tightly coupled with keeping track of active clauses as the question seems to wonder about.


What is the difference between object detection, semantic segmentation and localization? I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic segmentation vs localization is. It would be nice if you could give sources for your definitions.

I read a lot of papers about, Object Detection, Object Recognition, Object Segmentation, Image Segmentation and Semantic Image Segmentation and here's my conclusions which could be not true:

Object Recognition: In a given image you have to detect all objects (a restricted class of objects depend on your dataset), Localized them with a bounding box and label that bounding box with a label. In below image you will see a simple output of a state of the art object recognition.

Object Detection: it's like Object recognition but in this task you have only two class of object classification which means object bounding boxes and non-object bounding boxes. For example Car detection: you have to Detect all cars in a given image with their bounding boxes.

Object Segmentation: Like object recognition you will recognize all objects in an image but your output should show this object classifying pixels of the image.

Image Segmentation: In image segmentation you will segment regions of the image. your output will not label segments and region of an image that consistent with each other should be in same segment. Extracting super pixels from an image is an example of this task or foreground-background segmentation.

Semantic Segmentation: In semantic segmentation you have to label each pixel with a class of objects (Car, Person, Dog, ...) and non-objects (Water, Sky, Road, ...). I other words in Semantic Segmentation you will label each region of image.

Semantic  segmentation: It is  the  task  of  clustering parts  of  images  together  which  belong  to  the  same object  class.            eg:detecting road signs


Largest sum divisible by n I asked this question on StackOverflow, but I think here is a more appropriate place.

This is a problem from Introduction to algorithms course:

  You have an array $a$ with $n$ positive integers (the array doesn't need to be sorted or the elements unique). Suggest an $O(n)$ algorithm to find the largest sum of elements that is divisible by $n$.

Example: $a = [6, 1, 13, 4, 9, 8, 25], n = 7$.  The answer is $56$ (with elements $6, 13, 4, 8, 25$)

It's relatively easy to find it in $O(n^2)$ using dynamic programming and storing largest sum with remainder $0, 1, 2,..., n - 1$.

Also, if we restrict attention to a contiguous sequence of elements, it's easy to find the optimal such sequence in $O(n)$ time, by storing partial sums modulo $n$: let $S[i]=a[0]+a[1]+\dots + a[i]$, for each remainder $r$ remember the largest index $j$ such that $S[j] \equiv r \pmod{n}$, and then for each $i$ you consider $S[j]-S[i]$ where $j$ is the index corresponding to $r=S[i] \bmod n$.

But is there a $O(n)$-time solution for the general case? Any suggestions will be appreciated! I consider this has something to deal with linear algebra but I'm not sure what exactly.

Alternatively, can this be done in $O(n \log n)$ time?

Here are a few random ideas:

The dynamic-programming algorithm can be flipped to look for a smallest sum instead of a largest sum. You just end up looking for a sum congruent to the remainder of the sum of the entire array, instead of one congruent to zero. If we process the elements in increasing order, this sometimes allows the dynamic algorithm to terminate before processing the entire array.

The cost would be $O(n k)$ if we processed $k$ elements. There's not a lower bound of $\Omega(n \log n)$ on this algorithm because we don't have to sort all the elements. It only takes $O(n \log k)$ time to get the $k$ smallest elements.
If we cared about the set with the larget size, instead of the set with the largest sum, we might be able to use fast-fourier-transform-based polynomial multiplication to solve the problem in $O(n (\log n)^2 (\log \log n))$ time. Similar to what's done in 3SUM when the domain range is limited. (Note: use repeated squaring to do a binary search, else you'll get $O(n k (\log n) (\log \log n))$ where $k$ is the number of omitted elements.)
When $n$ is composite, and almost all remainders are a multiple of one of $n$'s factors, significant time might be saved by focusing on the remainders that aren't a multiple of that factor.
When a remainder r is very common, or there are only a few remainders present, keeping track of 'next open slot if you start from here and keep advancing by r' information can save a lot of scanning-for-jumps-into-open-spots time.
You can shave a log factor by only tracking reachability and using bit masks (in the flipped dynamic algorithm), then backtracking once you reach the target remainder.
The dynamic programming algorithm is very amenable to being run in parallel. With a processor for each buffer slot you can get down to $O(n)$. Alternatively, by using $O(n^2)$ breadth, and divide and conquer aggregation instead of iterative aggregation, the circuit depth cost can get all the way down to $O(\log^2 n)$.
(Meta) I strongly suspect that the problem you were given is about contiguous sums. If you linked to the actual problem, it would be easy to verify that. Otherwise I'm very surprised by how difficult this problem is, given that it was assigned in a course called "Introduction to Algorithms". But maybe you covered a trick in class that makes it trivial.

My proposed algorithm goes as follows:

A sum is divisible by n if you only add summands which are multiples of n.

Before you start you create a hashmap with an int as key and a list of indices as value. You also create a resultlist containing indices.

You then loop over the array and add every index which mod n is zero to your result list. For every other index you do the following:

You subtract the value mod n of this index from n. This result is the key for your hashmap which stores indices for elements with the required value. Now, you add this index to the list in the hashmap and move on.

After you finished looping over the array you compute the output.
You do this by sorting each list in the hashmap according to the value the index points to. Now you consider every pair in the hashmap summing up to n. So if n = 7 you search the hashmap for 3 and 4. If you got an entry in both you take the two largest values remove them from their lists and add them to your resultlist.

Last recommendation: still didn't test the algorithm, write a testcase against it using a brute force algorithm.


Data structures and algorithms for bridge game play? In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There are 28561 possible non repeated 4 card groups.

What is the best method of generating and storing all possible trick combinations (played according to the bridge rules just for one session) to be further processed by a computer program (i.e., data structures such as game trees, and any open source algorithms written for any computer language if any).

All resources to read to get the theory behind or any references are welcome.
Thank you.

If the data is really a tree graph, then maybe a Prüfer code?


Can you reduce a precedence graph or do *all* relevant nodes need to be connected Let's say we have the following simple transaction-schedule:

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
     | w(x) |
     |      | w(x)

T1 comes before T2, so in the precedence graph, we draw an arrow from T1 to T2. T2 comes before T3, so we draw an arrow from T2 to T3.

My question is: is it also necessary to draw an arrow from T1 to T3? T1 comes before T3, and the definition of a precedence graph says nothing about not drawing a line from Tx to Ty if there is some arbitrary Tz inbetween.

On the other hand, T1 -> T2 -> T3 implies T1 -> T3, and as the graph gets larger things will get a bit messy. Is it okay to 'reduce' a precedence graph?

If the answer to the above question is yes, here is a follow up - consider the following schedule:

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
 w(y)|      |
     | w(x) |
     | w(z) |
     |      | w(y)
     |      | w(z)

In the precedence graph, for the operations on x we draw an arrow from T1 to T2, for y an arrow from T1 to T3, and for z an arrow from T2 to T3. Would you be allowed to omit the arrow 'caused' by element z?

Yes it is necessary.

According to the definition of precedence graph, a directed edge $T_i \longrightarrow T_j$  is created if one of the operations in $T_i$ appears in the schedule before some conflicting operation  in $T_j$.

It is clear from the definition that we have to consider every two transactions separately : $T_1$and $T_2$, $T_1$and $T_3$ and $T_2$ and $T_3$.

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
     | w(x) |
     |      | w(x)

So an edge $T_1 \longrightarrow T_3$ is necessary because w(x) in $T_1$ and w(x) in $T_3$ are two conflicting¹ operations.

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
 w(y)|      |
     | w(x) |
     | w(z) |
     |      | w(y)
     |      | w(z)

For this schedule there will be three edges in the precedence graph:$T_1 \longrightarrow T_2$, $T_1 \longrightarrow T_3$ and $T_2 \longrightarrow T_3$.

1.Two operations are conflicting, if they are of different transactions, upon the same datum (data item), and at least one of them is write.

Whether it is necessary to include the edge $T_1 \to T_3$ depends upon how you plan to use the graph and what properties you want it to have.

In many applications, it is not necessary to include the edge $T_1 \to T_3$, since it is already implied by other edges.  For instance, the set of schedules that are consistent with this graph (i.e., the set of topological sorts of the graph) will be the same whether you use a dag $G$, the transitive reduction of $G$, or the transitive closure of $G$.

The answer might depend upon what your definition of a "precedence graph" is.  If you are using the phrase informally, then it is up to you to define what graph you want to use.  On the other hand, if you are using "precedence graph" as a formally defined term, as defined "in the concurrency control literature", that definition states that you should  include an edge from $u$ to $v$ if (1) $u$ must precede $v$, and (2) $u$ conflicts with $v$.  Thus, if $T_1$ conflicts with $T_3$, then you should include the edge $T_1 \to T_3$ (assuming you want to use that definition); if it doesn't conflict, don't include that edge.  In your example, it does conflict, so yes, you must include the edge $T_1 \to T_3$ if you want to use that definition of precedence graph.


Is the language with decreasing numbers of a, b and c context-free by pumping lemma? So I've been given the following language on an assignment.  It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours.

$$L=\{w:w\in(a+b+c)^*, n_a(w) > n_b(w)>n_c(w)\}$$

where $n_x(w)$ represents the number of character $x$ found in $w$.  The problem statement is: prove or disprove that the language is context-free.  Context-free grammars or pushdown automata are acceptable proofs.  Use pumping lemma to disprove.

I've extensively explored both possibilities and I'm fairly certain that it is context-free.

The approach I've taken in finding a context-free grammar for the language involves using rules which preserve the constraint $n_a(w) > n_b(w) > n_c(w)$ (ie. whenever a $b$ is added, add an $a$; whenever a $c$ is added, add a $b$).  Then, I've attempted to enforce that there are at least two $a$s and at least one $b$ (base case for the constraint).

The grammar I've used is:

$S\implies XaXaXbX | XaXbXaX | XbXaXaX$

$X \implies XX| A | B | C | \lambda$

$A \implies a$

$B \implies ab | ba$

$C \implies abc | acb | bac | bca | cab | cba$

(where $\lambda$ is the empty string)

My grammar fails for strings like $cccaaaaabbbb$.

I'm confused as to where to go from here.

I would really like a push in the right direction, not an answer.
 Any help is greatly appreciated!

If your language is context free, so is its intersection with the regular language $a^* b^* c^*$. And your proof in the answer that this isn't context free does go through. Your proof omits the cases where one of the strings straddles the $a/b$ or $b/c$ boundaries.

The following is my attempt at an answer.  I took a screenshot of my assignment, rather than retyping the proof into StackExchange.

Comments?


I'm looking for an algorithm to find unknown patterns in a string I am trying to detect patterns in huge code bases.
I managed to filter the entire codebase into a tagged string,
as in:
ABACBABAABBCBABA

The result should be:
ABA *3
CBA *2

I'm trying to build / use an algorithm which will find ANY unknown repeating pattern inside the string. The length of the pattern, it's composition, and the number of repeats is unknow.

To be a pattern it must occur atleast twice. And have atleast 2 items.
Once I detect the patterns I can represent them back in their original context

I have tried iterating over each tag.
For each tag find the following tag in the string.
continue until adding a tag matches only one repeat - hence no more pattern.

I get lost in implemetation (in JS or Python) and I'm hoping there is a better way.
Thanks.

Construct the suffix tree of your string, which takes time linear in the length of the string (assuming a finite alphabet). Every inner node represents a repeat, their respective descendant leaves encode the positions.

If I understand correctly, what you're asking is pretty much the opposite of the question "How truly random a string is?".
There's a huge literature on this in Cryptography and specifically random and pseudorandom generators, you can use statistical tests and tools to recognize recurring patterns.
But first you must have a clear vision on how to sort the significance of these patterns, I recommend defining a utility function u(n, r) in which n is the length of the pattern and r is it's repetition.