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,648 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
0
answers
29
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....
-2
votes
0
answers
33
views
How do i even solve this DFA automata? [closed]
I need to draw a state diagram where the alpabets are {a,b}*: {w ∈ {a,b}∗ | the first two symbols in w match the last two symbols in w}
-1
votes
0
answers
47
views
A unifying view of $X=1+aX$: from geometric series to exponential functions to regular languages [closed]
I recently noticed that the same algebraic form $$X=1+aX$$ seems to produce analogous structures across very different mathematical settings.
Over the real numbers:
The equation $$p(x)=1+x,円p(x)$$ has ...
1
vote
2
answers
89
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:
...
0
votes
1
answer
65
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-...
0
votes
0
answers
237
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 ...
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) = ...
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 ...
6
votes
1
answer
231
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
630
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 ...
4
votes
2
answers
326
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]...
1
vote
0
answers
52
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 ...
0
votes
0
answers
75
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 ...
2
votes
1
answer
115
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 ...
3
votes
2
answers
116
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$ ...