18

It's called "loop fusion". It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in your example may also put more pressure on the CPU's cache prefetch system. So do test it before declaring it more efficient.


16

I would add to the existing answer that the composition $h = f \circ g$ is the identity, which you already pointed out. This means that $g$ is the right-inverse of $f$, and $f$ is the left-inverse of $g$. That makes each of $f$ and $g$ invertible on the given side. For the pairs you have given, I would expect $g \circ f$ to also be the identity in the naïve/...


10

The language borrowed from category theory is that f is a retraction of g, and g is a section of f. If f is both a retraction and a section of g, then it's called an inversion.


9

Part 1 I'm going to do something I decided I wouldn't do: try to nutshell my research on this topic. I'll go over on how the algorithmic O-notation must be defined, why it is probably not what you've been taught, and what other misconceptions float around this topic. I wrote this in the form of an imaginary discussion. The following discussion is based on ...


7

Part 2 $$ \newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}[1]{\mathcal{P}(#1)} \newcommand{\setb}[1]{\left\{#1\right\}} \newcommand{\land}{\text{ and }} $$ Algorithms Are there cases where existing intuition on O-notation may not hold? You may find that your existing intuition does not hold when the input-set is something else ...


7

The definition you are looking for is "defective coloring": A $(k, d)$-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative ...


6

I'm not familiar with this variant, but it is still NP-complete for any fixed $p$. Given a graph $G$ and an integer $c$, connect to each vertex $v$ a clique $C_v$ on $(p+1)c-1$ vertices. If the original graph $G$ has a valid coloring $\chi$, then we can color the clique $C_v$ as follows: the color $\chi(v)$ appears $p$ times, and all other colors appear $p+1$...


6

The Complexity Zoo has a pronunciation guide by Scott Aaronson "for those who insist on communicating verbally about complexity." It recommends the "p slash polly" option.


5

In Haskell the syntactic sugar for bind e₁ (λ x . e₂) is do x ← e₁ e₂ That is, the result of the computation e₁ is bound to x, after which e₂ is computed. In ML-like languages the same thing is written as let x = e₁ in e₂ which again is a form of binding a variable to a value. As for return being a control-flow mechanism – that's precisely what it ...


4

The answer is unknown. If $X\in NP$ and $\bar X\in \mathcal{NP}$ than by definition it's a so called "co-NP" problem ($X\in \mathcal{coNP}$). It's still an open problem if $\mathcal{NP} = \mathcal{coNP}$. An example: Some problems are known to be in coNP. E.g. to decide if two number $n,m$ have a common divisor $>1$. This problem is in $\...


4

If we were to use the decimal expansion to represent real numbers, your reasoning would work. But that gives us a very badly behaved notion of computability: Proposition: Multiplication by 3 is not computable relative to the decimal representation. Proof: Assume the input starts 0.3333333... At some point, our computation needs to start outputting something. ...


4

In λ-calculus, the term $\lambda x. y$ binds $x$ in $y$. Once a value is given to $x$, any well-scoped reference to $x$ in $y$ will be replaced by that same value. Function composition $(f\circ g)$ can be seen as an operator that binds the result of $g$ to $f$'s argument. In a similar way, you can view bind : Monad m => m a -> (a -> m b) -> m b ...


4

A refinement type is a type together with a decidable predicate: $$ \{x:T ~|~ p(x)\} $$ where $x$ is a variable name, $T$ is a type, and $p(x)$ is a decidable predicate over $x$. A dependent pair type is the product type of two types where the second type depends on the value of the first: $$(x : T) \times q(x)$$ where $x$ is a variable name, $T$ is a type ...


3

Memoization is the technique to "remember" the result of a computation, and reuse it the next time instead of recomputing it, to save time. It does not care about the properties of the computations. Dynamic programming is the research of finding an optimized plan to a problem through finding the best substructure of the problem for reusing the computation ...


3

It appears that "F" does not stand for anything in particular: rather, it is the metavariable symbol that is used in the definition of F-bounded quantification. In the paper in which F-bounded quantification was introduced, F-Bounded Polymorphism for Object-Oriented Programming, the authors write: To solve this problem and related difficulties with other ...


3

There is no one true answer. It depends on context. The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time". Polylogarithmic time is used only in very narrow contexts. In general, if you think your audience might not be sure about ...


3

I would say that $X$ is a subset of $Y$, in terms of bits set.


2

In modern papers, and unless stated otherwise, NP-hardness is one of the following: A decision problem is NP-hard if it is NP-hard with respect to many-one reductions. An optimization problem is NP-hard if its decision version is NP-hard. Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem ...


2

According to the Wikipedia article on magic cookie, it was used already in 1979 in the manpage of fseek. The talk page of the Wikipedia article on magic cookie discusses questions regarding the origin and meaning of the word. The following quote of Douglas W. Jones from the talk page nicely summarizes it: Once upon a time, I asked Dennis Ritchie about the ...


1

I'm not familiar with the "strong" terminology. However, the 'obvious' answer to the other question is that it both duplicates the $x$ argument and exchanges the relative positions of (one copy of) the $x$ and $g$ arguments: $$\mathsf s\ f \ g\ x = f\ x\ (g\ x)$$ The other combinator it's usually paired with: $$\mathsf k\ x\ y = x$$ discards an ...


1

Bachmann–Landau notation or asymptotic notation is collection of notations one of which is Big-$O$. So they are not interchangeable, because as asymptotic notation also is known little-$o$, big-$\Omega$, big-$\Theta$ etc. Historically this symbol was introduced by German mathematician Paul Bachmann and then adopted by German number theoretician Edmund ...


1

I don't know if there's a name for such subgraphs, but here's something to get you started. If you require the subgraphs to be connected A polytime algorithm for $G=(V,E)$ would be: for every possible unordered pair $(A,F)\in \binom{V}{2}$ consider the connected components of the graph induced by $V\smallsetminus\{A,F\}$. Then consider the classes which ...


1

decrypt is the inverse of encrypt deserialize is the inverse of serialize In other words, the composition of a function and its inverse are the identity function.


1

I'll assume that we're working in the context of classical propositional logic. The first thing to point out is that $\lnot(A \rightarrow A)$ leads to a contradiction: ($A \land \lnot A$). Since propositional logic itself is consistent, it is impossible to derive a contradiction, so $\vdash \lnot(A \rightarrow A)$ is impossible. So perhaps your intention was ...


1

It's true: Assume $Y\in NP$. Now let $N$ be the poly time verifier for $Y$. Lets also call the poly time reduction $\phi$. Then, notice that $x\in X\iff\phi(x)\in Y\iff \exists w.N(\phi(x),w)$. Therefore, let us build the poly time verifier for $X$ as follows: $M(x,w):$ Compute $\phi(x)$ in poly time Emulate $N(\phi(x),w)$ and accept if and only if $N$ ...


1

I understand "to bail out" as to give up permanently; "to back out" is to give up some track, possibly to try something else.


1

I had the same suspicion going through the Nand to Tetris course. Indeed, if you look at John K. Bennett's annotated version of "The Elements of Computing Systems", specifically Chapter 5, he calls this out: The Hack architecture would more properly be called a “Harvard Architecture,” since the data and instruction memories are separate. We can ...


1

In simple words: Computer science is the study of computers Informatics is the study using computers This is what I personally think. Hope it helps you.


1

"...the most common misconception that an algorithm and a pseudocode is one of the same things. No, they are not! Let us take a look at definitions first: Algorithm : Systematic logical approach which is a well-defined, step-by-step procedure that allows a computer to solve a problem. (Can be what's in the code-side Notes explaining the performance ...


1

The naming of the method is probably deliberate in some textbooks (e.g. CLRS) because: The logic for "floating down" or "bubbling up" a key in a binary heap is straightforward if you know which direction (up/down) you are going. E.g. "bubbling up" a key is simply a recursive call on the node parents, vs floating down where you need to compare with each ...


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