People who code: we want your input. Take the Survey
77

As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here: A|B||0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f -+-++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 0|0||0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1 0|1||0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1 1|0||0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1 1|1||0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1 A and B are the inputs, 0 through f ...


25

It's easiest to think of $1$ representing a true statement and $0$ representing a false statement. The logic gates then act as truth functions. Say you put two statements, $p,q$, together to form a new statement, $r$. In the case of and (logical conjunction), both $p$ and $q$ must be true for $r$ to be true. In the case of or (logical disjunction), $r$ ...


23

I think the questioner has it backwards. If we have a logical function such that A | B | result ---+---+------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1 then we decide to call that function and because it is obvious that the result is 1 only when A and B are both 1. Similarly for or, exclusive-or, etc. There are 16 ...


9

The why of it actually comes from the development of logic, which is a philosophical study of what is true and what is not true. Logic was originally a study of human language with the assumption that if you can reason about how human language works you can maybe reason about how reason works. Since the language I'm answering you in English let's use ...


5

It turns out that the very popular textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, sneakily avoids this issue by giving a different definition of cycle in undirected vs directed graphs. In Section B.4, it defines cycle and simple cycle as I do (they also require at least one edge), in directed graphs. In an undirected graph, ...


4

There is a slight abuse of notation going on. We say that a function $f$ is NP-hard if $f\in FP$ implies $P=NP$. For example, if $L$ is NP complete and $M_L(x,y)$ is a verifier for $L$, then any function $f$ which maps $x$ to some $y$ such that $M_L(x,y)$ whenever such $y$ exists is of course NP-hard in this sense. We don't usually talk about actual ...


3

It looks like you misread or misunderstand the standard set notation "$E'\subseteq E$". That notation just means $E'$ is a subset of $E$, i.e. every element of $E'$ is also an element of $E$. We do not speak of "an improper subset", most of the time if not ever. Why? Suppose $A$ and $B$ are two sets. $A$ is a subset of $B$ iff every ...


3

The boolean operators (and, or) are functions that map two inputs to an output, just like any other binary operator (i.e. +). Their exact behavior (the why question) is an axiom of boolean logic, just as the behavior of addition is an axiom of mathematics, which is to say that we agree that these operators do what they do. It is therefore the bedrock of ...


3

Arguably two of the most definite textbooks on graph theory are Bundy & Murty (BM) (roughly 15000 citations at the time of writing) and Diestel (at least hundreds of citations). In BM (Section 1.6), the definition of a cycle is obtained via walks and trails, i.e., a cycle is a non-empty trail in which the first and last vertex are repeated. In your ...


3

I'll go with (3) From Bondy and Murty's Graph Theory with Applications (http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf), sections 1.6 "Paths and Connections" and 1.7 "Cycles": A walk is a finite non-null sequence of alternating vertices and edges (repetition of both allowed). If the edges of a walk are ...


2

A hash function is used to map a set of keys to a subrange of the integers (it is used as an index into an array, in the end). So it must be (assuming zero based arrays, as in C), $h \colon \mathcal{U} \to [0, m - 1]$ if $\mathcal{U}$ is the universe of keys.


2

The difference appears to be that "process" is a well-defined term with a specific meaning that is universally understood, whereas "task" is ambiguous and means different things to different people. The following Stack Overflow questions on the same topic support this: https://stackoverflow.com/questions/3042717/what-is-the-difference-between-a-thread-...


2

In general Monte Carlo is used to solve a wide variety of different types of problems. In this particular case you want to learn if a random variable is the constant 1, or not. The idea is straightforward, sample the random variable multiple times, (each sample independently from previous sample to avoid bias) and check if all results were 1. If at least ...


2

Set are at a higher level of abstraction than algorithms. You can certainly analyze algorithms at that level of abstraction but that's not the usual level of abstraction for discussing algorithms, instead you'd refer to data structures such as stacks, vectors, lists, linked lists etc. Sets are instead used in formal modeling contexts (Z,Coq,Agda,F-Star) to ...


2

The certificate you propose might not be polynomial in the size of the input. The input size of the problem is $O(n^3 + \log k)$, while your certificate has size $\Omega(k \log n)$. This is not polynomial, e.g., for $k = 2^n$. Your certificate would work if you set it, e.g., to an empty list whenever $k = \Omega(\frac{n^2}{\log n})$, and modify the verifier ...


2

The Hamming distance between two length-$n$ vectors is the number of coordinates in which they differ. I've only ever seen it on finite alphabets, i.e. vectors in $\Sigma^n$ where $|\Sigma|\in \mathbb{N}$. In theory there is no problem with extending this to $\mathbb{R}$, but you may have to be careful with how you use equality of floats for instance. ...


2

L-reductions were defined by Papadimitriou and Yannakakis in their paper Optimization, approximation, and complexity classes. From the abstract: Furthermore, we show that a number of common optimization problems are complete for MAXSNP under a kind of careful transformation (called L-reduction) that preserves approximability. A survey of various related ...


2

A decision tree is a special kind of "program" which computes a function, usual from $\{0,1\}^n$ to $\{0,1\}$. Let's take an example from Wikipedia: A decision tree is a binary tree. Internal nodes are labeled by functions from a set $\mathcal{F}$ (more on this, later). Leaves are labeled by elements from $\{0,1\}$. Each internal node has one ...


1

The interpretation of your professor is "intuitively correct" (but still formally wrong). The notation $o(n)$ denotes the set of functions that grow less than linearly with $n$. That definition means that, if we look at databases $d$ whose number of entries $n$ grows towards infinity, the candidate database $c$ will agree with $d$ in all but a ...


1

Here is what the remark says: A code $C \subseteq A^n$ is $t$-error-correcting if for all $x \in C$ and $y \in A^n$ such that $d(x,y) \leq t$, all $z \in C$ other than $x$ satisfy $d(x,y) < d(z,y)$. When is a code not $t$-error-correcting according to this remark? A code $C \subseteq A^n$ is not $t$-error-correcting if there exist $x,z \in C$ and $y \...


1

I have only one thing to add to D.W.'s answer which is worth considering. This is Wikipedia's pseudocode for DPLL: function DPLL(Φ) if Φ is a consistent set of literals then return true; if Φ contains an empty clause then return false; for every unit clause {l} in Φ do Φ ← unit-propagate(l, Φ); for every literal l that ...


1

What you are finding is that there are multiple versions of DPLL, all of which might have the name DPLL attached to them, even though they are a little different in some specifics. If you need to distinguish between them, then I suggest you introduce your own terminology. I don't think it really matters which one you call the "one true DPLL algorithm&...


1

You will not find a reference for "the standard definition" of NP-hardness. Some authors restrict the notion "NP-hard" to decision problems only, and use the definition of reduction you mention in your question (which is sometimes referred to as a "Karp reduction" or "many-one reduction"). Other authors use the term ...


1

In the definition of SUBEXP, $\epsilon$ ranges over all positive reals. But you get the same definition if you ask that $\epsilon < \epsilon_0$, for an $\epsilon_0>0$ of your choice; if you ask that $\epsilon$ be rational; if you only go over $\epsilon = 1/n$; and so on. This is because DTIME is monotone: if $f \leq g$ then $\mathsf{DTIME}(f) \subseteq ...


1

"$O(n^2)$ is indeed an upper bound for the recurrence" means $T(n) \in O(n^2)$. That is, $\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \le c n^2$. "$\Omega(n^2)$ must be a lower bound for the recurrence" means $T(n) \in \Omega(n^2)$. That is $\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \ge c n^2$. This is exactly the same ...


1

AND I like red AND ripe apples. If the apple is red and the apple is ripe, then the result is true 1 and 1 makes 1 (true) The apple is green, so I don't like it 0 and 1 makes 0 (false) The apple is red but not ripe 1 and 0 makes 0 (false) OR I'll eat an apple if it's ripe OR if it's red The apple is red, but not ripe so I'll eat it 1 or 0 makes 1 (...


1

I interpret question 'why' as asking for the purpose. So imagine OR, AND and NOT as the simplest building blocks from which you can build almost anything else. (Just remember it as some kind of simplification: NAND gate seems to be more universal and simpler from electronic engineering point of view but is less intuitive for learning purposes) As an ...


1

You can look at it as two stages. The first stage is that we want some particular outcome, such as wanting a 1 if either of the (2) inputs is a 1. We call this an “OR” gate. Another outcome that people want is to get a 1 only if both inputs are a 1. We call this an AND gate. The final stage is that we want a particular gate for every possible ...


1

To answer this, I think it is best to go back to those early 'Truth Tables' you probably saw in algebra. The first ones you see are 'and' & 'or'. We have two statements #1 & #2 (usually called p & q) which can either be true or false. Then, when we test them we have a result (usually called r). For example, #1 p = I like red #2 q = I like dogs ...


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