A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Tag Info

30

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-...

10

The two most obvious characteristics of an assembly language are: It is specific to a particular CPU architecture. There is a one-to-one correspondence between assembly language commands and machine code instructions (once you strip out labels, assembler directives and code comments). By contrast, a high-level language will have the following ...

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 ...

7

There are several things that are all called regular expressions. The answer to your question is different depending upon which thing you want to talk about. The three relevant distinctions for this question in my opinion are as follows: First The notion of regular languages and related things like recursive enumerability. Individual regular languages ...

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 ...

6

In computer science, "automaton" refers to some kind of finite state machine. This is a basic and fundamental model of computation, and automata are widely used in implementing simple electronic devices and in writing parsers, e.g., for programming languages.

5

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

5

I suspect you might have misheard. I suspect the lecturer said "takes the file decodes it generates the right waveforms and so on" (right, not white).

5

The essential difference between assembly language and every other programming language is that assembly language specifies the sequence of instructions directly, whereas in any other language, the code has to be converted into a sequence of instructions, a process known as compilation or code generation. As a consequence, assembly language is architecture-...

5

The automaton is mainly used as a simple model of computation to check input strings on some defined conditions by reading the string and giving out whether the string is accepted in a defined language or not. There are a lot of examples. A really crucial for example in terms of computing are the RegEx-expressions, if you heard of that. There are some ...

5

The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos  and Khuller, Purohit and Sarpatwar . It also appears in the recent survey of Narayanaswamy and Vijayaragunathan ...

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

P, NP, NP-complete and NP-hard are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties: Solvable in polynomial time: Defines decision problems that can be solved by a deterministic Turing machine (DTM) using a polynomial amount of computation time, i.e., its running ...

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 ...

4

(Warning, this historical account of increasing abstraction and declarative programming may annoy, confuse, or upset you:) Hello, world! By far and large, programing languages happen on a continuum, with "pure" instances of languages being ideals. This is because there are a variety of platforms, architectures, and goals when writing software. Of course, ...

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

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

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

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

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

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{...

3

They are called primitive data types. (This is a pretty basic find in Wikipedia's article on data types.)

3

Yes, your context-free grammar is in Chomsky Normal Form. A grammar is in CNF whenever its rules are of one of two types, either $A\to BC$ or $A\to a$, where $A,B,C$ are nonterminals, and $a$ is a terminal symbol. This means that every context-free grammar is equivalent to a cf grammar in CNF, up to the empty word. This means that by conversion into CNF ...

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