Skip to main content

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).

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user3716267's user avatar
  • 1,378
0 votes
0 answers
10 views

Unknown or hidden generator under exponentiation of singular finite matrices digital signature attempt.

My question is, in the following signature scheme, if there's any algebraic attack to apply to break it. I ask here in math.se as it's mostly algebraic, and has raised no interest in crypto.se $\...
daniel's user avatar
  • 101
-2 votes
0 answers
31 views

Prove that $A=\{a^nb^nc^md^m | \geq 0\}$ Is that grammar ambiguous or not? [closed]

Give a context-free grammar that generates the language $A=\{a^nb^nc^md^m | \geq 0\}$ Is that grammar ambiguous? Why or why not?
pro yell's user avatar
-1 votes
0 answers
30 views

Generate trajectory between 2 points to achieve a desired momentum

I have 2 points and I need to find a path between them to maximize momentum. You can consider this as a trajectory of a Racquet hitting a tennis ball. Current_Trajectory In the image above, the ...
Pratham's user avatar
2 votes
0 answers
37 views

Maximum of $M$ random variables which are the maximum of $m$ normal distributed variables.

Let $X_{i,1}, \dots, X_{i, m}$ be a collection of normally distributed random variables $\mathcal{N}(0,1)$, and let $X_{i, (m)} = \max_{j\leq m}X_{i, j}$. I know from extreme value theory that $X_{i, ...
Faber's user avatar
  • 21
6 votes
3 answers
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....
Harshit Bujar Baruah's user avatar
1 vote
0 answers
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 ...
Danendra's user avatar
-1 votes
0 answers
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 ...
Pit's user avatar
  • 9
-1 votes
0 answers
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 ...
lafinur's user avatar
  • 3,468
-1 votes
0 answers
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 ...
multus's user avatar
  • 1
1 vote
0 answers
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 ...
Princess Mia's user avatar
  • 3,019
2 votes
3 answers
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}^{+}$, ...
Princess Mia's user avatar
  • 3,019
0 votes
0 answers
37 views

Proving there exist $g,h$ where $g = \Theta(h)$ and $f(x) = g(x) - h(x)$ for a function $f$

I am trying to prove that for any function $f : \mathbb{Z}^{+}\rightarrow \mathbb{R}^{+}$, there exist $2$ functions $g : \mathbb{Z}^{+}\rightarrow \mathbb{R}^{+}$ and $h : \mathbb{Z}^{+}\rightarrow \...
Princess Mia's user avatar
  • 3,019
0 votes
1 answer
91 views

Must both conditions of operator "OR ($\vee$)" be defined in mathematics? [closed]

I am in the process of writing an article and to explain my question, am providing to you a smaller instance of my wondering so that you can understand it, suppose that $A=\{0,1\}$ and that I define ...
JKHA's user avatar
  • 131
-5 votes
1 answer
49 views

Question about concrete mathematics double summation derivation [closed]

How did the author in the image convert the summation into a double summation? I can see how the double summation turns into the sum of squared integers but how would you go about converting the sum ...
adeldude13's user avatar
0 votes
1 answer
54 views

Proving $f + c = O(f)$ doesn't always hold- where is my mistake?

I seem to have proved the following statement false: that for any function $f : \mathbb{Z}^{+}\rightarrow \mathbb{R}^{+}$ and any $c \in \mathbb{R}, f +c = O(f)$, where for any $2$ functions $f : \...
Princess Mia's user avatar
  • 3,019
1 vote
0 answers
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 ...
David's user avatar
  • 353
0 votes
1 answer
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 ...
lafinur's user avatar
  • 3,468
0 votes
1 answer
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 ...
JR03's user avatar
  • 11
0 votes
0 answers
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 ...
Barzi2001's user avatar
  • 253
0 votes
0 answers
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 ...
Princess Mia's user avatar
  • 3,019
-2 votes
0 answers
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 ...
Jery Lazman's user avatar
0 votes
0 answers
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 (...
felix's user avatar
  • 101
0 votes
1 answer
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-...
Javier Lázaro's user avatar
2 votes
1 answer
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. ...
Flairo's user avatar
  • 77
0 votes
1 answer
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 ...
Sharuk0's user avatar
2 votes
1 answer
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} $$...
Adan Mike's user avatar
0 votes
1 answer
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 ...
linear_combinatori_probabi's user avatar
0 votes
0 answers
29 views

Conditional Probability of Byte Being Smaller Than the Max in a Sequence

I have the following byte sequence. $X, A, B_1, \ldots, B_h$ are discrete i.i.d. random values in $[0,255]$. I want to simplify the probability $$ P(X < \max(A,B_1,\ldots,B_{h-1})\mid\max(B_1,\...
Cutaraca's user avatar
  • 143
0 votes
0 answers
21 views

Converting generalized nondeterministic finite automata (GNFA) into regular expressions

When converting from a GNFA to a regular expression, we systematically remove states from the GNFA until we are left with just the start and accept state such that the transition arrow from the former ...
Michael24601's user avatar
-1 votes
2 answers
57 views

Why $d^*(q, \epsilon)$ has definition when $d(q, \varepsilon)$ does not in DFA?

I'm reading an online book about DFA and NFA but it confuses me. Given a DFA say $D=(Q,\Sigma, q_0, \delta, F_Q)$, its transition function is a total function defined on every symbol from a given ...
linear_combinatori_probabi's user avatar
0 votes
0 answers
39 views

Calculating N evenly spaced points on a ringed torus surface(not randomly)

I have been trying to find a optimised solution for calculating the x, y, z of a point that lives along the surface of the torus and is equally spaced out like other points. The naive approach is to ...
McBrincie212's user avatar
2 votes
2 answers
110 views

ODE book for a computer science researcher (Birkoff/Rota vs Arnold)

I've have been looking for a book on ODEs and have narrowed it down to 2 candidates: Birkoff and Rota's 'ordinary differential equations' or Arnold's 'ordinary differential equations: 3rd edition'. ...
ctk's user avatar
  • 61
1 vote
2 answers
64 views

XOR sum of array

When you are given an array of even number of elements: [$a_1$ $a_2$ $a_3$ ….. $a_n$] ($n$ is even) Assume the $a_i$ are not all zero Let $S$ = the XOR sum of all these original elements You will ...
Ashishkabaab's user avatar
2 votes
2 answers
224 views

What does it mean when the transition function of a NFA returns an empty set?

Given a NFA, $N = (Q, \Sigma, q_0, \partial, F_Q)$, where $\partial$ is the transition function $Q \times (\Sigma \cup \{ \varepsilon \} ) \to \mathcal{P}(Q) $. So $\partial(q, a)$ returns a set, ...
linear_combinatori_probabi's user avatar
1 vote
1 answer
88 views

What is the computational complexity of generalized Long Live the Queen?

Consider the following model of computation: The computer's memory consists of $n$ registers denoted $r_1, ..., r_n$, each holding an integer. In the following, an affine combination means an ...
Naomi Zhang's user avatar
0 votes
0 answers
31 views

Formalities on loop invariant - algorithms

When proving an algorithm using a loop invariant, we need to check these three things. The loop invariant holds before the loop is entered (initialization) If the loop invariant holds before the loop ...
Agustin G.'s user avatar
0 votes
0 answers
42 views

Definition of carrier map/ task for two processes

In distributed computing, we define a carrier map to be a map between a graph $\mathcal{G}$ and the power set $2^\mathcal{H}$ of a graph $\mathcal{H}$ s.t, for simplices $\sigma$ and $\tau$ of $\...
user2795243's user avatar
0 votes
1 answer
38 views

Is there a technique for solving magic square-style puzzle using matrices on pen and paper?

The cells (in the puzzle below) must be filled with integers in {1,2,...,12} and they must all be distinct. The numbers on the outside indicate the sum of the cells. For example, the 1st row's cells ...
lightyourassonfire's user avatar
0 votes
0 answers
11 views

For $n,m \geq 1$, when do exist $p_1,\dots,p_n \in S_m$ so that they coordinate-wise map $X$ to $X'$, where $X,X' \subset \{1,\dots,m\}^n, |X|=|X'|$?

Suppose $n,m \in \mathbb{N}$. Let $Y = \{1,\dots,m\}^n$. Suppose $p_i \in S_m, i = 1,\dots,n$. Define $P_{p_1,\dots,p_n}: Y \rightarrow Y$ as follows: $\forall y=(y_1,\dots,y_n) \in Y, P(y) = (p_1(y_1)...
H-a-y-K's user avatar
  • 729
2 votes
1 answer
63 views

Is this looser case of the maximal clique(connected subgraph) problem also hard?

Suppose $n,m \in \mathbb{N}$. Let $Y = \{1,\dots,m\}^n$. We'll call vectors $(x_1,\dots,x_n), (y_1,\dots,y_n) \in Y$ independent iff $\forall 1 \leq i \leq n, x_i \neq y_i$. There can be at most $m$ ...
H-a-y-K's user avatar
  • 729
0 votes
0 answers
23 views

Bounding d-regular graph traversal length for every starting node and every traversal

Question: (Past exam question i'm using to revise) Let $G = (V,E)$. A connected d-regular graph. Let $v_1 \in V$. Assume that at each node, the ends of the edges incident with the node are labelled $1,...
Willow's user avatar
  • 1
0 votes
0 answers
15 views

The elements of a list of length n that take the greatest number of function calls to be found using binary search

I was wondering if there was any information on determining the indices of the elements that take the greatest number of function calls to be found, if binary search is used to find the element, in a ...
nazorated's user avatar
1 vote
2 answers
68 views

How many isomorphism classes are there of strings of length $n$ over alphabet $\Sigma$ of size $k$?

Isomorphisms of Strings. $$ s = aa \simeq bb\\ s = ab \simeq ba $$ So the set of strings over a 2-letter alphabet of length 2 have merely 2 isomorphism classes. $$ s = aaa \simeq bbb \\ s = aab \simeq ...
SeekingAMathGeekGirlfriend's user avatar
0 votes
1 answer
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 ...
lazyelekid's user avatar
1 vote
1 answer
23 views

General Solutions to Probabilistic Systems

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....
Leo Peckham padrillium's user avatar
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 ...
John0207's user avatar
  • 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 ...
jim's user avatar
  • 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 ...
Vivek Joshy's user avatar
1 vote
0 answers
61 views

Mathematical and Intuitive understanding of "Optimal Substructure"

Wikipedia formally puts the definition of optimal substructure as below: "A slightly more formal definition of optimal substructure can be given. Let a "problem" be a collection of &...
Floatoss's user avatar
  • 167

1
2 3 4 5
112