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

0
votes
0answers
10 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
34 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
58 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 ...
2
votes
0answers
23 views

Reversal distance of strings (with duplicates)

Note: If the following is true, then it would be best if you could just point me in the right direction, rather than giving a complete proof right away. Let $\Sigma$ be a finite alphabet and $s,t\in\...
1
vote
1answer
72 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
0answers
82 views
+50

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
16 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 [...
-2
votes
0answers
10 views

Can someone give me a hint on how to solve this lambda calculus related question?

et TRUE = \x y -> x let FALSE = \x y -> y let ITE = \b x y -> b x y let NOT = \b x y -> b y x let AND = \b1 b2 -> ITE b1 b2 FALSE let OR = \b1 b2 -> ITE b1 TRUE b2 -- YOU SHOULD ONLY ...
0
votes
1answer
83 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
42 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
17 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 ...
0
votes
1answer
49 views

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.

I'm a complete beginner at this, and was having trouble with this problem. looking at $T(n) = c(T(n/c) + 1)$. I'm pretty sure its in the form of f(n) = af(n/b) + Cnd I think the master theorem ...
0
votes
1answer
50 views

How do you solve a linear recurrence relation for $a_{n}$ given the solution

I'm a beginner who is starting to learn about linear recurrence relations. I've just come across a problem where I'm not sure how to progress. Going off of my notes linear recurrence was solved ...
0
votes
0answers
29 views

Calculation of CPU Utilization Problem

A computer, has an operating system occupying 1GB of memory. The following are the processes with memory sizes and their I/O wait percentages: A(512MB, 50%), B(128MB, 60%), C(64MB, 70%). If the ...
0
votes
1answer
14 views

determining lowest starting index for travelling around a circular array without a negative partial sum

Suppose I have a circular array of integers, for example: $$ [1,2,3,-4] $$ A trip starting at a particular index $i$, wrapping around, and ending right before index $i$ is successful if none of the ...
0
votes
1answer
22 views

Time Complexity of CLRS Optimal Parenthesis Algorithm

I am reading the Introduction to Algorithms CLRS book, and I am unsure about the time complexity of one of the algorithms that is a recursive algorithm that calls itself twice. This chain matrix ...
1
vote
1answer
17 views

$Show\:that\:B_A=\left\{w\in \sum ^{\ast }:\:\exists \:x\in \:A\:s.t\:\left|x\right|\le \left|w\right|\right\}\:is\:decidable\:$

$A\:is\:some\:language\:over\:\sum.\\Show\:that\:B_A=\left\{w\in \sum ^{\ast }:\:\exists x\in A\:s.t\:\left|x\right|\le \left|w\right|\right\}\:is\:decidable\:$ I thought to show a non-deterministic ...
0
votes
1answer
16 views

Creating Arbitrary Equation For Quality Metric

I am trying to come up with an equation for a quality metric based on 3 attributes: Defect-proneness (Scored as a decimal between 0 and 1 -> lower value is better) Maintainability (Scored as a ...
2
votes
0answers
39 views

Numerical methods for the computation of a square matrix determinant

I have found many different ways to compute the determinant of a square matrix we'll call A over the internet : using LU decomposition, using Cholesky decomposition on the dot product $transp(A) . A$, ...
2
votes
1answer
52 views

Time complexity for finding the nth Fibonacci number using matrices

I have a question about the time complexity of finding the nth Fibonacci number using matrices. I know that you can find $F_n$ from: $ \begin{pmatrix} 1 & 1\\ 1 & 0\\ \end{pmatrix}^n = \...
3
votes
0answers
20 views

Maximal distinct CNFs from list of conjunctions

I'm working on an algorithm for a product I'm writing. I believe the problem can be expressed best as some sort of manipulation of a Boolean algebra expression. But this is a new field for me. So I'm ...
2
votes
2answers
24 views

Is there a notation for iterated/repeat concatenation?

Given a string x and natural number y, is there a commonly used notation for a function that concatenates string x to itself y times? Example: $x = \mathrm{'foobar'}$ $y = 3$ $f(x,y)=\mathrm{'...
1
vote
1answer
34 views

Combine 2 DFAs to produce a new DFA that accept L1 U L2

I am trying to solve a problem where i have to create a new DFA that accept $L_1 \cup L_2$ where $L_1 = \{0^{3i} 1^{3j+1} 0^{3k+2} \mid i \in \mathbb{N}, j \in \mathbb{N},k\in \mathbb{N} \}$ and $L_2 =...
0
votes
1answer
22 views

P Langauage to NP Reduction in Polynomial Time

Let L be a language in P. Prove it is polynomial time reducible to any language in NP, including any language in P, which contains at least one string but doesn’t contain all the strings. I tried ...
0
votes
0answers
20 views

Stochastic knapsack problem with correlated item values - problem name

I am trying to find papers on solving a 0-1 knapsack problem, where the sizes of the items are deterministic and known and the values are drawn from known probabilistic distributions. Moreover, the ...
0
votes
1answer
32 views

let $L = \{\langle M \rangle \mid M \text { is a TM, } \forall x \in L(M), x^R \notin L(M)\}$. Prove/disprove $L\in RE \backslash R$

let $L = \{\langle M \rangle \mid M \text { is a TM, } \forall x \in L(M), x^R \notin L(M)\}$ ($x^R$ is the reverse of $x$) I need to determine and prove whether $L\in R , L\in RE \backslash R, \...
0
votes
3answers
73 views

Show this function is bounded by 1/n [closed]

Let $b>0$ and $f(n) = (\frac{3+2n}{1+2n})^b-1$. I need to show $f(n) \in O(\frac{1}{n})$. Is this even true?
1
vote
1answer
30 views

What is the number of functions $f$ from the set $\{1, 2, . . . , 2n\}$ to $\{1, 2, . . . , n\}$ so that $f(x) \leq \lceil x/2 \rceil$ for all $x$?

What is the number of functions $f$ from the set $\{1, 2, . . . , 2n\}$ to $\{1, 2, . . . , n\}$ so that $f(x) \leq \lceil x/2 \rceil$ for all $x$? I'm a complete beginner at solving something like ...
3
votes
2answers
79 views

How to solve simplex problem with $x_1 + x_2 + x_3 + x_4 =1$ as restriction?

So, there's this problem: maximize $$6x_1 + 8x_2 + 5x_3 + 9x_4$$ subject to $$x_1+x_2+x_3+x_4 = 1 \;\text{ knowing that }\; x_1, x_2, x_3, x_4\geq0$$ The solution is obvious: since the sum of ...
2
votes
1answer
26 views

Compute the worst case time complexity of the following algorithm, for i = 1 to n do for j = i to n^2 do print (i, j).

for i = 1 to n do for j = i to n^2 do print (i, j). So here is what I've got $\sum_{i=1}^n \ \sum_{j=i}^{n^{2}} \ $ $C\sum_{i=1}^n \ \sum_{j=...
0
votes
1answer
24 views

Prove whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$.

$f(n) = e^{n} \ln(n)$, $g(n) = 2^{n} \log(n)$ log can be assumed to be base $2$. Alright so I put this in the form $f(n) / g(n)$ and then used L'Hôpital's rule giving me $$ \frac { \dfrac{e^n}{n} +...
0
votes
0answers
22 views

Is this solution correct? Prove whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$

$f(n) = n + (\log n)^{2}$, $g(n) = n + \log(n^{2})$. log is assumed to be base 2 So I differentiated each of the functions $f(n)' = 1 + 2(\log n)$ $g(n)' = 1 + (2/n\ln(2))$ and then finding the ...
0
votes
2answers
39 views

Prove whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$. $f(n) = n + (\log n)^{2}$, $g(n) = n + \log(n^{2})$.

$f(n) = n + (\log n)^{2} , g(n) = n + \log(n^{2} ).$ Now so far I've done $g(n) = n+ 2\log(n)$ and then I think since its the same change to both, I can remove $n$. leaving me with $f(n) = (\log n)^...
1
vote
1answer
15 views

Upper and Lower shapes in Perlin Noise Generated Terrain

I am trying to learn about Perlin Noise and procedural generation. I am reading through an online tutorial about generating landscapes with noise, but I don't understand part of the author's ...
1
vote
1answer
91 views

Application of (Solomonoff) Algorithmic Probability formula?

Ray Solomonoff gives the Algorithmic Probability formula as, $$ P_M(x)=\sum_{i=1}^{\infty}2^{-|s_{i}(x)|} \tag{1} $$ ​​​If I understand the formula correctly, $M$ is a Turing machine ...
0
votes
2answers
42 views

Is this RSA problem solvable?

A secret message M has been encrypted using the RSA algorithm producing the cyphertext C=12. The public key for the RSA algorithm is e=3, n=51. Compute the decryption component d and hence decipher ...
0
votes
1answer
59 views

What is the number of one-to-one functions from the set $\{1, 2,\dots , n\}$ to the set $\{1, 2, \dots , 2n\}$

What is the number of one-to-one functions from the set $\{1, 2,\dots , n\}$ to the set $\{1, 2, \dots , 2n\}$ so that $2i − 1$ and $2i$ on the right-hand set are not mapped at the same time for all $...
0
votes
2answers
37 views

Proving $\log^n(n)=\omega(n^{\log(n)}) $

Proving $\log^n(n)=\omega(n^{\log(n)}) $ Hey everyone. I am trying to prove that $\displaystyle\lim_{n\to\infty}\frac{(\log n)^n}{n^{\log n}}=\infty $ (here $\log n= \log_2 n$) I've tried proving ...
2
votes
0answers
86 views

Implicit Euler method yields incorrect output - in depth and simple

We are given the system of PDEs $\begin{pmatrix}f_t \\ g_t\end{pmatrix} = i\begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}f_{xx}\\ g_{xx}\end{pmatrix}+i\begin{pmatrix}3 & -1 \\ -...
0
votes
0answers
12 views

Size of replicates needed to calculate MSE in R?

I'm calculating MSE for cauchy distribution estimators in R. My code is the following ...
4
votes
1answer
106 views

Solving the recurence $T(n) = T(n/5) + T(7n/10) + n$ using substitution method

I am not sure how to handle this problem given no base case. Is it enough to assume that $T(n/5) + T(7n/10) <= c(n/5) + c(7n/10)$, and substitute that back in? This seems like a weak way of proving ...
-1
votes
1answer
25 views

How to solve this harmonic progression ? summation $\sum _{i=1} ^{\log(n)-1} \frac 1 {\log(n)-i}$?

This question was actually derived from a time complexity recurrence relation question. Please also explain how is this a harmonic series.?$$\frac 1{\log (n)- i}$$ Explain how is this a harmonic ...
0
votes
1answer
19 views

Why does this definition of the 3-PARTITION problem imply that every set contains exactly 3 elements?

I have the following definition of the 3-PARTITION problem taken from this paper: https://www.sciencedirect.com/science/article/pii/0166218X93900853 Given $3m$ positive integers $a_1, a_2,...,a_{3m}$ ...
0
votes
0answers
23 views

Algorithm to arrange different-sized circles in a square area?

Suppose I have a large square and a set of $n$ circles, each with a different radius $r$, such that there exists some way to fit all the circles into the square. Is there an algorithm to find the "...
0
votes
1answer
24 views

How many triplets with index (i,j,k) in an array such that i < j and j < k?

Can someone give me a formula to calculate all possible triplets with index (i,j,k) in an array such that i < j and j < k? So far I've tried to find out what is the pattern on small arrays, ...
2
votes
4answers
75 views

Prove that among any set of 34 different positive integers that are at most 99, there is always a pair of numbers that differ by at most 2.

Alright, so I'm pretty new at this. I feel like this should be a pretty simple solution, but I don't know how to start. So here's where I was going If we have a set $\{1,2,...,99\}$ and then I start ...
0
votes
0answers
13 views

Polynomial reduction to $\Pi_2^p$

Suppose I have decision problem $L$ and $L'$ and $L$ is reducible to $L'$ in polynomial time. Suppose further, that $L$ is in $\Pi_2^p$ in the polynomial hierarchy. What can be said about the class of ...
0
votes
0answers
24 views

Byzantine Fault Tolerance Threshold of Bitcoin: 1/2 or 1/3?

Although, this question is related to the Bitcoin network; however, its calculation is more relative to the Mathematics. So, let's bring it up here: According to this answer: https://bitcoin....
2
votes
1answer
45 views

Representing Iterations in Math

I'm coming from a software engineering background and not a mathematical one. You may have to explain the exact notation to me but I would really appreciate it. I want to represent one of my processes ...
0
votes
1answer
35 views

Prove that for any three distinct positive integers, at least one will be greater than the xor of the other [closed]

That is, prove that for distinct positive integers $x$, $y$, and $z$, at least one of these integers will be greater than the bitwise XOR of the other two integers. The only "progress" I managed to ...