168

Theoretical computer science could certainly be considered a branch of mathematics. This branch of computer science deals with computers and computer programs as mathematical objects. Theoretical computer scientists could be described as computer scientists who know little about computers. However, when people say "computer science" they usually include ...


106

A dictionary is just a function $\mathrm{Dict}\colon \mathrm{Keys} \rightarrow \mathrm{Values}\cup\{\epsilon\}$ where $\epsilon$ is a "null character" with the understanding that $\epsilon\notin\mathrm{Values}$. For example, let $\mathrm{Keys}=\{A,B,C,...,Z\}$, and $\mathrm{Values}=\mathbb{Z}$. Then, in your case, $$ \mathrm{Dict}(x)=\begin{cases} 1 & \...


78

From physics, I'm used to seeing the Kronecker delta,$$ {\delta}_{ij} \equiv \left\{ \begin{array}{lll} 1 &\text{if} & i=j \\ 0 &\text{else} \end{array} \right. _{,} $$and I think people who work with it find the slightly generalized notation$$ {\delta}_{\left[\text{condition}\right]} \equiv \left\{ \begin{array}{lll} 1 &\text{if} & \left[...


74

Goldbach's weak conjecture isn't a conjecture anymore, but before it was proved (in 2013), it had already been proved that it was true for every $n>e^{e^{16\,038}}$. It was not computationally possible to test it for all numbers $n\leqslant e^{e^{16\,038}}$ though.


68

Let $C$ and $M$ be the set of all things which are considered "computer science" and "mathematics", respectively. If I understand you correctly, your question is: Is $C\subset M$? If this is the case, your question is not well posed because neither $C$ nor $M$ are well defined. How do you draw the line between what is math and what is not math without ...


64

The expression b + (c > 0 ? 1 : 2) is not a ternary operator; it is a function of two variables. There is one operation that results in $a$. You can certainly define a function $$f(b,c)=\begin {cases} b+1&c \gt 0\\ b+2 & c \le 0 \end {cases}$$ You can also define functions with any number of inputs you want, so you can define $f(a,b,c)=a(b+c^...


57

A more general approach to this is given by topological sorting. In particular, a topological sort exists if and only if the graph is a directed acyclic graph. The 'algorithms' described in the other answers effectively perform a topological sort, in that they repeatedly remove vertices with no incoming/outgoing edges. For instance, a topological ordering ...


56

There are a bunch of teddy bears A, B, C, D and so on that are red on one side and blue on the other! (You choose how to color them) AND there are a bunch of 3 armed aliens with really long arms. Each alien grabs 3 teddy bear hands! (A teddy bear hand can be grabbed by more than one alien.) 3-SAT is the problem of whether you can color the teddy bears ...


52

In Concrete Mathematics by Graham, Knuth and Patashnik, the authors use the "Iverson bracket" notation: Square brackets around a statement represent $1$ if the statement is true and $0$ otherwise. Using this notation, you could write $$ a = b + 2 - [c \gt 0]. $$


51

Step 1. Since $A$ has no indegree it can't be part of any cycle. So remove it. We have now graph $G_1$. Step 2. Since $C$ has no indegree it can't be part of any cycle (in this new graph $G_1$). So remove it. We get $G_2$ Step 3. Now in $G_2$ nodes $B$ and $D$ have no indegree so remove them.


49

Some notorious problems of this kind are in discrete mathematics but involve a search space that is many magnitudes beyond what is feasible. For example, the values of certain Ramsey numbers or the existence of a Moore graph of degree 57.


46

This is a good question, but to dig into it we have to look at the underlying assumptions. First, for the purpose at hand, it doesn't really make sense to say that a number itself is random. There is a sense of a particular number being random from Kolmogorov complexity, but that is not what is intended here. Instead, what we are interested in might be ...


43

Yes, you can. This method is known as proof by exhaustion. Also, see computer-assisted proof. Edit: As others have noted, this of course works only for finite sets.


39

Basically, it looks like this: (Image rendered in POV-Ray by the author, using a recursively constructed mesh, some area lights and lots of anti-aliasing.) In the picture, the blue square on the $x$-$y$ plane represents the unit square $[0,1]^2$, and the yellow shape is the graph $z = x \oplus y$ over this square, where $\oplus$ denotes bitwise $\rm xor$. ...


37

A software engineer probably does not need to study calculus, and it is less likely to be useful than graph theory, elementary logic, study of algorithms, etc. Of course, if you are implementing algorithms for use in science and engineering, calculus and numerical methods for approximating calculus operations will show up all of the time. AI, on the other ...


33

The things you actually write on the paper or some other medium are not definable as any kind of mathematical objects. Mathematical structures can at most be used to model (or approximate) the real world structures. For example we might say that we can have strings of symbols of arbitrary length, but in the real world we would run out of paper or ink or ...


29

The page Coding The Matrix: Linear Algebra Through Computer Science Applications (see also this page) might be useful here. In the second page you read among others In this class, you will learn the concepts and methods of linear algebra, and how to use them to think about problems arising in computer science. I guess you have been giving a standard ...


29

I think your first question has been answered eloquently by others here. I'd just like to add a group of references for your second question. As a math major / CS minor, I was taught CS by people in "Dijkstra's school", which I would consider more rigorously grounded in mathematics than Knuth's. To get a taste of Dijkstra's ideas, you can read all his ...


29

Using the indicator function notation:$$a=b+1+\mathbb{1}_{(-\infty, 0]}(c)$$


28

Let us take your concrete example:- $$p(x) = a_0 + a_2x^2 + a_4x^4 + a_6x^6$$ $$q(x) = b_0 + b_4x^4 + b_6x^6 + b_8x^8$$ We can express the above two polynomials in vector format:- $$\mathbf{p}=[a_0,0,a_2,0,a_4,0,a_6]$$ $$\mathbf{q}=[b_0,0,0,0,b_4,0,b_6,0,b_8]$$ where the $k$th entry (for $k\in\{0,1,2,..\}$) represents the coefficient of $x^k$. Once we ...


28

This is a known property of the Leibniz–Gregory series, and has been used to actually compute $\pi$ to many digits using this series. It arises from the Euler–Maclaurin formula: $$\frac{\pi}{2} - 2 \sum_{k=1}^\frac{N}{2} \frac{(-1)^{k-1}}{2k-1} \sim \sum_{m=0}^\infty \frac{E_{2m}}{N^{2m+1}}$$ where $E_n$ are the Euler numbers. When $N$ (the number of terms) ...


26

In his book Diophantine equation,(page $257-258$) L.J.Mordell proved that the equation $$y(y+1)=x(x+1)(x+2)$$ has only the integer solutions $x=-1,-2,0,1,5.$


26

I would say that computer science is a branch of mathematics. Donald Knuth is a famous computer scientists and is also considered a great mathematician. He wrote a series of books called "The Art of Computer Programming" which is extremely rigorous and mathematical. Edit: To make my position more clear since it is apparently controversial. Almost all ...


26

We have $3(f+g+h)^2 = 3(f^2 + g^2 + h^2) + 6(fg + gh + hf) = 20(fg + gh + hf)$, so that both $f+g+h$ and $fg + gh + hf$ are divisible by $5$. Plugging in the roots of $(X-f)(X-g)(X-h) = X^3 - (f+g+h)X^2 + (fg+gh+hf)X - fgh$, we find that $f^3 \equiv g^3 \equiv h^3 \equiv fgh\pmod{5}$, which (by uniqueness of cube roots modulo $5$) is only possible if $f\...


26

There is no such book. If someone wants to implement a proof assistant based on type theory now, they can look at a) tutorial implementations b) papers c) source code of existing systems. The issue with a) is that it only covers a small fraction of real-world functionality and commonly presents naive solutions which don't scale and differ greatly from real-...


25

This is a reduction from undirected Hamilton Cycle to undirected Hamilton Path. It takes a graph $G$ and returns a graph $f(G)$ such that $G$ has a Hamilton Cycle iff $f(G)$ has a Hamilton Path. Given a graph $G = (V,E)$ we construct a graph $f(G)$ as follows. Let $v \in V$ be a vertex of G, and let $v',s,t \notin V$. We want to make $v'$ a "copy" of $v$, ...


25

It is not uncommon to hear ideas along the lines that computer science is computer programming without practical constraints theoretical computer science is computer science without physical constraints mathematics is computer science without finiteness constraints Each subject in the chain is seen as a limiting case of the one before, where some ...


25

Algebra is incredibly useful in computer science. I'll preface my answer with my opinion: I view a good portion of computer science as a branch of mathematics. So my answer will be quite broad. Note that my opinion is one that not everyone shares. Algebraic Combinatorics and Graph Theory: Recall Cayley's Theorem from group theory, which states that every ...


25

Determining for any statement if there is a proof with $n$ symbols or less is an $NP$ problem (i.e. the proof can be checked in polynomial time with respect to the length of the proof and the statement), that's probably the sense in which they meant that "P versus NP is itself NP". However, it does not really make sense to assign a complexity class ...


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