# Questions tagged [computer-science]

All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For questions from scientific computing, use (computational-mathematics).

5,580 questions
Filter by
Sorted by
Tagged with
18 views

### Type theory reference including applications to multiple computer languages

I'm wondering if anyone could recommend me a good text on the application of type theory to computer languages (plural). What I'm looking for: Discusses formal theory in moderately-rigorous terms ...
• 1,378
10 views

• 21
801 views

### Math heavy programming challenge book.

I know how to code and some math. I love Project Euler because it combines both math and programming. Please recommend some math heavy programming challenge books as I can't seem to find any on Google....
1 vote
20 views

### Delaunay Triangulation but in 3D

I guess this is the right place to ask this question. Let me tell you why did I ask this question, so I have a pointcloud data that I want to calculate it's volume, I know that pointcloud lib has ...
• 11
41 views

### Is the language $L=\{0^{m}1^{n}0^{m\cdot n}\text{ with }m,n \geq 0\}$ context free? [closed]

I can't prove the language $L=\{0^{m}1^{n}0^{m\cdot n}\text{ with }m,n \geq 0\}$ is non-context free by using the pumping lemma. But at the mean time, I can't find a CFG that can generate it. Can ...
• 9
32 views

### Fixed quantities in Big O notation

Consider the following description of a random graph generation algorithm with parameters $n$ (number of vertices) and $m$ (number of edges). All iterations add an edge except those where a ...
• 3,468
20 views

### Finding minimal injective projection [closed]

Suppose there is a set of axes $S = \{X_0, \ldots , X_n\}$ and a set of points $P = \{p_0, \ldots , p_m \}$; A projection $f: S \stackrel{f}{\longmapsto} s$ is called minimal if $s$ has the fewest ...
1 vote
67 views

### What does "any polynomial dominates any logarithm" mean here?

My textbook states that any polynomial dominates any logarithm: $n$ dominates $(\log n)^3$. This also means, for example, that $n^2$ dominates $n\log n$ However, it wasn't clear to me what the ...
• 3,019
87 views

### Why does $\lim _{x \rightarrow \infty} \frac{f(x)}{g(x)} = L \implies f = \Theta(g)$ not hold when $L=0$?

I am currently seeing a contradiction from my use of the "theorem" For any $2$ functions $f : \mathbb{Z}^{+} \rightarrow \mathbb{R}^{+}$ and $g: \mathbb{Z}^{+} \rightarrow \mathbb{R}^{+}$, ...
• 3,019
37 views

• 3,019
1 vote
58 views

### Tight bound proof

Suppose that for a classifier, the worst-case error rate is shown to be $\leq \frac{1}{4}$. I want to prove that $\frac{1}{4}$ is a tight upper bound. To do so, my approach is that it is sufficient to ...
• 353
49 views

### A proof for the statement: The 3-Dimensional matching problem is NP-Complete

The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite $3$-hypergraph with ...
• 3,468
49 views

### Proof that if a graph has edge connectivity 3, then the girth is bounded by the number of nodes divided by two + 1, g(G) <= |V(G)| / 2 + 1

I've not been able to solve this problem for a week now. My idea was that I start with a circle with n nodes and because the edge connectivity is 3, every node must have at least 3 neighbours, so to ...
• 11
44 views

### Software language specification: null VS empty objects.

I have noticed that in software language specifications, there is pretty much always a NULL element and I am wondering if it is strictly necessary and how it maps to algebraic structures, given that ...
• 253
59 views

### How does $G_n$ relate to $F_n$ here? [duplicate]

Let $F_n$ be the $n$th Fibonacci number, i.e $$F_n=\left\{\begin{array}{cl}F_{n-1}+F_{n-2} & \text { if } n>1 \\ 1 & \text { if } n=1 \\ 0 & \text { if } n=0\end{array}\right.$$ and ...
• 3,019
50 views

### How to prove the recursively defined set L' is equal to L?

In the book https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/resources/mit6_042js15_textbook/ Page 199,there is an excercise on recursive sets and structural induction ...
23 views

### Number of significant digits when computing percentages on prices

I have two numbers total and partial that are always rounded to two decimals as they are prices in currencies that have cents (...
• 101
73 views

### How to define the reverse of a string recursively and then prove that : $Reverse(s*t)=Reverse(t)*Reverse(s)$?

I was doing the excercises of section 6.5 of the book Mathematics for Computer Science revised Monday 18th May, 2015, of the MIT opencourseware(https://ocw.mit.edu/courses/6-042j-mathematics-for-...
52 views

### Unclear evaluation of brackets in $\lambda$-Calculus

I have problems with evaluating this $\lambda$-Expression. $$(\lambda x.\lambda y.x(yx))\ (\lambda z.w)$$ The result should be, according to online calculators, $\lambda y.w$. But Iam really confused. ...
• 77
59 views

### Expected time to receive all n numbers at least once [duplicate]

Consider the following problem: every second we receive a random number from the set $A = \{1, \ldots, n\}$. We stop when we have received all $n$ numbers at least once. We want to know the ...
55 views

### Taking K elements from an infinite set sum, the expectation of getting a duplicate element exactly the Kth time

First, the probability of selecting $k$ elements from an $n$-element set, where the $k$th selection is the first time a duplicate occurs, is given by: $$\frac{\binom{n}{k-1} (k-1)!(k-1)}{n^k}$$...
87 views

### What's the behaviour of $\partial(q, a)=\emptyset$ on NFA?

Given an NFA say $N=(Q,\Sigma, q_0, \partial, F_Q)$, where $\partial: Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal{P}(Q)$. It's confusing about the behavior of say $\partial(q, a)=\emptyset$ for any ...
29 views

26 views

### Problem understanding proof about deterministic pushdown automaton

So I already posted this in Computer Science Stack Exchange but haven't received any real answers and my exam is tomorrow, so I'll post it here too hoping for some clarification: I'm having problem ...
1 vote
23 views

Suppose we have a system like this (the actual numbers and structure don't matter): $$P(a_1) = 0.28, P(a_2) = 0.36, P(a_3) = 0.41,\\ P(a_1 \cup a_2) = 0.59, P(a_1 \cup a_3) = 0.6, P(a_2 \cup a_3) = 0.... 1 vote 0 answers 29 views ### Comparing functions with regard to runtime complexity Just started studying runtime complexity, and I'm starting to compare functions to determine whether one or the other is "faster". I've got five definitions, which can be condensed into ... • 214 0 votes 0 answers 27 views ### Asymptotic analysis of (\log n)^{\log n} vs n^{\log \log n} What is the most informative relationship between the functions$$\begin{align*} f(n) &= (\log n) ^ {\log n} \\ g(n) &= n ^ {\log \log n} \end{align*} out of $f = O(g)$, $f = \Omega (g)$, $f ... • 1 1 vote 0 answers 92 views ### What is the proof that Term Finding in Calculus of Constructions ($\lambda{C}\$) is undecidable?

It is mentioned in a textbook "Type Theory and Formal Proof: An Introduction", but couldn't find the paper or proof anywhere on the internet. To quote the textbook: The question of Term ...
• 157
1 vote