# Tag Info

232

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

214

Part II Continued from Part I. The previous one exceeded the maximum number of letters allowed in an answer (30000) so I am breaking it in two. $\mathsf{NP}$-completeness: Universal $\mathsf{NP}$ Problems OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of efficiently verifiable problems ($\mathsf{NP}$). As ...

123

I have a different answer from other folks: pixel is the correct unit for areas, and you do need dimensional analysis. The discrepancy is that the pixel in "3840 pixels wide" is not the same unit as the pixel in "the display has 8294400 pixels". Instead, "pixel" is a natural-language abbreviation for different units at different times, and it takes some ...

83

An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006): By the way, why did Church choose the notation “$\lambda$”? In [Church, 1964, §2] he stated clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to ...

54

For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word. Language: a language is simply a set of strings. If you have an alphabet, such as $\Sigma$, then $\Sigma^*$ is the set of all ...

53

It's called linearithmic time, and is a special case of a more general class known as quasi linear. As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact they have a lower complexity than algorithms which run in $O(n^k)$ with $k > 1$.

46

The Wikipedia article on hash functions is very good, but I will here give my take. What is a hash? "Hash" is really a broad term with different formal meanings in different contexts. There is not a single perfect answer to your question. I will explain the general underlying concept and mention some of the most common usages of the term. A "...

44

A pixel is already a two-dimensional object In your example, you specify centimeters as a contrasting example. Centimeters are a unit of length, which is by nature a one-dimensional measurement. When measuring areas, we need to talk about square centimeters, which defines the unit as a two-dimensional quadrilateral with right angles and equal length sides = ...

43

You are right, there always is a context in some sense. I don't think you can understand what "context" means in "context-free" without understanding a production. A production is a substitution rule. It says that, to generate strings within the language, you can substitute what is on the left for what is on the right: A -> xy This means that the ...

41

Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size. Exponential time algorithms are algorithms whose running time increases by a constant factor when the input size increases by 1. For laypeople you can perhaps identify NP-complete problems with problems solvable only in exponential ...

40

An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running ...

40

Humans are bad at logic until they have to employ it to figure out human affairs. Think of "if $A$ then $B$" as a kind of promise: "I promise to you that if you do $A$ then I will do $B$". Such a promise says nothing about what I might do if you fail to do $A$. In fact, I might do $B$ anyhow, and that would not make me a liar. For instance, suppose your ...

39

Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are engineering, and parts are mathematics. The more theoretical parts of computer science are purely mathematical. For example, what is a good algorithm for sorting? How do we define ...

39

The main differences are along two dimensions -- in the underlying theory, and in how they can be used. Lets just focus on the latter. As a user, the "logic" of specifications in LiquidHaskell and refinement type systems generally, is restricted to decidable fragments so that verification (and inference) is completely automatic, meaning one does not require ...

39

Let me see if I can clear up a few potential misconceptions here. Sometimes people think that when they write a research paper they have to use fancy language: it's not enough to just say what they mean, but rather, it has to be written in academic code with more complex-sounding language. Or, they think that using bigger words will make them sound more ...

38

Would it be incorrect to cast polynomial time as "time measured in (computational) operations?" Yes. Completely incorrect. "Time" does indeed mean "time measured in (computational) operations" but you've not translated "polynomial" at all. It's like translating "twelve days" as "time measured in number of rotations of the earth on its axis." That's exactly ...

34

You can say that an algorithm is asymptotically optimal in such a case. In general, people might also say that an algorithm is optimal in some other sense, like assuming some particular complexity-theoretic conjecture like (S)ETH.

33

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 distance to $... 31 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 ... 30 The major distinction between how DFAs (Deterministic Finite Automaton) and TMs work is in terms of how they use memory. Intuitively, DFAs have no "scratch" memory at all; the configuration of a DFA is entirely accounted for by the state in which it currently finds itself, and its current progress in reading the input. Intuitively, TMs have a "scratch" ... 30 The context can be explained with regards to the production rules allowed for different grammars in Chomsky hierarchy. If you consider context-free grammars, their production rules have the following form: $$A \rightarrow \alpha$$ So, you can observe that the left part of this kind of rules is made up of only one non-terminal symbol; thus, the ... 29 How about an automotive analogy? uses computers and maybe "is good with computers" :: a driver (can drive and refuel safely) and maybe a car enthusiast (can jump start a car; is familiar with many makes and models; knows techniques like using windshield treatment to keep rain from reducing visibility). programmer :: an automotive mechanic or technician. ... 27 Wikipedia has the answer: All types of edges appear in this picture. Trace out DFS on this graph (the nodes are explored in numerical order), and see where your intuition fails. This will explain the diagram:- Forward edge: (u, v), where v is a descendant of u, but not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.... 25 Since it is an english major: Computer literacy is like reading, computer programming like composition, and computer science like linguistics. All 3 are about language, but the skills are not exactly interchangable. 25 As far as I'm concerned, null, nil, none and nothing are common names for the same concept: a value which represents the “absence of a value”, and which is present in many different types (called nullable types). This value is typically used where a value is normally present, but may be omitted, for example an optional parameter. Different programming ... 24 The term "true concurrency" arises in the theoretical study of concurrent and parallel computation. It is in contrast to interleaving concurrency. True concurrency is concurrency that cannot be reduced to interleaving. Concurrency is interleaved if at each step in the computation, only one atomic computing action (e.g. an exchange of messages between sender ... 24 Yes, there is a difference between the three terms and the difference can be explained as: Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree. 18 / \ 15 20 / \ 40 50 / \ 30 50 Complete Binary Tree: A Binary Tree is complete ... 23 You seem to have stumbled on a contentious issue. Apparently computer scientists like to argue. I certainly like to argue, so here goes! My answer is an unequivocal: No. A deterministic finite automata does not need a transition from every state for every symbol. The meaning when$\delta(q,a)$does not exist is simply that the DFA does not accept the ... 23 Refinement types are simply usual types with predicates. That is, given that$T$is a usual type and$P$is some predicate on$T$$$\{v:T \mid P(v)\}$$ is a refinement type.$T$in this case is called a base type. AFAIK, in Liquid Haskell, they also allow some dependend function types, that is types$\{x:T_1 \to T_2 \mid P\}\$ [1]. Notice that fully ...

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