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

learn more… | top users | synonyms

3
votes
1answer
23 views

How to compute $\cos(x)$ within $n$ digit accuracy when $x = \sqrt{y}$ with $y \in \mathbb{N}$

How does one compute $\cos(x)$ within desired $n$ digit accuracy when $x = \sqrt{y}$ with $y \in \mathbb{N}$ and $x$ is not rational? The reason I am asking this question is that calculators ...
2
votes
1answer
54 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
0
votes
1answer
22 views

Use the Pumping Lemma to prove that $L=\{a^{m}b^{2^{n}} \}$ is not regular.

Normally pumping lemma proofs aren't too hard; you just experiment with different values of $i$ and sort of stumble on the solution. However, this problem is really bugging me and I am spending a lot ...
0
votes
1answer
25 views

How would you apply the Greedy technique in this situation/why wouldn't it work?

I am going over the Rod Cutting Problem The author states "Selling a rod of length $i$ units earns $P$[i] dollars." Here is the table $P$ for this problem I'am currently going over this question ...
1
vote
1answer
34 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
0
votes
0answers
25 views

What's the mathematical model of Consistent Hash?

What's the mathematical model of Consistent Hash? There are several implementations: Karger's implementation using a bucket cycle: Jump Consistent Hash [Highest Random Weight (HRW)][3] hashing: ...
1
vote
1answer
82 views

Undecidable definition of pure function

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
1
vote
1answer
24 views

What does the notation $\{ \pm 1 \}^X$ in relation to functions and hypothesis classes means in the context of PAC learning over half spaces?

I was reading the following paper (on PAC learning over half-spaces) and encountered the following notation for a hypothesis class (on page 4): $$\mathcal{H} \subset \{ \pm 1 \}^X$$ However, it was ...
0
votes
0answers
41 views

About Katz centrality

I am studying Graph Theory and Network Analysis, I have this measurement formula which called Katz centrality: My question is: why $A^k$ will grow [infinitely] in $k$ for most cases. As I think ...
1
vote
1answer
95 views

Struggling with difference between greedy and naive but optimal algorithms? (Graph theory)

I've been thinking about the following problem for quite a while and tried multiple solutions, but I'm having difficulty telling the difference between a greedy algorithm and an inefficient naive ...
0
votes
0answers
10 views

Is my LL(1) parse table correct?

I have the following Grammar: ...
0
votes
2answers
301 views

Why are every finite language decidable?

I don't understand why every finite language is decidable. For example, if I have an infinite set of strings L over an alphabet E, why is there a Turing Machine M that decides L? I understand the ...
0
votes
1answer
55 views

A formula that, when plotted, yields its own display

I've just seen a video on Tupper's self-referential formula. When I heard that this formula was not at all self-referential but merely a simple way to generate every possible $17\times 107$ dot matrix ...
0
votes
2answers
42 views

Converting an NFA to DFA

I am atttempting to convert an NFA into an equivalent DFA. I did it, but i am not sure if it is correct. If anyone can please take a look at let me know if it is correct or if there is something wrong ...
3
votes
3answers
73 views

Wouldn't each addition take time $O(n)$?

I am going over the asymptotic runtime of regular matrix multiplication. Here is a lecture slide I am referencing(too much to type out, shown below), from Algorithms Everything makes sense up ...
1
vote
0answers
25 views

Learning Booth's Algorithm, I Can't Find the Issue on Final Result

I am practicing using Booth's Algorithm to multiply a positive number and a negative number (specifically the problem is $-12 \times 4$). I have included my attempt, but I can't find the issue. If ...
0
votes
1answer
20 views

How do I input this Boolean Expression into a K map?

Determine the minimum SOP, sum of products expression using K-Map F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’ Do i have to actually simplify it first by multiplying ...
1
vote
3answers
47 views

How to apply Master theorem to this relation?

This is the definition of master theorem I am using(from Master Theorem) I am trying to use that master theorem to find the tight bound for this relation $T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$ ...
0
votes
0answers
15 views

Torelli Shanks Algorithm - Repeated Squarring Method

This algorithm is using when you want to find a square root of a number in a given moduli. I can't see the idea behind this algorithm, so can someone explain it in a simple way?
1
vote
3answers
55 views

How to find the solution of $T(n,m) = T((n-1),m) + T(n,(m-1))$ in terms of big $O$ notation?

I would like to solve the recurrence $T(n,m) = T((n-1),m) + T(n,(m-1))$. I think the solution is $$O(2^{n+m})$$ because in every step you can reduce either $n$ or $m$ by one or not, but I can not ...
2
votes
1answer
28 views

Proving a language $L$ is in $\mathrm{co\text{-}NP}$ if $| L \cap \{0,1\}^n | \in \operatorname{poly}(n)$ for all $n$

Let $L \in NP$ such that $|L \cap \{0,1\}^n|=\operatorname{poly}(n)$ for all $n$. Prove that $L \in \mathrm{co\text{-}NP}$. If I understand the problem correctly, in words this says that "for any ...
1
vote
1answer
39 views

How to simplify Boolean Expression $\bar B + \bar C (B + A)$

I trying to figure out how $ \bar B + \bar C (B + A)$ simplifies to $ \bar B + \bar C$.
3
votes
2answers
130 views

What is a good book for reviewing high school math, and preparing for university?

I'm signing up for University soon (Compsci program) as a mature student. It's been a long time since I've done any math, and I went as far as grade 11 in high school. So, I'm looking for a book that ...
1
vote
0answers
20 views

Changed matrix dimensions - now formula doesnt work. Related to computer science

I'm writing a computer code to solve a problem, and I ran into some difficulties. This is not a coding question, my problem is purely mathematical, I will explain. We have a matrix $M\in Mat(\mathbb ...
1
vote
1answer
25 views

Entropy Calculation and derivation of logarithm

I have probabilities as $$p_1 = 0.4,\ p_2 = 0.3,\ p_3=0.2,\ p_4=0.1$$ hence entropy is given by: $$H(x) = -\big(0.4\cdot \log_2(0.4) + 0.3\cdot \log_2(0.3) + 0.2\cdot \log_2(0.2) + 0.1\cdot ...
0
votes
1answer
26 views

NDFSM Transition State Network

My coursework question asks me to "Draw a State Transition for the nondeterministic finite state machine (NDFSM)" from a state transition table. By following the examples in our lecture materials, ...
4
votes
1answer
139 views

Why do we divide or multiply by 2 when converting binary?

Trying to understand the fundamentals of binary rather than just following steps, I wanted to know why do we multiply by 2 to convert a decimal (0.5, 0.25) to a binary and why do we divide by 2 when ...
0
votes
1answer
23 views

Context Free Grammer (CFG) for a language

Consider the language above $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y : x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$ I need define a CFG for this language. I've tried couple of ...
1
vote
1answer
85 views

Inverting a map from a finite 3D grid to 1D

I need help with this mathematics question. I have made a program on the computer that flattens a 3D array into a 1D array. A 3D array needs an x, y and z but by using this formula (max x * max y * ...
1
vote
2answers
51 views

Quick solution check for the TSP

Given a solution for the Boolean satisfiability or the Hamilton cycle problem it's obvious whether it's true or not, but how does one quickly check whether a solution for the TSP (travelling salesman ...
1
vote
1answer
24 views

$2^n=na_n+na_{n-1}-a_{n-1}$ by range transformation

I want to range transform $2^n=na_n+na_{n-1}-a_{n-1}$ to get rid of the $2^n$ term and then solve it with any other method (seems like telescoping will work once it's reduced). I've tried ...
0
votes
0answers
19 views

Problem with DES Encryption

If the input string to a round of DES is 11001100 · · · 1100 = ‘1100 × 16′ and if the round key is 1111 . . . 111 (‘1 × 48′), Then how can I calculate the 20th and 33rd output bits ? This was an ...
0
votes
1answer
18 views

Proving $1+2CZ+3C^2Z^2+…=1/(1-CZ)^2$, considering $\sum\limits_{i=1}^{\infty}c^iZ^i=(1-CZ)(1+2CZ+3C^2Z^2+…)$

I'm told that we can prove this common identity for solving generating functions: $1+2CZ+3C^2Z^2+....=1/(1-CZ)^2$ Using only the property ...
0
votes
0answers
43 views

algorithm for generating a random non-degenerate matrix over $[0,1 ]$?

I want to generate a random matrix $V\in [0,1]^{(n+1)\times n}$(not necessarily being binary ), such that for each row of $V$, there is at least one component is $1,$ and at least one component is ...
0
votes
1answer
19 views

Demonstrating Strassen's method using domain transformation: $T(n)=7T(n/2)+an^2$

I want to solve the recurrence for Strassen's method (for multiplying square matrices) with domain transformation and get a closed form. The equation is given below: $T(n)=b$, at $n=2$ ...
1
vote
2answers
43 views

The “Smooth Factor” in a number sequence

I'm trying to figure out a programming problem that has mathematical foundations. The problem says: For an array $$a = a_1, a_2, ..., a_n$$ of values, the smooth factor of $$a$$ is the length of a ...
0
votes
1answer
25 views

Explanation of Distance of binary vectors formula

So, here's once again this article from topcoder about combinatorics. After the article successfully describes what theory it will use: Combinations/Permutations, it goes into an application for it, ...
0
votes
1answer
29 views

Getting rid of exponents with n when solving with annihilators: $a_n=a_{n-1}+2a_{n-2}+2^n+n^2$

To solve the following with annihilators: $a_n=a_{n-1}+2a_{n-2}+2^n+n^2$, for $n\ge2$, with initial conditions $a_1=0$ and $a_0=0$ we would have to get rid of the $2^n$ term at least, otherwise any ...
1
vote
1answer
35 views

Solving $\scriptsize a_n=\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+\ldots}}}$ with range transformation

This is a practice problem provided by a textbook on recurrences. Solve using range transformation: $a_n=\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+...}}}$, where $a_0$ =4 The hint is to view the ...
1
vote
0answers
35 views

A combinatorial way to understand $\sum \log^2 n $

Stirling's formula has many derivations using the factorial function: $$ \log N! = \sum_{n=1}^N \log n = \sum_{n=1}^N \sum_{m=1}^n \bigg( \log m - \log (m-1) \bigg) = \sum_{n=1}^N \sum_{m=1}^n - ...
0
votes
1answer
23 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
1
vote
3answers
33 views

Solving $a_n=5a(n/3)-6a(n/9)+2log_3n$ using domain transformation

$a_n=5a(n/3)-6a(n/9)+2log_3n$, For $n\ge9$ and n is a power of 3. $a_3=1$, and $a_1=0$ Transforming the first two terms is straightforward, but I'm not sure what to do with the log term. Should I ...
0
votes
2answers
26 views

Getting rid of $2^n$ when solving $a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ by characteristic roots

$a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ For $n\ge3$, With initial conditions $a_2=1$, $a_1=1$, and $a_0=1$ I'd like the find the particular solution with characteristic roots. However when generating ...
3
votes
1answer
25 views

Computational Theory: Proof, Chomsky normal form

Prove or disprove: If $G$ is a CFG in Chomsky normal form, then for any string $w \in L(G)$ of length $n\geq 1$ then exactly $2n-1$ steps are required for any derivation of $w$. I'm stuck at where to ...
0
votes
2answers
32 views

Help with Recurrence relations forward substitution and progression

I have seen a few questions regarding this topic. I have been unable to find one that could help me with analyzing the progression. My question :solve by recurrence relation using forward ...
3
votes
0answers
55 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
0
votes
1answer
23 views

Context free language false proof

What is wrong with the following proof? Show whether $L$ is context-free or not, where $L = \left\{ a^nb^{2n}a^n | n \geq 0\right\}$ We know $\left\{a^nb^n | n \geq 0 \right\} $ and $\left\{b^na^n | ...
0
votes
1answer
16 views

Minimum sum of products expression from k map

I am just looking for confirmation that I have done this correctly. Here is the truth table. and here is the answer that I got.
0
votes
0answers
16 views

Proof for Kolmogorov complexity is uncomputable using Turing reductions

I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, ...
2
votes
1answer
58 views

The output spanning tree of Kruskal's algorithm is a minimum spanning tree

I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction. We suppose that $S$ is not a minimum spanning tree. ...