Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
0answers
27 views

Has there been any mathematical research relating to the natural semantic metalanguage theory?

This topic was called to my attention in an answer to my question in the philosophy community. https://philosophy.stackexchange.com/q/63580/35343 Though mathematics is not a "natural language", the ...
0
votes
0answers
15 views

Update an existing route with a set of pedestrian crossings

I am trying to route though a set of pedestrian crossings. I ask a route to some location service to get a default route, the problem with that route is that it does not include some waypoints (...
0
votes
0answers
25 views

Number of eulerian paths in an undirected connected graph between two given vertices?

Given a undirected connected graph G(V, E). Provide an optimal algorithm, which finds the number of eulerian paths between vertex 1 and vertex |V|. I was thinking about matrix multiplication, but I ...
-1
votes
0answers
20 views

Check if pair of numbers is in set of 4 numbers

I have a list of numbers 1 to 23, i need a very fast way of checking if any two numbers (order matters) (it could be same number twice) is in a set of 4 numbers. e.g ...
0
votes
0answers
33 views

Derive a bound for a tree with node having k left branches

We are given a binary tree of maximum level n and where each node can have a maximum $k$ left directed edge. $n$ is always greater than or equal to $k$. I want to know a bound on the number of nodes ...
1
vote
0answers
51 views

Question about big $O$ notation

We all know that exponential functions grow faster than polynomials. Let us consider the following function: $f(n) = n^{a_1} \cdot (\log n)^{a_2}\cdot (\log \log n)^{a_3} \cdot (\log \log \log n)^{a_4}...
0
votes
0answers
23 views

cputime in MatLab

I am using cputime in MatLab to computer time of a program (see the attached figure). There is a problem, that is the results are not identical. More precisely, four calculations give four different ...
-1
votes
0answers
13 views

Difference Entropy Output and Input [closed]

In a ternary channel with same probabilities for all inputs. I have H(X) entrance entropy and H(Y) output entropy. What does the difference of these 2 Entropy tell me?
0
votes
1answer
38 views

What kind of math should I learn before I tackle policy search PEGASUS research paper by Andrew Ng?

I provided the link below https://ai.stanford.edu/~ang/papers/uai00-pegasus.pdf the paper was referenced in the AI: Modern Approach book, and I would like to dive in depth into it. But my math is ...
0
votes
0answers
17 views

Proving language is not context free using pumping lemma

Hi I'm completely stuck on an exercise which is to prove this language is not context free using pumping lemma for context free languages: ...
0
votes
0answers
33 views

Finding small solutions to modular congruences

I was wondering what computational/algorithmic techniques can be used to solve a modular congruence when we are looking for a pair of small values. The specific problem is like this (the numbers are ...
0
votes
0answers
16 views

Transformation matrix maps pair of intersecting straight to pair of intersecting straight lines [closed]

In my Computer graphics mid-term exam, it was asked to prove, Transformation matrix maps pair of intersecting straight lines to intersecting straight lines. Here, transformation matrix is taken in ...
2
votes
0answers
55 views

Counting the Number of Lattice Points in an $n$-Dimensional Sphere

Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
2
votes
1answer
39 views

What exactly is significand?

per wiki, The significand is part of a number in scientific notation or a floating-point number, consisting of its significant digits. in this example $$123.45 = 0.12345 × 10^3$$ which part is The ...
0
votes
0answers
13 views

Non-computable composition of functions

I am working through "Computable Analysis", by Weihrauch, and I was wondering if anybody could help me with a problem? Section 2.1 question 9 asks us to show that given $g: \Sigma^{\omega} \to \Sigma^*...
0
votes
1answer
25 views

Converting IF condition to a mathematical equation

I am trying the formulate if conditions. i=1...10 p=1...5 j=1...50 k=1...7 C_ijpk=b_ik+LC_ik+CC_ik ∀ijt k∈ {1,2,3} I have three different LC_ik values and ...
0
votes
1answer
33 views

Red-Black-Tree Insertion & Deletion Complexity proof

I'm struggling with two propositions in my algorithms book. I'm unsure how to proof this. The insertion is abolutely logical that it takes up to O(log(n)) recoloring and at most one restructuring (as ...
3
votes
1answer
59 views

Restricted Totient Sums $\sum_{n=1}^{\sqrt {L-1}}\widehat \varphi(B_n,n)$

Let the Euler totient function be:$$ (1) \qquad \qquad\varphi(n) = \sum_{k=1, \atop gcd(k,n)=1}^{n}1$$ And let the following 2 functions be variations of the original Euler totient function: $$(2) \...
0
votes
0answers
19 views

Proof by resolution - showing there is no contradiction

For simpler questions involving proof by resolution, it is easy to see whether or not a contradiction can be found by inferring the empty clause, and somewhat easy to show there is no empty clause ...
1
vote
1answer
24 views

Describing indefinitely nested language generated by Context-Free Grammar

Grammar: $G=\{\{A, B, C\}, \{d_0, d_1\}, P, d_0\}$ Productions: $ 1) d_0 \rightarrow Ad_1 \\ 2) d_1 \rightarrow Ad_1B \\ 3) d_1 \rightarrow Bd_1A \\ 4) d_1 \rightarrow C \\ 5) d_1 \rightarrow ...
0
votes
1answer
20 views

is it possible to convert assignment of a set of boolean variables into a 3cnf propositions in polynomial time?

very interested in knowing if this conversion is possible, i.e if we can create a function that can be computed in a polynomial time is respect to the input size, so that for an input of boolean ...
0
votes
1answer
8 views

PDA for this CFL $L=\{a^i b^j c^k, k=i*j, i,j=0,1,2…\}$

I have troubles constructing pushdown automata for the following language: $L=\{a^i b^j c^k \mid k=i*j; \quad i,j=0,1,2...\}$ .I am not interested in the automata itself, just the idea of handling the ...
0
votes
0answers
33 views

Optimization as theorem proving?

There is sometimes need to find optimal rules, optimal policies, e.g. optimal Markov policy in symbolic form. E.g.see article about symbolic planning and hierarchical reinforcement learning. My ...
1
vote
1answer
45 views

What would be the explicit formula of a “dictionary” function / relation?

What would be the explicit formula of a " dictionary" function / relation that would put in the "dictionary order" all the words of a natural language ( having an alphabet)? I think that one of the ...
0
votes
1answer
24 views

How to present numbers in a large base (e.g. Sexagesimal)

When writing numbers in bases $2$ through $10$ it is common to simply write each digit in order without padding, for example $$(1.1)_{10}=(1.0\overline{0011})_2=(1.0\overline{2})_5$$ but, for large ...
1
vote
2answers
38 views

Number of one to one functions from the set {1, 2, . . . , n} to {1, 2, . . . , n} so that f(x) = x for some x and f(x) $\neq$ x for all the other x?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the setm {1, 2, . . . , n} so that f(x) = x for some x and f(x) $\neq$ x for all the other x? Alright so the fact ...
0
votes
0answers
24 views

Is this the correct generating function to determine the number of ways to choose k objects from n objects when the ith object appears at least 2i

Find the generating function to determine the number of ways to choose k objects from n objects when the ith object appears at least 2i times for 1 ≤ i ≤ n. So if the generating function for one ...
1
vote
0answers
43 views

Division by Mersenne primes

Mersenne primes are used in Computer Science and Cryptography because they support fast modulo computation. If $p$ is a Mersenne prime, $n \bmod p$ can be computed with just a few add and shift ...
3
votes
1answer
24 views

An interesting list ordering result based on skipping indexes by value entered

This is something interesting I've found while attempting to shuffle $n$ values in a list is a deterministic way intended to look "random-ish". The idea is that you sort a number of values $r$ from $0....
3
votes
4answers
148 views

The one bit computer scientist thought experiment

This is a thought experiment that has been noodeling around in my head for a while but I'm yet to come up with a good answer to it. Suppose a philosopher angry at almost staving due to a deadlock has ...
0
votes
1answer
26 views

Using the master theorem to find an expression for T(n) in Big Oh

Solve the recurrence relation $T(n)$ = $2T$($\frac n 3$) + $c\sqrt2^{logn}$ , T(1) = 1, by finding an expression for T(n) in big-Oh notation. So I'd like to solve this using the master theorem but I ...
0
votes
1answer
15 views

How to distribute n questions to n students with all students having the same questions but in different orders.

I am building an online exam platform. Let's say I have an MCQ test of 20 questions and say 60 students in a class. Is there a mathematical function or probability that I can compute to in a way that ...
5
votes
1answer
141 views

Summing the totient function $\sum_{k=1}^n \varphi(k)$

I explored some computer science/number theory challenges sites for fun, and they presented the following problem, exactly as follows: Let $$P(n) = \sum_{k=1}^n \varphi(k)$$ Find $P(10^{16})$ I ...
0
votes
1answer
20 views

How can I determine the form of a geometric series in a recurrence relation by using iterative substitution?

This question is based more in computer science however I think a mathematics approach is probably better. When solving a recurrence relation using iterative substitution you generally need to find ...
0
votes
0answers
39 views

How to estimate working time of algorithm in the form “Time is O(f(n))”

I really don't know how can I evaluate working time if given is graph problem, so every idea is welcome: 3-CUT. Let’s look at graph problem 3-CUT (maximum slit), where given graph G and number k. It ...
0
votes
1answer
18 views

Epsilon transition in NFA to DFA conversion

I worked through this conversion and it all makes sense except for one small part. Shouldn't $(q_1q_2)$ go to $q_1$ in the DFA on input $0$, not a self loop? We have state $q_iq_2$ to begin with ...
-1
votes
1answer
38 views

If a length is 1 and then it's elevated to two then what is it? [closed]

If $x=1$, then that means that $x^2 = 1$, also. Is the case the same if it has to do with lengths? That's if I got the $|x| = 1$ and then I raised to the power of two so $|x|^2= ...$ will it then be 2 ...
1
vote
0answers
12 views

Computing number of subsets with bounded sum

Suppose I have a set $\mathcal{S}$ of $N$ positive integers, and I want to compute the number of subsets of $\mathcal{S}$ whose elements sum to at most $M$. Clearly this problem will require ...
2
votes
1answer
55 views

Problem regards filling up a 2D grid with odd elements each

Let's assume I have a grid with x by x elements inside which x is an odd number, if I mark any ONE of these 8 cells as impassable [(1,0),(0,1),(x-2,0),(x-1,1),(0,x-2),(1,x-1),(x-2,x-1),(x-1,x-2)], I ...
2
votes
1answer
22 views

First-order logic task with limited clauses

I have the following axioms The sum of a natural number x and 0 is equal to x. The sum of a natural number x and the successor of a natural number y is equal to the successor of the sum of x and y. ...
0
votes
0answers
14 views

Calculating utilization of BITMAP protocol

i was reading around and didn't find any solution to my problem, either here in stackexchange, nor in recaps and tutorials online, so i am trying posting it here, hoping that i might get lucky and ...
0
votes
0answers
37 views

Solve the recurrence relation: $T(n) = T(n - \sqrt{\mathstrut n}) + T(\sqrt{\mathstrut n}) + O(n)$

I think that $T(\sqrt{\mathstrut n})$ part is $O(log(log(n)))$ but I cannot solve the whole problem. . Can anyone help? Edit: The formula appears while solving the following problem: If in quick-...
0
votes
1answer
86 views

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x? Alright so I did see this question, but it really ...
15
votes
2answers
220 views

Conjecture about reversal operations on strings (with duplicates)

Note: If you can find a proof of this, please give me just a hint first, so I can try to solve it on my own. Let $\Sigma$ be a finite alphabet (set of symbols) and $s,t\in\Sigma^\ast$ two strings (...
1
vote
1answer
79 views

What's the minimum step size that can be used in Euler's method before it becomes unreliable?

In particular, if Euler's method is implemented on a computer, what's the minimum step size that can be used before rounding errors cause the Euler approximations to become completely unreliable? I ...
0
votes
1answer
128 views

How does this convolution algorithm work mathmatically

I stumbled across this code which describes how you can construct smooth functions with compact support. Unfortunately, I'm not familiar with the programming language used so I can only guess what ...
0
votes
0answers
19 views

Stuck in proof for $AM[2] = BP \cdot NP$

I am trying to solve this problem from Arora, Barak Exe 8.3 . For showing $BP \cdot NP \subset AM[2]$ , I have the following Since $BP.NP = \{L | L \leq_R 3SAT\},\ \exists \text{ PTM M st. } \Pr [...
0
votes
1answer
91 views

How many ways are there to pick r objects from n objects when each object appears an odd number of times

I had misunderstood this problem earlier, and wanted to try again in the correct way, and I think I've got the correct start but I'm not sure how to progress. So from reading my notes here's what I ...
0
votes
1answer
45 views

Understanding the recurrence relation T(n) = c(T(n/c) + 1)

Solve the recurrence relation T(n) = c(T(n/c) + 1), T(1) = 1, by finding an expression for T(n) in big-Oh notation. Think about inputs of the form $c^k$. $$T(c^k)=cT(c^{k-1})+c=c^2T(c^{k-2})+c^2+...
0
votes
0answers
19 views

Asymptotic Big-Omega Proof

I wrote a different Big-O proof from what my professor wrote (which involved splitting up the inequality on the right of the implication into three parts and then proving each part individually). Can ...