# Tag Info

30

What you described is Voronoi diagram. Here is an excerpt from Wikipedia. In the simplest case, shown in the first picture, we are given a finite set of points ${p_1, \cdots, p_n}$ in the Euclidean plane. In this case each site $p_k$ is simply a point, and its corresponding Voronoi cell $R_k$ consists of every point in the Euclidean plane whose ...

29

In the most general sense, a key is a piece of information required to retrieve some data. However, this meaning plays out differently depending on exactly what situation you're dealing with. In the contexts you mention, a key is a unique identifier for the complete data used to retrieve it from some location in the structure. Each key is associated with ...

12

A key in the context of data structures (such as in the book CLRS) is a value (often an integer) that is used to identify a certain component of a data-structure. Often, keys determine how the underlying data is stored or manipulated. For example, in binary search trees we have that for every node, the key of that node is larger than the keys in the left sub-...

8

This is called the reachability problem -- is it possible for a given system to enter a given state? Techniques that attempt to answer this problem fall under reachability analysis, which is one of the main goals of (finite / symbolic) model checking. As the other answer suggests, this is one of the many instances covered by Rice's theorem. Answering ...

7

I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time. Very nice question! What you are talking about is best characterized as promise problem, "a generalization of a decision problem where the input is promised to belong to a ...

7

"On the order of" is an informal statement which really only means "approximately". Big O notation is a precise mathematical formulation which expresses asymptotic behavior, not approximate values of a function (e.g., $10n \in O(n)$, despite $10n$ being 10 times as larger as $n$). They can hardly be considered the same things. What the lecturer is trying to ...

6

"Super-exponential" just means more than exponential, so a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ for every constant $c$, i.e., if $\lim_{n\to\infty} f(n)/c(n)=\infty$ for all constants $c$. Conversely, a function is "sub-exponential" if it is $o(c^n)$ for ...

6

This is essentially a Segment tree which is a data structure that augments an array with a binary tree as you describe such that: You have fast set and get at any index You have fast "aggregate" queries on ranges You can support fast update queries on ranges, for some combinations of updates and queries The $j$th node at height $k$ in the tree "summarizes" ...

6

The function $$\lambda f.\lambda x.\lambda y.f\;y\;x$$ of type $$\forall X. \forall Y. \forall Z.(X \to Y \to Z) \to Y \to X \to Z$$ is often called flip. This is the case in Haskell (see here), and in some OCaml libraries as well (see here). According to wikipedia, people call this function (or combinator) $C$ in the context of combinatory logic (that name ...

5

Summary: the memoization technique is a routine trick applied in dynamic programming (DP). In contrast, DP is mostly about finding the optimal substructure in overlapping subproblems and establishing recurrence relations. Warning: a little dose of personal experience is included in this answer. Reading suggestion: If this answer looks too long to you, just ...

5

EDIT: This answer is more detailed than mine. This is an example of a question covered by Rice's theorem. For example, the question of if a program outputs "Hello World" or not is covered by that theorem. It also covers quantification over inputs (e.g. does program $P$ do $X$ on all input, does program $P$ do $X$ on some inputs, does program $P$ do $X$ on ...

4

Since this issue is still not quite clear even now in 2019, and it might help new ML-Learners choose, here is a very good image showing the differences: (localisation is the bounding box around the "sheep" class, after a classification of the image has been done) source: Towardsdatascience.com

4

There is no exact answer to your question. The terms "programming model" and "programming paradigm" are not exact technical terms that have fixed definitions. Depending on a context, some authors might define "programming model" in some specific way, but that will usually turn out to cover only some aspects of what people understand under "programming model"....

4

I good starting point is Benjamin Pierce's Types and programming languages (popularly referred to as "TAPL").

4

Using any/all (a.k.a. or/and) gives rise to alternating Turing machines. Goldschlager and Parberry (On the construction of parallel computers from various bases of boolean functions, Theoretical Computer Science 48:43–58, 1986) consider the generalization to allowing arbitrary Boolean functions, and they call the resulting machines extended Turing ...

4

The answer depends on exactly what problem you're solving. If your goal is to produce an algorithm that correctly solves the problem on the restricted instances, then it's kind of up to you whether or not you check. It feels more robust to check the input but it's perfectly reasonable not to, and that puts you in the realm of promise problems. Here, the "...

4

This is something you will encounter over and over, not just in science but also in engineering, in law, in programming, and generally in jargon. If there is a definition for a term, then that term means exactly what the definition says it means. No more. No less. In particular, you may have an intuitive notion of what the term means in English, but this is ...

4

LSB (least significant bit) and MSB (most significant bit) apply purely to the values of an integer. The least significant bit is the bit with value 1, the second least significant bit is the bit with value 2, and so on. "Little endian" and "Big endian" are just artefacts from the fact that the bytes of a number can be accessed individually as they are ...

3

Using David's definition; a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ for every constant $c$, i.e., if $\lim_{n\to\infty} f(n)/c(n)=\infty$ for all constants $c$. The $n$-th formula of Catalan Numbers is given by Wikipedia as; $$C_n \approx \frac{4^n}{n^{3/... 3 Your two definitions are essentially the same: a \Sigma_1^0 formula is one of the form$$\exists x Q(n,x),$$where Q is computable and n is the parameter. Another difference between the two definitions is that the first only defines r.e. sets, i.e. unary relations, whereas the second defines r.e. relations of arbitrary arity. The two definitions ... 3 The IELR(1) Parsing Algorithm The IELR(1) parsing algorithm was developed in 2008 by Joel E. Denny as part of his Ph.D. research under the supervision of Brian A. Malloy at Clemson University. The IELR(1) algorithm is a variation of the so-called "minimal" LR(1) algorithm developed by David Pager in 1977, which itself is a variation of the LR(k) parsing ... 3 You are looking for a Multi-Class Classification Algorithm. I suggest you have a look at: K-Nearest Neighbors algorithm (or KNN). Here is an introductory blog post. Support Vector Machines. You can start reading up on it here. 3 I think that many programmers would look at it in terms of the conversions between the two formats, and say that each format can be converted to the other losslessly, and that it's possible to make a round-trip without losing any data. It's not a standard usage, but if you said that the two formats were round-trippable wrt each other, you would probably be ... 3 Undecidable is simply the complement of decidable, as the name suggests: anything that is not decidable is undecidable. So the whole pink area of your diagram consists of undecidable languages. All languages over finite alphabets are countable. For example, every string over alphabet \{0,1\} is a natural number written in binary.1 Everything in your ... 3 A language is defined as a set of strings over an alphabet. We will assume the usual situation where the alphabet is a finite set. Then the set of all strings are countably infinite. Why is it countable? Because we can list all strings of length 0, all strings of length 1, all strings of length 2, all strings of length 3 and so on. The correct diagram ... 3 Rooted Tree How do you call a rooted tree if the number of branches per node is arbitrary (outdegree of n) but the indegree 1 for all nodes other than the root node? That is none other than an rooted tree itself or, more accurately, an arborescence or branching tree or out-tree according to the following quote from Wikipedia entry on rooted tree. A ... 3 I think that's often called a "variable assignment", since it assigns to each variable a value (a vertex in the graph, in your case). If the graph is equipped with a set of such tuples, these might be considered to be hyperedges, i.e. edges connected to an arbitrary number of vertices (not necessarily two of them). 3 Yes, the code written by your friend implements the selection sort. It is not exactly how the selection sort is usually implemented, though. What is done in your friend's code? At the first iteration where i=0, it finds the smallest element by comparing the element at index 0 with all other element, swapping if necessary so that the minimum element so far ... 3 A problem is always claimed to be NP-hard, period. Indeed, a problem's definition already contains a specification of its parameters. (See the entries in Richard Karp's seminal collection of NP-complete problems for several examples.) Usually, there is no need to make explicit reference to the parameters per se, as they are "automatically scaled" by the ... 3 I don't know a standard name for this, but what you've described is representable as a function into \mathbb{R}. For your example, if X is the set of your things then you can represent your 'fractional multiset' as a a function f : X \to \mathbb{R} such that$$ f(x) = \begin{cases} 1 & x = \text{carpenter}, \text{sawyer} \\ 0.5 & x = \text{...

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