# Tag Info

18

The short answer is that no one knows what real randomness is, or if such a thing exists. If you want to quantify or measure the randomness of a discrete object, you would typically turn to Kolmogorov complexity. Before Kolmogorov complexity, we had no way of quantifying randomness of say a sequence of numbers without considering the process that spawned it. ...

13

What you want to do seems to be known as Audio Feature Extraction or, more specifically, Music Information Retrieval, that is automated methods that distill characteristics out of (sets of) music files. You would have to extract features of samples of both equivalence classes and look at differences that can inform song choice. Researchy tools are available ...

12

The classic consequence of $a^nb^n$ being context-free rather than regular is on opening and closing brackets. $a^nb^n$ represents the simplest possible case of this: no interleaving of opens and closes and no intervening characters. Regular expressions can't even deal with this most basic case.

11

What you're looking for is a heuristic. No algorithm can say, given a graph of friends as the only input, whether two individuals not directly connected are friends or aren't; the friendship/acquaintance relation isn't guaranteed to be transitive (we can assume symmetry, but that might even be a stretch in real life). Any good heuristic will therefore need ...

10

There is a lot of work done on this problem as the popularity of social networking has taken off. The problem is typically termed "Link Prediction" and very good and comprehensive surveys can be found here and here. The methods range from the very simple (e.g. Jaccard similarity between nodes) to the very complex (e.g. constructing statistical models of the ...

9

You can easily profit from warfare that way: $$M \stackrel{\mathrm{def}} = c.( d_{\text{tea}}.\bar e_{\text{tea}}.M + r.\bar b.M + c.( d_{\text{coffee}}.\bar e_{\text{coffee}}.M + r.\bar b.\bar b.M ) )$$ note that you have to press refund to get a tea if you put too many coins. If you don't want that, you can ...

8

In the case of Java (or similar languages), we know the algorithm used to create the random numbers. If it starts with a single seed, the numbers are not random at all, i.e. if we know $a_i$ in a sequence $a_0,\dots,a_n$, we know $a_{i+1}$, or stated as conditional probability: $$\forall k,l,i: P(a_{i+1}=k\mid a_i=l)\in\{0,1\}$$ Nevertheless those series ...

7

There are two parts to this: (a) selecting a graph (experimental design) to determine which pairs of essays the students will evaluate in the peer grading process, and (b) ranking all the essays, based upon the student's peer grades, to determine which the teacher should rank. I will suggest some methods for each. Choosing a graph Problem statement. The ...

7

You can think of the social graph as a matrix $\mathbf{M}$. One approach to the problem is to first calculate $\mathbf{M}^2$, which will give all of the paths of length two between two actors in the social network. This can be seen as the weight of the connection between these friends of friends. The next step is to select the columns from the row of $\... 7 Average degree and mean degree are the same. In the$G(n,m)$model, the average degree is$2m/n$. In the$G(n,p)$model, the expected average degree is$np$. The actual average degree has normal distribution with mean$np$and standard deviation$\sqrt{2(1-\tfrac{1}{n})p(1-p)}$, so it is pretty close to$np$with high probability. When$p=c/n$for fixed$c$,... 6 Model theory, branch of mathematical logic, is based on three things: atoms, functions, and relations. With these you can define pretty much anything. In fact, functions are subsumed by relations, so you only need two. What is a list but a next relation? What is a hierarchy but a parent-child relation? Of course these satisfy axioms, and these can readily ... 5 Is there a more efficient encoding, preferably without a database of each valid sudoku setup? Yes. I can think of an encoding improving your 149-bit encoding of a minimal$9\times 9$puzzle in 6 or 9 bits, depending on a condition. This is without a database or any register of other solutions or partial boards. Here it goes: First, you use$4$bits to ... 5 This$M_0$machine is more convenient than the one you propose: $$M_0 := c.M_1$$ $$M_1 := d_{\text{tea}}.\bar e_{\text{tea}}.M_1 + r.\bar b.M_0 + c.M_2$$ $$M_{n} := d_{\text{tea}}.\bar e_{\text{tea}}.M_{n-1} + d_{\text{coffee}}.\bar e_{\text{coffee}}.M_{n-2} + r.\underbrace{\bar b.\dots\bar b.}_{n}M_0 + c.M_{n+1}$$ (But using infinite processes is ... 5 Ad Question 1: Assuming that your assumptions on how the catalogue is used -- that is the choice of the next cell only depends on the current (or constantly many preceeding) cell(s), not the (full) history -- then yes, you can use a Markov Chain to model it. However, you do not seem to need the "Hidden" part; this is only useful if you have (probabilistic) ... 5 "new flow arrivals" means "arrivals of new flows". A flow is a TCP connection (roughly); each individual TCP connection is a separate "flow". So, this is talking about new TCP connections, and the rate/time at which the server receives new TCP connections. Contrarily to the statement you quoted, web requests won't necessarily be Poisson. There are many ... 4 First a bit about the classifier: The knn classifier works by majority voting. It takes an input record, finds the k nearest labeled data points, looks at the class labels on each data point and assigns the current record the most common class label. For instance, if I use a 3-NN classifier and my three neighbors are of class [1 1 2], then I will select ... 4 Disclaimer: I am wildly guessing here; I have not read any genre research. You could look at how many connections to nodes share relatively to the number of conncetions a node has. This is a very naive (as local) idea, but here goes. Every node$N$(person or some other concept) has a set of connections$C_N$. Now, given two nodes$N_1$and$N_2$, suggest$...

4

In the past I worked on usability of interfaces in the information retrieval area, so I give you some practical ideas on how to measure the usability. You didn't give details of what a "catalogue" is, so I will assume that a user has a problem (or need) and he is searching your catalogue (in paper or electronic format) for one or more solutions. Then you ...

4

The interests are categorical data and may be modeled as binary variables (a user either likes them or he does not). You can subsume little-used categories under broader categories. For example, a user who likes a little-known horror movie can simply be marked as liking horror movies. You can even subsume such items under multiple categories if it belongs to ...

4

Hmm, using Bayes Theorem to make new recipes out of old recipes. I imagine you first would want the algorithm to pull apart the ingredients into a form it understands (not sure if we are using NLP for that, or if you manually enter the data in yourself, that's neither here nor there.) From there... I envision something like this. Test Data analyzed. Now we ...

4

This answer considers two cases: the overlapping relation between two disks, which is a very simple problem. the ovelapping or covering of a disk by a set of other disks, which is somewhat harder in general. Case of two disks It is indeed a good idea to use center and radius to represent your circles. However I think you are not thinking of circles, which ...

4

If you want to model an alldiff() constraint in SAT, there are several options. Here are two different options you can try: One way is to expand $\text{alldiff}(x_1,\dots,x_n)$ into $n(n-1)/2$ inequality constraints: $(x_1 \ne x_2) \land (x_1 \ne x_3) \land \cdots$. Now you can express each inequality constraint $x_i \ne x_j$ on $b$-bit values in turn as ...

4

I'm not sure how to approach your particular problem, but here is an attempt. Consider the recipe you are using as a collection of steps, some of which depend on others; for a salad you might have "make dressing", "shred lettuce", "slice cucumber" etc. The dependencies are given through resources, which here are ingredients, possibly in some processed state,...

4

You can't. You can't express this without using quadratic constraints. Your requirement is about Euclidean distance. The Euclidean distance is inherently quadratic. To be more precise about that: the problem cannot be expressed using solely using linear constraints, as the Euclidean distance is non-linear. That said, you can solve your one-sentence ...

4

It seems you're looking for a symmetric set similarity measure. (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$. Set similarity since each person's preference is defined by a set of objects.) A number of these are used in the CS literature. Probably the most common is Jaccard similarity, defined by $|A\cap B|/|A\cup B|$...

3

The river crossing problem using integer programming is solved by Börndorfer et al. in [1]. [1] Borndörfer, Ralf, Martin Grötschel, and Andreas Löbel. Alcuin's transportation problems and integer programming. ZIB, 1995.

3

It is impossible to know for sure whether a given sequence is random or not. You can, however, look at characteristics (or parameters) of a sequence and calculate the probability of such a sequence given the distribution of interest. If you could generate an infinitely long sequence using your random generator, it should have the same parameters as the ...

3

An easy optimization to the naive algorithm is to skip some points when you check one covered by a window. Say you scan left-to-right, top-to-bottom. If you encounter an $(x, y)$ in window $w = (l, r, w, h)$, you can jump from $x$ to $l + w + 1$ and continue. If windows are big and don't overlap, off the cuff, I'd wildly conjecture that would give you an \$O(...

3

The modern theory of computing answer is "a random source is a source that looks random to your favorite class of algorithms". This is a utilitarian perspective: if a source of randomness looks like true randomness to all algorithms you care about, then nothing else matters. You can analyze your algorithms as if they are given truly random coin tosses, and ...

3

Recipe generation is commonly used as an example application for Case Based Reasoning systems. It is even used as an example on the Wikipedia Page. A google search for "case based reasoning recipes" yields numerous results.

Only top voted, non community-wiki answers of a minimum length are eligible