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,646 questions
-1 votes
0 answers
47 views
Practical Applications of Polynomials and Types [closed]
Context: I am testing 8 different root finding algorithms on their efficiency on finding roots of different polynomials. However, on its own, random polynomials (meaning degree and coefficients are ...
- 29
0 votes
0 answers
38 views
Determiniing max roundness of number in an array
I'm trying to solve the following Codeforces question (https://codeforces.com/contest/837/problem/D), and I feel like I have a solution that's very close but is probably still over the time constraint....
1 vote
2 answers
112 views
How does this CFG enforce the inequality $0^a 1^b 0^c$ where $a < b + c$ and $a, b, c \geq 0$?
I am studying Context-free Languages, and my professor gave as homework the following language $$ 0^a 1^b 0^c \quad where \quad a < b + c \quad and \quad a,b,c \ge 0 $$ My friend gave this answer: ...
- 97
0 votes
1 answer
68 views
If a graph has at least 3 vertices (A,B,C) and there are 2 paths between A,B as well as 2 paths between B,C prove there is/n’t 2 paths between A,C
An undirected graph G contains at least 3 vertices (A,B,C). A and B have two edge-disjoint paths; B and C also have two edge-disjoint paths. Can I conclude that A and C also have two edge disjoint-...
- 11
0 votes
0 answers
243 views
In binary subtraction, is it possible to apply the mathematical notion of borrowing expecting a result equivalent to a two's complement calculation?
TL;DR. Question in a very short fashion could be: In subtraction of two binary numbers, minuend smaller than subtrahend and using just (school) borrowing method (not two's complement, etc), how do ...
- 109
0 votes
0 answers
36 views
Can lasso selection in Plotly interactive plots describe rational point density?
I am exploring the number of rational points on $\mathbb{P}^2(\mathbb{})$ with bounded height, for example, height less than or equal to 32. More specifically, I am calculating $$N_{\mathbb{P^2}}(B) = ...
- 13
0 votes
1 answer
32 views
analysis of the difference in the description of statistical distributions obtained mathematically/physically/computer-generated?
I plot the Gaussian distribution based on the mathematical definition and using the np.random.normal generator: Next, using different interval steps and other parameters, I subtracted both twice to ...
- 3
6 votes
1 answer
236 views
A supplement to "FROM FREGE TO GÖDEL A Source Book in Mathematical Logic, 1879-1931" for developments on type theory and computation
This is a cross-posting from Computer Science SE. (Some background - Its actually the second time I am posting this question here. At the first time I was advised to post it on 'Histoy of maths SE', ...
5 votes
2 answers
651 views
Proof that NP is a subset of EXP
I would like to clarify a misunderstanding I have about the proof that all NP problems can be solved in exponential time. The argument as I understand it is that you can simply test all possible ...
- 319
4 votes
2 answers
336 views
Is there any algorithm which can find a common divisor of two polynomials modulo $p^k$?
Let us consider two monic polynomials $f(X), g(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$. Now, we call $h(X)$ is a divisor of $f(X)$, if there exists a $l(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]...
- 4,295
1 vote
0 answers
54 views
Prove that the zig-zag product of $G$ and $H$ (where $H$ is the smaller of the two) lifts $H^2$
Prove that the zig-zag product of $G$ and $H$ (where $H$ is the smaller of the two) lifts $H^2$. I was reading Expander Graphs and their Applications (Lecture notes for a course by Nati Linial and ...
- 1,811
0 votes
0 answers
78 views
Most Important Asymmetric Computational Problems in Mathematics and Beyond.
I’m interested in computational problems that are asymmetric: problems where finding a solution is hard, but verifying a candidate solution is easy. For example, in the approximate nearest neighbour ...
- 793
2 votes
1 answer
129 views
How to analytically find the intersection of two cubic Bezier curves in general?
You can find the intersection points of two Bezier curves fully analytically using a technique called implicitization. It's nearly fully analytical, as you have to find the roots of a 9th-degree ...
- 125
3 votes
2 answers
123 views
Random partitions by using hash functions?
I am looking for a practical(!) way to create many different random partitions of a large set, and then to identify efficiently into which partition some elements of the set belong. Details $\Omega$ ...
- 2,799
2 votes
1 answer
79 views
Lambda calculus, $M$ does (doesn't) have a normal form. Find $MI$ that doesn't (does) have a normal form. [closed]
I'm trying to construct terms $M_1$, $M_2$ such that $M_1$ has a normal form, but $M_1I$ doesn't. $M_2$ doesn't have a normal form, but $M_2I$ does. This is somewhat related to these two questions, $...
- 125